UESTC 1726 整数划分（母函数水题）
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：将整数n进行划分，要求不能有相同的数，问有多少种划分种数
http://acm.uestc.edu.cn/problem.php?pid=1726
简单的母函数水题。
(1+x)*(1+x^2)*(1+x^3)……(1+x^n)。表示1……n最多只能取1次
最终求的是x^n的系数
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<string>#include<vector>#include<algorithm>#include<map>#include<set>#define maxn 200005#define eps 1e-8#define inf 1<<30#define LL long long#define zero(a) fabs(a)<eps#define MOD 19901014#define N 47000using namespace std;int c1[1005]={0},c2[1005]={0};int main(){c1[0]=1;c1[1]=1;for(int i=2;i<=1000;i++){for(int j=0;j<=1000;j++){c2[j]=(c2[j]+c1[j])%MOD;if(j+i<=1000)c2[j+i]=(c2[j+i]+c1[j])%MOD;}for(int j=0;j<=1000;j++){c1[j]=c2[j];c2[j]=0;}}int t,n;scanf("%d",&t);while(t--){scanf("%d",&n);printf("%d\n",c1[n]);}return 0;}