#include <iostream> #include <vector> typedef long long int ll; int n, m; ll p; int i; std::vector<ll> dp[2]; inline void set(int start,int len,ll value) { dp[1-(i&1)][start*m+len-1]=value; } inline ll get(int start,int len) { return dp[i&1][start*m+len-1]; } ll calc(int start,int len) { ll res=0; for(int len2=1;len2<=m;++len2) { int start2_start=start-len2+1; if(start2_start<0)start2_start=0; int start2_end=start+len-1; if(start2_end+len2-1>=m)start2_end=m-len2; for(int start2=start2_start;start2<=start2_end;++start2) res=(res+get(start2,len2))%p; } return res; } void step() { for(int start=0;start<m;++start) for(int len=1;len<=m-start;++len) set(start,len,calc(start,len)); } int main() { std::cin>>n>>m>>p; dp[0].resize(m*m,1); dp[1].resize(m*m); for(i=0;i<n;++i) step(); ll result=get(0,m); std::cout<<result; }
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 46 47 48 49 50 51 52 53 54 55 56 57 | #include <iostream> #include <vector> typedef long long int ll; int n, m; ll p; int i; std::vector<ll> dp[2]; inline void set(int start,int len,ll value) { dp[1-(i&1)][start*m+len-1]=value; } inline ll get(int start,int len) { return dp[i&1][start*m+len-1]; } ll calc(int start,int len) { ll res=0; for(int len2=1;len2<=m;++len2) { int start2_start=start-len2+1; if(start2_start<0)start2_start=0; int start2_end=start+len-1; if(start2_end+len2-1>=m)start2_end=m-len2; for(int start2=start2_start;start2<=start2_end;++start2) res=(res+get(start2,len2))%p; } return res; } void step() { for(int start=0;start<m;++start) for(int len=1;len<=m-start;++len) set(start,len,calc(start,len)); } int main() { std::cin>>n>>m>>p; dp[0].resize(m*m,1); dp[1].resize(m*m); for(i=0;i<n;++i) step(); ll result=get(0,m); std::cout<<result; } |