#include<bits/stdc++.h> using namespace std; #define st first #define nd second #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) typedef long long lli; typedef pair<int, int> pii; typedef pair<lli, lli> pll; typedef pair<lli, int> pli; typedef pair<int, lli> pil; const int N=1005; int n, k, mod, pascal[N][N], ile[N]; lli dp[N][N][3]; int32_t main() { boost; cin>>n>>k>>mod; for(int i=0;i<=n;i++) { pascal[i][0]=1; pascal[i][i]=1; for(int j=1;j<i;j++)pascal[i][j]=(pascal[i-1][j]+pascal[i-1][j-1])%mod; } dp[2][1][2]=1; ile[2]=1; for(int i=2;i<=n;i++) { for(int j=1;j<i;j++) { if(j==1) { for(int l=2;l<=i;l++) { if(l==i) { for(int m=2;m<i;m++) { int pom=pascal[i-3][m-2]; for(int p=1;p<=max(ile[m], ile[i-m+1]);p++) { lli blep=(lli((dp[m][p][2]-dp[m][p-1][2]+mod)%mod)*dp[i-m+1][p-1][2])%mod; blep=blep*pom%mod; dp[i][p][2]=(dp[i][p][2]+blep)%mod; blep=(lli((dp[i-m+1][p][2]-dp[i-m+1][p-1][2]+mod)%mod)*dp[m][p-1][2])%mod; blep=blep*pom%mod; dp[i][p][2]=(dp[i][p][2]+blep)%mod; blep=(lli((dp[m][p][2]-dp[m][p-1][2]+mod)%mod)*((dp[i-m+1][p][2]-dp[i-m+1][p-1][2]+mod)%mod))%mod; blep=blep*pom%mod; dp[i][p+1][2]=(dp[i][p+1][2]+blep)%mod; } } } else { int pom=pascal[i-2][l-2]; for(int p=1;p<=max(ile[l], ile[i-l+1]);p++) { lli blep=((lli(dp[l][p][2])*dp[i-l+1][p][1]%mod)-(lli(dp[l][p-1][2])*dp[i-l+1][p-1][1]%mod)+mod)%mod; blep=blep*pom%mod; dp[i][p][1]=(dp[i][p][1]+blep)%mod; } } } } else { int pom=pascal[i-1][j-1]; for(int p=1;p<=max(ile[j], ile[i-j+1]);p++) { lli blep=((lli(dp[j][p][1])*dp[i-j+1][p][1]%mod)-(lli(dp[j][p-1][1])*dp[i-j+1][p-1][1]%mod)+mod)%mod; blep=blep*pom%mod; dp[i][p][0]=(dp[i][p][0]+blep)%mod; } } } for(int j=1;j<=max(i, 20);j++) { if(dp[i][j][0]+dp[i][j][1]+dp[i][j][2]!=0)ile[i]=j; dp[i][j][1]=(dp[i][j][1]+dp[i][j][2])%mod; dp[i][j][0]=(dp[i][j][0]+dp[i][j][1]*2)%mod; for(int l=0;l<=2;l++)dp[i][j][l]=(dp[i][j][l]+dp[i][j-1][l])%mod; } } lli wyn=(dp[n][k][0]-dp[n][k-1][0]+mod)%mod; cout<<wyn<<"\n"; 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 89 90 91 92 93 94 | #include<bits/stdc++.h> using namespace std; #define st first #define nd second #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) typedef long long lli; typedef pair<int, int> pii; typedef pair<lli, lli> pll; typedef pair<lli, int> pli; typedef pair<int, lli> pil; const int N=1005; int n, k, mod, pascal[N][N], ile[N]; lli dp[N][N][3]; int32_t main() { boost; cin>>n>>k>>mod; for(int i=0;i<=n;i++) { pascal[i][0]=1; pascal[i][i]=1; for(int j=1;j<i;j++)pascal[i][j]=(pascal[i-1][j]+pascal[i-1][j-1])%mod; } dp[2][1][2]=1; ile[2]=1; for(int i=2;i<=n;i++) { for(int j=1;j<i;j++) { if(j==1) { for(int l=2;l<=i;l++) { if(l==i) { for(int m=2;m<i;m++) { int pom=pascal[i-3][m-2]; for(int p=1;p<=max(ile[m], ile[i-m+1]);p++) { lli blep=(lli((dp[m][p][2]-dp[m][p-1][2]+mod)%mod)*dp[i-m+1][p-1][2])%mod; blep=blep*pom%mod; dp[i][p][2]=(dp[i][p][2]+blep)%mod; blep=(lli((dp[i-m+1][p][2]-dp[i-m+1][p-1][2]+mod)%mod)*dp[m][p-1][2])%mod; blep=blep*pom%mod; dp[i][p][2]=(dp[i][p][2]+blep)%mod; blep=(lli((dp[m][p][2]-dp[m][p-1][2]+mod)%mod)*((dp[i-m+1][p][2]-dp[i-m+1][p-1][2]+mod)%mod))%mod; blep=blep*pom%mod; dp[i][p+1][2]=(dp[i][p+1][2]+blep)%mod; } } } else { int pom=pascal[i-2][l-2]; for(int p=1;p<=max(ile[l], ile[i-l+1]);p++) { lli blep=((lli(dp[l][p][2])*dp[i-l+1][p][1]%mod)-(lli(dp[l][p-1][2])*dp[i-l+1][p-1][1]%mod)+mod)%mod; blep=blep*pom%mod; dp[i][p][1]=(dp[i][p][1]+blep)%mod; } } } } else { int pom=pascal[i-1][j-1]; for(int p=1;p<=max(ile[j], ile[i-j+1]);p++) { lli blep=((lli(dp[j][p][1])*dp[i-j+1][p][1]%mod)-(lli(dp[j][p-1][1])*dp[i-j+1][p-1][1]%mod)+mod)%mod; blep=blep*pom%mod; dp[i][p][0]=(dp[i][p][0]+blep)%mod; } } } for(int j=1;j<=max(i, 20);j++) { if(dp[i][j][0]+dp[i][j][1]+dp[i][j][2]!=0)ile[i]=j; dp[i][j][1]=(dp[i][j][1]+dp[i][j][2])%mod; dp[i][j][0]=(dp[i][j][0]+dp[i][j][1]*2)%mod; for(int l=0;l<=2;l++)dp[i][j][l]=(dp[i][j][l]+dp[i][j-1][l])%mod; } } lli wyn=(dp[n][k][0]-dp[n][k-1][0]+mod)%mod; cout<<wyn<<"\n"; return 0; } |