51nod 1201 整数划分 dp

基准时间限制：1 秒空间限制：131072 KB

关注

将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示例

Output示例

思路：dp[i][j]表示i分成j个数的方案；

　　　dp[i][j]=dp[i-j][j]+dp[i-j][j-1];

　　　一个表示含有1的数目，一个表示不含有1的数目；

　　　nsqrt（n）；

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<bitset>

#include<set>

#include<map>

#include<time.h>

using namespace std;

#define LL long long

#define bug(x)  cout<<"bug"<<x<<endl;

const int N=5e4+,M=1e6+,inf=1e9+,MOD=1e9+;

const LL INF=1e18+,mod=1e9+;

const double eps=(1e-),pi=(*atan(1.0));

int dp[N][];

int main()

{

    dp[][]=;

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

    {

        for(int j=;i>=j&&j<=;j++)

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

    }

    int n,ans=;

    scanf("%d",&n);

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

        ans+=dp[n][i],ans%=mod;

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

    return ;

}

秒客网

51nod 1201 整数划分 dp

相关文章