poj 1221 UNIMODAL PALINDROMIC DECOMPOSITIONS (母函數)

poj 1221 UNIMODAL PALINDROMIC DECOMPOSITIONS (母函數)

/*
給出一個數n，把它拆分成若干個數的和，要求最大的數在中間並向兩邊非遞增。問拆法有多少種。

母函數。枚舉中間的那一個數，因為左右對稱，所以只需要求左邊部分的方案即可。
注意，左右兩部分的取數必須小於中間的數，中間的數是0的話則以n為最大取值。
*/
# include 
# include 
# include 
# include 
typedef long long LL;
using namespace std;
LL c1[10010],c2[10010];
LL slove(LL m,LL n)
{

    for(int i=0; i<=n; i++)
    {
        c1[i]=1;
        c2[i]=0;
    }
    if(m==0)
        m=n;
    for(int i=2; i<=m; i++)
    {
        for(int j=0; j<=n; j++)
        {
            for(int k=0; k+j<=n; k+=i)
            {
                c2[k+j]+=c1[j];
            }
        }
        for(int j=0; j<=n; j++)
        {
            c1[j]=c2[j];
            c2[j]=0;
        }
    }
    return c1[n];
}
int main()
{
    int  n;
    LL ans;
    while(~scanf("%d",&n),n)
    {
        ans=0;
        for(int i=0;i<=n;i++)
        {
            if((n-i)%2==0)
               {
                   ans+=slove(i,(n-i)/2);
               }
        }
        printf("%d %lld\n",n,ans);
    }
    return 0;
}