说明

这段代码用于计算一个整数的单峰回文分解数目。单峰回文分解是指将一个整数拆分成若干个数的和，这些数构成一个回文序列，并且序列在中间值之前不下降，从中间到末尾不再上升（即单峰性质）。例如，整数4的单峰回文分解有4种：(4)、(1 2 1)、(2 2)、(1 1 1 1)。

算法标签

• 动态规划：使用母函数（生成函数）的方法计算拆分数。
• 组合数学：通过生成函数计算拆分的组合数。
• 回文分解：利用对称性简化计算。

解题思路

1. 问题分析：需要将一个整数拆分成一个单峰回文序列，即序列对称且中间值最大。
2. 关键观察：由于序列是回文的，只需计算左半部分的拆分方式，右半部分对称即可。中间的数可以是任意不超过剩余数的值。
3. 算法选择：
   • 使用母函数方法计算左半部分的拆分方式。
   • 枚举中间的数，计算剩余数拆分成不大于中间数的数的组合数。
   • 累加所有可能的中间数对应的组合数。

分析

1. 母函数方法：slove(m, n)函数计算将整数n拆分成不超过m的数的组合数。若m为0，则拆分数不超过n。
2. 动态规划初始化：c1数组初始化为1，表示拆分成1的组合数。
3. 递推计算：对于每个数i（从2到m），更新组合数c1，表示拆分成不超过i的数的组合数。
4. 结果累加：对于每个可能的中间数i，若剩余数(n-i)为偶数，则计算左半部分的拆分数slove(i, (n-i)/2)并累加。

实现步骤

1. 输入处理：读取输入的整数n，直到遇到0为止。
2. 枚举中间数：对于每个n，枚举所有可能的中间数i（从0到n）。
3. 检查剩余数：若(n-i)为偶数，则计算左半部分的拆分数。
4. 输出结果：输出每个n及其对应的单峰回文分解数目。

代码解释

• 母函数计算：slove(m, n)函数使用动态规划计算拆分数，c1和c2数组分别存储当前和下一步的组合数。
• 主函数：读取输入，枚举中间数，调用slove函数计算拆分数，并累加结果。
• 输出格式：按题目要求输出每个整数及其分解数目。

通过这种方法，程序能够高效地计算每个整数的单峰回文分解数目。

代码

/*
给出一个数n，把它拆分成若干个数的和，要求最大的数在中间并向两边非递增。问拆法有多少种。

母函数。枚举中间的那一个数。由于左右对称。所以仅仅须要求左边部分的方案就可以。

注意，左右两部分的取数必须小于中间的数，中间的数是0的话则以n为最大取值。


*/
# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <iostream>
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;
}