回文拆分（palin）

题目描述

数的回文拆分从归纳角度定义：单个正整数 $A$ 是回文拆分；若 $A$ 是回文拆分，则 $A+A$ 以及 $A+x+A$ （ $x$ 为任意正整数）也是回文拆分。例如 $7$ 的回文拆分有 $7,\ 1+5+1,\ 2+3+2,\ 1+1+3+1+1,\ 3+1+3,\ 1+1+1+1+1+1+1$ 。给定正整数 $N$ （ $1 \leqslant N \leqslant 1000$ ），求它的回文拆分数 mod $10^9+7$ 。输入：一行一个正整数 $N$ 。输出：一行一个整数。

样例输入	样例输出
`4`	`4`
`20`	`60`

思路

按定义，值 $n$ 的拆分只有三类：基础型 $[n]$ 、A+A 型（ $n$ 偶数时贡献 $f(n/2)$ ）、A+x+A 型（贡献 $\sum_{a \leqslant (n-1)/2} f(a)$ ），用前缀和化简后得到 $f(2m)=f(2m+1)=F(m)$ ，求和项彻底消失。于是 $f(1)=1$ ，奇数项抄前一项 $f(2m+1)=f(2m)$ ，偶数项 $f(2m)=f(2m-1)+f(m)$ ，从 $2$ 到 $N$ 递推一遍、每步取模即可。样例验证： $f(4)=f(3)+f(2)=2+2=4$ ， $f(20)=f(19)+f(10)=46+14=60$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 19:07
# update_at: 2026-10-02 19:07

import sys

MOD = 1_000_000_007


def solve() -> None:
    """读入 N，输出 N 的回文拆分数 mod 1e9+7。"""
    n = int(sys.stdin.buffer.read())

    # f[k] = k 的回文拆分数。由归纳定义推出：f(1)=1，
    # 奇数与前一个偶数相等 f(2m+1)=f(2m)，偶数再叠上"两半相同"的 f(m)。
    f = [0, 1] + [0] * (n - 1)
    for k in range(2, n + 1):
        f[k] = (f[k - 1] + (f[k // 2] if k % 2 == 0 else 0)) % MOD

    print(f[n])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 22:16
 * update_at: 2026-10-04 22:16
 */
#include <cstdio>

typedef long long ll;

const ll MOD = 1e9 + 7;
const int MAXN = 1005;

ll f[MAXN]; // f[i] 表示值 i 的回文拆分数（mod 1e9+7）

int main() {
    ll n;
    scanf("%lld", &n);

    // 由归纳定义推出：
    // 基础型恒有 1 个，A+A 型贡献 f(n/2)（n 为偶数），
    // A+x+A 型贡献 sum_{a<=floor((n-1)/2)} f(a)，用前缀和化简后得
    // 关键恒等式 f(2m)=f(2m+1)=F(m)，等价于下面两条递推：
    // 奇数项抄前一项，偶数项 = 前一项 + 半值项。
    f[1] = 1;
    for (ll k = 2; k <= n; ++k) {
        if (k % 2 == 1)
            f[k] = f[k - 1];
        else
            f[k] = (f[k - 1] + f[k / 2]) % MOD;
    }

    printf("%lld\n", f[n]);
    return 0;
}