dp小总结

写在前面

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)

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define N 1005

 #define M 15

 int n,d,mod,dp[N][M][N],inv[N];

 int pw(int a,int b){int r=;for(;b;b>>=,a=1ll*a*a%mod)if(b&)r=1ll*r*a%mod;return r;}

 int main()

 {

     scanf("%d%d%d",&n,&d,&mod);

     if(n<=){puts("");return ;}

     for(int i=;i<n;i++)inv[i]=pw(i,mod-);

     dp[][][]=dp[][d-][]=;

     for(int i=;i<=n;i++)for(int j=;j<=d;j++)for(int k=;k<i;k++)

     {

         dp[i][j][k]=dp[i][j][k-];

         int r=dp[k][d-][k-],c=;

         for(int t=;t*k<i&&t<=j;t++,r++)

         {

             c=1ll*c*r%mod*inv[t]%mod;

             dp[i][j][k]=(dp[i][j][k]+1ll*dp[i-t*k][j-t][min(i-t*k-,k-)]*c)%mod;

         }

     }

     int ans=dp[n][d][(n+)/-];

     if(n%==)ans=(ans+1ll*dp[n/][d-][n/-]*(dp[n/][d-][n/-]+)/)%mod;

     printf("%d\n",ans);

     return ;

 }

巴特西

dp小总结

最新文章

热门文章