nyoj--90--整数划分(母函数)

整数划分

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述

将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，

其中n1≥n2≥…≥nk≥1，k≥1。

正整数n的这种表示称为正整数n的划分。求正整数n的不

同划分个数。

例如正整数6有如下11种不同的划分：

6；

5+1；

4+2，4+1+1；

3+3，3+2+1，3+1+1+1；

2+2+2，2+2+1+1，2+1+1+1+1；

1+1+1+1+1+1。

输入

第一行是测试数据的数目M（1<=M<=10）。以下每行均包含一个整数n（1<=n<=10）。

输出

输出每组测试数据有多少种分法。

样例输入

1

6

样例输出

来源 [苗栋栋]原创 //母函数公式为：g(x)=(1+x+x^2+x^3+x^4+......)*(1+x^2+x^4+x^6+......)*(1+x^3+x^6+x^9+......)*...... //a[i]为第一项中的元素，b[i]第二项，数组中存入的都是系数，每次枚举出所有的系数 //但是大于n的都要舍去 #include<stdio.h> #include<string.h> int a[12],b[12]; int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<=n;i++) { a[i]=1; b[i]=0; } for(int i=2;i<=n;i++)//共有n-1个多项式 { for(int j=0;j<=n;j++)//每次枚举前边多项式中的每一项 { for(int k=0;k+j<=n;k+=i)//不同的i表示系数的等差 { b[k+j]+=a[j]; } } for(int j=0;j<=n;j++)//将新得到的数据重新存入到a中 { a[j]=b[j]; b[j]=0; } } printf("%d\n",a[n]); } return 0; }

巴特西

nyoj--90--整数划分(母函数)

整数划分

最新文章

热门文章