51nod-1259-分块+dp

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1259

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

将N分为若干个整数的和，有多少种不同的划分方式，例如：n = 4，{4} {1,3} {2,2} {1,1,2} {1,1,1,1}，共5种。由于数据较大，输出Mod 10^9 + 7的结果即可。

Input

输入1个数N(1 <= N <= 50000)。

Output

输出划分的数量Mod 10^9 + 7。

Input示例

Output示例

5

  与1201相似但是允许出现重复的数，如果还按照1201的写法，复杂度就是平方级了，看了讨论的解法感觉很巧妙。
  利用分块将数据分成了[1,sqrt(n)],[sqrt(n)+1,n]两部分，分别用f[i][j]和g[i][j]表示用区间内的数j个组合成和为i的数的方案个数，计算f时无限背包，计算g时使用1201的
方程计算（注意这里的区间最小的值是sqrt(n+1）)。最后用乘法原理计算答案ans=SUM{f[n][i]*h[n-i]},其中0<=i<=n,h[i]表示g[i][..]的总和。注意乘法时候会爆int使用longlong就好了。

 #include<bits/stdc++.h>

 using namespace std;

 const int mod=1e9+;

 #define LL long long

 int f[],g[][];

 int main()

 {

     int n,i,j,k;

     cin>>n;

     f[]=;

     int m=sqrt(n*1.0);

     for(i=;i<=m;++i)

         for(j=i;j<=n;++j)

      f[j]=(f[j]+f[j-i])%mod;

      g[][]=;

      g[m+][]=;

     for(i=m+;i<=n;++i)

     {

         int k=i/(m+);

         for(j=;j<=k;++j)

         {

             if(i+j<=n){

             g[i+j][j]=(g[i+j][j]+g[i][j])%mod;

             }

             if(i+m+<=n){

             g[i+m+][j+]=(g[i+m+][j+]+g[i][j])%mod;

             }

             g[i][]=(g[i][]+g[i][j])%mod;

         }

     }

     LL ans=;

     for(i=;i<=n;++i)

         ans=(ans+(LL)f[i]*g[n-i][]%mod)%mod;

     cout<<ans<<endl;

     return ;

 }