题解：P11909 [NHSPC 2023] H. 整数的回文分解法

Error_Eric · 2025-03-18 11:36:03 · 题解

Statement

求有几个正整数回文串的和等于 n。

Sol

回文串可以被拆成左侧，中间，右侧三个部分。令 x, y, z 分别是这三个部分的和，特殊地，若回文串的长度是偶数，我们定义中间是 0。若长度是 1，我们定义 x = z = 0。那么 x + y + z = 2x + y = n。换言之 0\le2x\le n。只需要确定每个 x 的拆分方法数即可。

一个整数 p 的拆分方法数等于一个长度为 p 的序列拆分为若干个子区间的方法数。注意到除了第一个位置，每个位置都可以独立地选择是否和左边的位置放在同一个区间，因此方法数是 2^{p-1}。特殊地，根据题目定义，p=0 的答案是 1（对应不拆分的情况）。

因此答案就是 1+\sum_{x=0}^{\lfloor n/2\rfloor -1}2^x = 2^{\lfloor n/2\rfloor}。

Code

for _ in range(int(input())):
    print(pow(2, int(input()) // 2, int(1e9+7)))