51nod 1201 整数划分

Type:DP,思维

题意

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

Input

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

Output

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

Input示例

6

Output示例

4

题解

首先我们可以由

1+2+3+…+m=n 估算出 大概只有sqrt(2*n)个数字左右

我们设当前状态为 dp[i][j]

dp[i][j] 代表当前数字为 j ,被划分成了 i 部分.
状态转移推倒:

我们假设已知所有 dp 的划分数序列.

(1) 我们将 dp[i][j-i] 每个 划分数每个数字 +1 ,我们将得到 不存在1 的划分数.

(2) 我们将 dp[i-1][j-i] 每个 划分数每个数字(共 i-1 个) +1 ,我们将得到 不存在1 的且长度为 i-1 ,和为 j-1 的划分数,然后我们将 1 放到划分数中,即得到全部 有1 的划分数.

即 dp[i][j]=(dp[i][j-i]+dp[i-1][j-i])%mod

正确性证明:

假设已知 dp[i][j] 的全部序列.
我们只需要一直对每个数字 -1 就可以将所有序列置为 全0.

给一个例子自己倒着推一下也成立

组成1的 有 {1} 

组成2的 有 {2} 

组成3的 有 {1,2} {3}

组成4的 有 {1,3} {4}

组成5的 有 {1,4} {2,3} {5}

组成6的 有 {1,5} {2,4} {1,2,3} {6}

组成7的 有 {1,6} {2,5} {3,4} {1,2,4} {7}

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=50010;
const LL mod=1e9+7;
int N;
LL dp[330][maxn];

int main(){
    scanf("%d",&N);
    dp[1][1]=1ll;
    for(int i=2;i<=N;++i){
        for(int j=1;j<=(int)sqrt(2*i);++j){
            dp[j][i]=(dp[j][i-j]+dp[j-1][i-j])%mod;
        }
    }
    LL ans=0;
    for(int i=1;i<=(int)sqrt(2*N);++i) ans=(ans+dp[i][N])%mod;
    printf("%lld\n",ans);
    return 0;
}