学步园

G(x)=(1+x+x2+x3+x4+…)(1+x4+x8+x12+…)(1+x9+x18+x27+…)…

典型母函数！

//HDOJ_1398  Square Coins
//G(x)=(1+x+x^2+x^3+x^4+…)(1+x^4+x^8+x^12+…)(1+x^9+x^18+x^27+…)…
#include <iostream>
using namespace std;
const int lmax=300;
int c1[lmax+1],c2[lmax+1];
int main(void)
{	int n,i,j,k;
	while (cin>>n &&n)
	{	for (i=0;i<=n;i++)
		{	c1[i]=1;	c2[i]=0;		}//1
		for (i=2;i<=17;i++)//2
		{	for (j=0;j<=n;j++)//3
				for (k=0;k+j<=n;k+=i*i)//4
				{	c2[j+k]+=c1[j];	}
			for (j=0;j<=n;j++)//5
			{	c1[j]=c2[j];	c2[j]=0;	}
		}
		cout<<c1[n]<<endl;
	}
	return 0;
}

几点说明：第i个括号里面的指数为K的系数为j

1: 对c1初始化，由第一个表达式(1+x+x²+..x^17)初始化，把质量从0到17的所有硬币个数都初始化为1.

2： i从2到n遍历，一次模拟手工打开括号，从第二个到低17个括号

3：j
从0到n遍历，这里j就是里第j个变量的系数。.   

4: k表示的是第j个指数，所以k每次增i*i

5:为打开下一个括号准备

//HDOJ_1398  Square Coins
//变化一点点，灵活多多多
…
int main(void)
{	int n,i,j,k;
    int elem[17]={1,4,9,16,25,36,…,169,196,225,256,289}
	while (cin>>n && n!=0)
	{	for (i=0;i<=n;i++)
		{	c1[i]=1;	c2[i]=0;		}
		for (i=2; i<=17; i++)
		{	for (j=0;j<=n;j++)
				for (k=0;k+j<=n; k+=elem[i-1] ) 
				{	c2[j+k]+=c1[j];	}
			for (j=0;j<=n;j++)
			{	c1[j]=c2[j];	c2[j]=0;	}
		}
		cout<<c1[n]<<endl;
	}
	return 0;
}

变化一下就可以敢好多事情啦!

杭电1028：

//整数拆分。由于拆分结果只考虑有几个1几个2几个3...Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem.问题就和之前的砝码邮票什么的一样了。
//G(x)=(1+x+...)(1+x^2+...)(1+x^3....)...(1+x^n)

#include <iostream>
using namespace std;
const int lmax=120;
int c1[lmax+1],c2[lmax+1];
int main(void)
{
    int n,i,j,k;
    while (cin>>n )
    {
        for (i=0; i<=n; i++)
        {
            c1[i]=1;	   //1
            c2[i]=0;
        }
        for (i=2; i<=n; i++) //每个有n个
        {
            for (j=0; j<=n; j++) //3
                for (k=0; k+j<=n; k+=i) //4
                {
                    c2[j+k]+=c1[j];
                }
            for (j=0; j<=n; j++) //5
            {
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
        cout<<c1[n]<<endl;
    }
    return 0;
}

看完上面也许觉得还是不太明白，有点感觉自己蒙混过关的意思，下面看完下面这个题就是很傻逼的方法：

//HDOJ1085
//G(x)=(1+x+x^2+...+x^a)*(1+x^2+x^4...+x^2b)*(1+x^5+x^10+...+x^5c)
#include <iostream>
using namespace std;
const int lmax=8000;
int c1[lmax+1],c2[lmax+1];
int main(void)
{
    int i,j,k,a,b,c;
    while (cin>>a >> b >> c,a||b||c)//这种写法简练
    {
        for (i=0; i<=lmax; i++)
        {
            c1[i]=1;
            c2[i]=0;
        }
        for(i=0; i<=a*1; i++)     c1[i]=1;//第一个括号的系数
        for(i=0; i<=a; i++)
            for(j=0;j<=b*2; j+=2)
                 c2[i+j]+=c1[j];
        for(i=0;i<=a+(b*2);i++)//刷新一下
       {
           c1[i]=c2[i];
           c2[i]=0;
       }
       for(i=0;i<=a+(b*2);i++)

          for(int j=0;j<=c*5;j+=5)

              c2[i+j]+=c1[i];


       for(i=0;i<=a+(b*2)+(c*5);i++)
       {
           c1[i]=c2[i];
           c2[i]=0;
       }
       for(i=0;i<=a+(b*2)+(c*5);i++)
       {
           if(c1[i]==0)//不能支付
           {
              cout  << i << endl;
               break;
           }
       }
       if(i==a+(b*2)+(c*5)+1)  cout << i << endl;//可以支付前面所有的
    }
    return 0;
}

PS:这个资料很不错！