题意分析

本题要求计算正整数 ( N ) 的递归回文分划数目。递归回文分划的定义如下：

1. 回文性：分划序列正向和反向相同。
2. 递归性：分划的左半部分（去掉中间元素后）也是递归回文分划，或左半部分为空（即分划长度为1）。

关键性质：

• 分划可视为由中心元素（可能不存在，当长度为偶数时）和左右对称的部分组成。
• 左半部分必须是递归回文分划，右半部分是左半部分的逆序。

解题思路

1. 动态规划建模

设 ( dp[n] ) 表示正整数 ( n ) 的递归回文分划数目。根据分划的结构，可分为以下两种情况：

• 分划长度为1：即分划仅包含 ( n ) 本身，贡献1种分划。
• 分划长度为奇数 ( 2k+1 )：中心元素为 ( c )，左右各有 ( k ) 个元素，且左右部分互为逆序，左部分是递归回文分划。此时，分划可表示为 $[a_1, a_2, \dots, a_k, c, a_k, \dots, a_2, a_1]$，其中 $ a_1 + a_2 + \dots + a_k + c + a_k + \dots + a_2 + a_1 = n $，即 ( 2S + c = n )（( S ) 为左半部分和）。
• 分划长度为偶数 ( 2k )：无中心元素，左右各 ( k ) 个元素互为逆序，左部分是递归回文分划。分划表示为 $[a_1, a_2, \dots, a_k, a_k, \dots, a_2, a_1]$，即 ( 2S = n )（( S ) 为左半部分和）。

2. 状态转移方程

• 基础情况：( dp[1] = 2 )（分划 ( [1] ) 和 ( [1+1-1] ) ？不，实际 ( n=1 ) 只有一种分划 ( [1] )，但题目说明至少两种，可能题意中“所有1”的分划和自身分划，需注意 ( n=1 ) 时 ( dp[1]=2 )？需重新分析。
  • 更正：对于 ( n=1 )，分划只能是 ( [1] )，但题目中说明“至少两个”可能是指 ( n \geq 2 ) 的情况。根据样例，( n=4 ) 的输出为4，需正确推导。
• 动态转移：
  • 对于每个 ( n )，初始化为1（分划 ( [n] )）。
  • 枚举左半部分和 ( S )，其中 ( S ) 可以是任意正整数，且满足：
    • 对于奇数长度，( c = n - 2S \geq 1 )，此时左半部分和为 ( S )，对应分划数目为 ( dp[S] )（左半部分是递归回文分划）。
    • 对于偶数长度，( n = 2S )，左半部分和为 ( S )，分划数目为 ( dp[S] )。
  • 注意：左半部分的和 ( S ) 必须小于 ( n )，否则中心元素或右半部分无法存在。

实现步骤

1. 初始化：

   • 创建数组 ( dp )，其中 ( dp[i] ) 存储 ( i ) 的递归回文分划数目。
   • ( dp[1] = 2 )（分划 ( [1] ) 和 ( [1+1-1] ) 不成立，实际应为 ( dp[1] = 1 )，但根据题目描述，“至少两个”可能是指 ( n \geq 2 )，需根据样例调整。通过样例 ( n=4 ) 的输出为4，推导 ( dp[4] ) 的计算方式：
     • 分划包括 $[4], [1+2+1], [2+2], [1+1+1+1]$，共4种，故 ( dp[4] = 4 )。
     • 由此可知，( dp[n] ) 应包括所有可能的对称分划，其中左半部分递归回文。

2. 动态规划计算：

   • 对于 ( n ) 从1到最大输入值（如1000），依次计算 ( dp[n] )。
   • 对于每个 ( n )，初始 ( dp[n] = 1 )（分划自身）。
   • 枚举 ( s ) 从1到 ( n-1 )：
     • 若 ( n - 2s \geq 1 )（奇数情况），则 ( dp[n] += dp[s] )。
     • 若 ( n - 2s == 0 )（偶数情况），则 ( dp[n] += dp[s] )。
   • 注意：当 ( s = n ) 时，( 2s = 2n > n )，无需处理。

3. 处理样例：

   • ( n=4 )：
     • 奇数情况：( c = 4-2s \geq 1 )，即 ( s=1 ) 时 ( c=2 )，对应分划 ( [1,2,1] )，贡献 ( dp[1] = 2 )？不，实际 ( s=1 ) 的左半部分和为1，其递归回文分划数目为 ( dp[1]=2 )，但左半部分只能是 ( [1] )，故可能此处状态定义需调整为左半部分的和为 ( s )，且左半部分是递归回文分划，无论其分划方式如何。

正确动态规划定义

重新定义 ( dp[n] ) 为 ( n ) 的递归回文分划数目，满足：

• 分划可以是单个元素 ( [n] )（贡献1种）。
• 对于分划长度大于1的情况，分划可表示为 ( [A, c, A^R] )（奇数长度，( c ) 为中心元素，( A ) 是左半部分，( A^R ) 是逆序）或 ( [A, A^R] )（偶数长度），其中 ( A ) 是递归回文分划，且 ( A ) 的和为 ( s )，则 ( 2s + c = n )（奇数）或 ( 2s = n )（偶数）。

因此，状态转移方程为：
$ dp[n] = 1 + \sum_{s=1}^{\lfloor (n-1)/2 \rfloor} dp[s] + \sum_{s=1}^{\lfloor n/2 \rfloor} dp[s] $ 其中：

• 第一个1对应分划 ( [n] )。
• 第一个求和项对应奇数长度，( c = n-2s \geq 1 )，即 ( s \leq (n-1) /2 )。
• 第二个求和项对应偶数长度，( n=2s )，即 ( s \leq n/2 )。

但注意到当 ( n ) 为偶数时，偶数长度的情况中 ( s = n/2 ) 对应分划 ( [A, A^R] )，其中 ( A ) 的和为 ( s )，且 ( A ) 是递归回文分划。此时，( A ) 可以是任意递归回文分划，其和为 ( s )，因此贡献 ( dp[s] ) 种分划。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int n,i,f[1005],m;
	f[0]=1; f[1]=1;
	for(i=2;i<=1000;i++){
		f[i]=0;
		for(int j=0;j<=i/2;j++){
			f[i]+=f[j];
		}
	}
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++){
			scanf("%d",&m);
			printf("%d %d\n",i,f[m]);
		}
	}
	return 0;
}