正整数拆分
hdu1028
解:
对于正整数 $n$ 的拆分,其母函数为
$$f(x) = (1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+x^9+...)...$$
答案就是多项式展开后 $x^n$ 项的系数。
Code:
//其实就是模拟,从前往后一一合并
#include<bits/stdc++.h> using namespace std; const int _max = 10001; int c1[_max], c2[_max]; //c1存放前面项计算出来的结果,c2存放中间结果 int n; int main() { while(scanf("%d", &n) == 1) { for(int i=0; i<=n; ++i) { c1[i] = 1; //第一项系数全1 c2[i] = 0; //中间变量初始化为0 } for(int i=2; i<=n; ++i) // 最多涉及前n项 { for(int j=0; j<=n; ++j) // 枚举c1中的项 for(int k=0; k+j<=n; k+=i) // 枚举第i个大括号中的项 { c2[j+k] += c1[j]; } for(int j=0; j<=n; ++j) //转移到c1 { c1[j] = c2[j]; c2[j] = 0; } } printf("%d\n", c1[n]); } return 0; }
参考链接:Tanky Woo——http://www.wutianqi.com/blog/596.html