写在前面
Just some easy problem solving with dynamic programming.
(Given me a dynamic programming table, I can tell you a new world.)
juruo眼中的神仙dp,(测试博客园的blog最多允许多长系列)
lv1 codeforces 724D
日常口胡:傻子也知道,答案最多sqrt(n)个,切了.
正常思路:性质1:答案最多sqrt(n)个:1.1<=k<=sqrt(n) 不同答案最多sqrt(n)个 2.k>sqrt(n) ans<=n/k<=sqrt(n) 最多sqrt(n)个.
性质2:满足单调性(不难从k的方案中构造出答案相同的k-1的方案),
于是二分/整体二分边界,O(nsqrt(n)logn)
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define N 1005 5 #define M 15 6 int n,d,mod,dp[N][M][N],inv[N]; 7 int pw(int a,int b){int r=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)r=1ll*r*a%mod;return r;} 8 int main() 9 { 10 scanf("%d%d%d",&n,&d,&mod); 11 if(n<=2){puts("1");return 0;} 12 for(int i=1;i<n;i++)inv[i]=pw(i,mod-2); 13 dp[1][0][0]=dp[1][d-1][0]=1; 14 for(int i=2;i<=n;i++)for(int j=1;j<=d;j++)for(int k=1;k<i;k++) 15 { 16 dp[i][j][k]=dp[i][j][k-1]; 17 int r=dp[k][d-1][k-1],c=1; 18 for(int t=1;t*k<i&&t<=j;t++,r++) 19 { 20 c=1ll*c*r%mod*inv[t]%mod; 21 dp[i][j][k]=(dp[i][j][k]+1ll*dp[i-t*k][j-t][min(i-t*k-1,k-1)]*c)%mod; 22 } 23 } 24 int ans=dp[n][d][(n+1)/2-1]; 25 if(n%2==0)ans=(ans+1ll*dp[n/2][d-1][n/2-1]*(dp[n/2][d-1][n/2-1]+1)/2)%mod; 26 printf("%d ",ans); 27 return 0; 28 }