HDU1284錢幣兌換問題( 母函數打表)

題解：用母函數暴力打表，因為錢幣取值給定，是不變的，所以只有三個表達式G（x）=（1+x+x^2+x^3+……+x^MAX）（1+x^2+x^4+……+x^2*MAX）（1+x^3+x^6+……+x^3*MAX）；要把循環放在外面，要不然TEL；

 
#include<cstdio>   
using namespace std;  
#define MAX 32768   
int a1[MAX],a2[MAX];  
void init()//暴力打表   
{  
    int i,j,k;  
    for(i=0;i<MAX;i++)  
    {  
        a1[i]=1;  
        a2[i]=0;  
    }  
    for(i=2;i<=3;i++)  
    {  
        for(j=0;j<MAX;j++)  
        for(k=0;k+j<MAX;k+=i)  
        a2[j+k]+=a1[j];  
        for(j=0;j<MAX;j++)  
        {  
            a1[j]=a2[j];  
            a2[j]=0;  
        }  
    }  
  
}  
int main()  
{  
    init();  
    int n;  
    while(scanf("%d",&n)!=EOF)  
    printf("%d\n",a1[n]);  
    return 0;  
}