母函数--1~n无限组成n的方法数--模板
#include <bits/stdc++.h> //1~n_Num 无限组成n_Num的方法数 using namespace std; const int maxn=10001; int c1[maxn],c2[maxn]; //c1保存各种组合的方法数 //c2是中间变量 int main() { int n_Num,i,j,k; while(~scanf("%d",&n_Num)) { for(int i=0;i<=n_Num;i++)//初始化第一个式子 {//(1+x+x^2+x^3+...+x^n)各种质量方法数都是1 c1[i]=1; c2[i]=0; } for(int i=2;i<=n_Num;i++)//从第二个式子开始 { for(int j=0;j<=n_Num;j++)//j表示前面累乘的式子的第j个数 //对于(1+x)(1+x^2)(1+x^3) //i=2 指行完成后 (1+x+x^2+x^3)j就指向这个式子 //c1指向累乘的式子的系数 c2是新的式子 for(int k=0;k+j<=n_Num;k+=i)//第i个式子每次增量是i,所以加i {//这个k指第j个数的指数 c2[k+j]+=c1[j]; } for(int j=0;j<=n_Num;j++) { c1[j]=c2[j]; c2[j]=0; } } printf("%d ",c1[n_Num]); } return 0; }优质内容筛选与推荐>>