Partition
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 114 Accepted Submission(s): 46
Problem Description
How many ways can the numbers 1 to 15 be added together to make 15? The technical term for what you are asking is the "number of partition" which is often called P(n). A partition of n is a collection of positive integers (not necessarily distinct) whose sum equals n. Now, I will give you a number n, and please tell me P(n) mod 1000000007.
Input
The first line contains a number T(1 ≤ T ≤ 100), which is the number of the case number. The next T lines, each line contains a number n(1 ≤ n ≤ 10 5) you need to consider.
Output
For each n, output P(n) in a single line.
Sample Input
4 5 11 15 19
Sample Output
7 56 176 490
Source
Recommend
zhuyuanchen520
根本就不会嘛公式谁会推啊，写个DP超，果断搜公式爆搜，终于找到了维基百科的公式了，结果题解给的就是这个网站。哎！这就一公式。
#include背包版本#include #include #define FOR(i,a,b) for(int i=a;i<=b;++i)#define clr(f,z) memset(f,z,sizeof(f))#define LL __int64using namespace std;const int mm=1e5+9;const LL mod=1000000007;LL dp[mm],f[mm];void getdata(){ int zt=1000; FOR(i,-1000,1000)f[i+zt]=i*(3*i-1)/2; dp[0]=1; FOR(i,1,mm-1) { dp[i]=0; FOR(j,1,i) { if(f[j+zt]<=i) { if(j&1) { dp[i]+=dp[i-f[j+zt]]; } else dp[i]-=dp[i-f[j+zt]]; } else break; dp[i]=(dp[i]%mod+mod)%mod; if(f[zt-j]<=i) { if(j&1) { dp[i]+=dp[i-f[zt-j]]; } else dp[i]-=dp[i-f[zt-j]]; } else break; } dp[i]=(dp[i]%mod+mod)%mod; }}int main(){ int cas; getdata();int n; while(~scanf("%d",&cas)) { while(cas--) { scanf("%d",&n); printf("%I64d\n",dp[n]); } } return 0;}
#include递归版本#include #include #include using namespace std;int a[100001];int main(){ //freopen("data.txt","w",stdout); int lim = 10000; a[0] = 1; for(int i=1;i<=lim;i++) for(int j=0;j+i<=lim;j++){ a[i+j] = (a[i+j] + a[j]); if (a[i+j] >= 1000000007) a[i+j] -= 1000000007; } int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); printf("%d\n",a[n]); } return 0;}
#include#include #include #define FOR(i,a,b) for(int i=a;i<=b;++i)#define clr(f,z) memset(f,z,sizeof(f))#define LL __int64using namespace std;const int mm=1e5+9;const LL mod=1000000007;const int cd=1000;LL dp[mm][cd];LL Part(LL n,LL m){ if ((n < 1)||(m < 1)) return 0; if ((n == 1)||(m == 1)) return 1; if(m<1000&&dp[n][m]!=-1)return dp[n][m]; LL ret=0; if (n < m) {ret=Part(n, n); ret%=mod; if(m<1000)dp[n][m]=ret; return ret; } if (n == m) {ret=Part(n, m-1) + 1; ret%=mod; if(m<1000)dp[n][m]=ret; return ret; } ret=Part(n, m-1) + Part(n-m, m); ret%=mod; if(m<1000)dp[n][m]=ret; return ret;}int main(){ int cas,n; clr(dp,-1); while(~scanf("%d",&cas)) { while(cas--) { //scanf("%d",&n); FOR(i,1,50) { n=i; printf("%d %I64d\n",i,Part(n,n)); } } } return 0;}
整数划分，求每个划分。
void print_partition(int n){ int i = 1; int m = 1; int h = 1; int t, r; int a[n + 1]; for (; i < n + 1; ++i) a[i] = 1; a[1] = n; printf("%d \n", a[1]); while (a[1] != 1) { if (a[h] == 2) { a[h--]--; m++; } else { r = --a[h]; t = m - h + 1; while (t >= r) { a[++h] = r; t -= r; } if (t == 0) m = h; else m = h + 1; if (t >= 2) a[++h] = t; } for (i = 1; i < m + 1; i++) printf("%d ", a[i]); printf("\n"); }}