#include <bits/stdc++.h> using namespace std; int mod; int n,m; inline int w(int i, int j) { return i*(m+1)+j; } int dp[25000005]; int pref1[25000005]; int pref2[25000005]; int main() { ios_base::sync_with_stdio(0); cin>>n>>m>>mod; // dp[w(0,1)]=1; for(int j=1;j<=m;j++)dp[w(1,j)]=j; for(int i=2;i<=n;i++) { int sum=0; for(int j=1;j<=m;j++) { sum+=dp[w(i-1,j)]; if(sum>mod)sum-=mod; pref1[w(i-1,j)]=pref1[w(i-1,j-1)]+dp[w(i-1,j)]; if(pref1[w(i-1,j)]>mod)pref1[w(i-1,j)]-=mod; pref2[w(i-1,j)]=pref2[w(i-1,j-1)]+pref1[w(i-1,j)]; if(pref2[w(i-1,j)]>mod)pref2[w(i-1,j)]-=mod; } for(long long j=1;j<=m;j++) { long long tmp=j*sum-j*pref1[w(i-1,m-j)]-pref2[w(i-1,j-1)]; tmp%=mod; if(tmp<0)tmp+=mod; dp[w(i,j)]=tmp; } } long long res=0; for(int j=1;j<=m;j++)res+=dp[w(n,j)]; cout<<res%mod<<endl; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <bits/stdc++.h> using namespace std; int mod; int n,m; inline int w(int i, int j) { return i*(m+1)+j; } int dp[25000005]; int pref1[25000005]; int pref2[25000005]; int main() { ios_base::sync_with_stdio(0); cin>>n>>m>>mod; // dp[w(0,1)]=1; for(int j=1;j<=m;j++)dp[w(1,j)]=j; for(int i=2;i<=n;i++) { int sum=0; for(int j=1;j<=m;j++) { sum+=dp[w(i-1,j)]; if(sum>mod)sum-=mod; pref1[w(i-1,j)]=pref1[w(i-1,j-1)]+dp[w(i-1,j)]; if(pref1[w(i-1,j)]>mod)pref1[w(i-1,j)]-=mod; pref2[w(i-1,j)]=pref2[w(i-1,j-1)]+pref1[w(i-1,j)]; if(pref2[w(i-1,j)]>mod)pref2[w(i-1,j)]-=mod; } for(long long j=1;j<=m;j++) { long long tmp=j*sum-j*pref1[w(i-1,m-j)]-pref2[w(i-1,j-1)]; tmp%=mod; if(tmp<0)tmp+=mod; dp[w(i,j)]=tmp; } } long long res=0; for(int j=1;j<=m;j++)res+=dp[w(n,j)]; cout<<res%mod<<endl; } |