#include <bits/stdc++.h> using namespace std; int a,b; long long c,odp; long long tab[2][4000][4000]; long long szybpot(long long pod,long long wyk) { long long ret=1; while(wyk) { if(wyk%2==1) ret=(ret*pod)%c; wyk/=2; pod=(pod*pod)%c; } return ret; } int main() { scanf("%d%d%lld",&a,&b,&c); if(a==1) { printf("%lld",(((b*(b+1))%c)*szybpot(2,c-2))%c); return 0; } if(b==2) { long long ter=3,popr=1,pom; for(int i=2;i<=a;++i) { pom=ter; ter=(popr+(2*ter)%c)%c; popr=pom; } printf("%lld",ter); return 0; } for(int i=1;i<=b;++i) { for(int j=1;j<=i;++j) { tab[0][i][j]=1; } } for(int i=1;i<a;++i) { for(int j=1;j<=b;++j) { for(int k=1;k<=j;++k) tab[i%2][j][k]=0; for(int k=b;k>=j;--k) { for(int l=k-j+1;l<=k;++l) { for(int m=1;m<=j;++m) { tab[i%2][j][m]+=tab[(i+1)%2][k][l]; tab[i%2][j][m]%=c; } } } for(int k=j-1;k>0;--k) { for(int l=1;l<=k;++l) { for(int m=j-k+1;m<=j;++m) { tab[i%2][j][m]+=tab[(i+1)%2][k][l]; tab[i%2][j][m]%=c; } } } } } for(int i=1;i<=b;++i) { for(int j=1;j<=i;++j) { odp+=tab[(a-1)%2][i][j]; odp%=c; } } printf("%lld",odp); return 0; }
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | #include <bits/stdc++.h> using namespace std; int a,b; long long c,odp; long long tab[2][4000][4000]; long long szybpot(long long pod,long long wyk) { long long ret=1; while(wyk) { if(wyk%2==1) ret=(ret*pod)%c; wyk/=2; pod=(pod*pod)%c; } return ret; } int main() { scanf("%d%d%lld",&a,&b,&c); if(a==1) { printf("%lld",(((b*(b+1))%c)*szybpot(2,c-2))%c); return 0; } if(b==2) { long long ter=3,popr=1,pom; for(int i=2;i<=a;++i) { pom=ter; ter=(popr+(2*ter)%c)%c; popr=pom; } printf("%lld",ter); return 0; } for(int i=1;i<=b;++i) { for(int j=1;j<=i;++j) { tab[0][i][j]=1; } } for(int i=1;i<a;++i) { for(int j=1;j<=b;++j) { for(int k=1;k<=j;++k) tab[i%2][j][k]=0; for(int k=b;k>=j;--k) { for(int l=k-j+1;l<=k;++l) { for(int m=1;m<=j;++m) { tab[i%2][j][m]+=tab[(i+1)%2][k][l]; tab[i%2][j][m]%=c; } } } for(int k=j-1;k>0;--k) { for(int l=1;l<=k;++l) { for(int m=j-k+1;m<=j;++m) { tab[i%2][j][m]+=tab[(i+1)%2][k][l]; tab[i%2][j][m]%=c; } } } } } for(int i=1;i<=b;++i) { for(int j=1;j<=i;++j) { odp+=tab[(a-1)%2][i][j]; odp%=c; } } printf("%lld",odp); return 0; } |