[NOIP2001-普及]数的计数

题目描述

给定自然数 $n$ （ $1 \leqslant n \leqslant 1000$ ），按如下规则处理：不作任何处理；或在 $n$ 左边加上一个不超过 $n$ 一半的自然数，加上的数继续按同样规则处理，直到不能再产生新数。求整个过程中（包含 $n$ 本身）能得到的不同数的个数。例如 $n=6$ 时能得到 $6, 16, 26, 36, 126, 136$ 共 $6$ 个。

输入：一个自然数 $n$ 。输出：满足条件的数的个数。样例：输入 6，输出 6。

思路

设 $f(n)$ 为从 $n$ 出发（含 $n$ ）能得到的数的个数：在 $n$ 左边拼上 $m\ (1 \leqslant m \leqslant \lfloor n/2 \rfloor)$ 后的产物与从 $m$ 出发的产物一一对应（拼接结果位数可反解，单射），故 $f(n) = 1 + \sum_{m=1}^{\lfloor n/2 \rfloor} f(m)$ 。求和部分恰是 $f$ 的连续前缀和，随递推维护 $s_n = s_{n-1} + f(n)$ 即可 $O(n)$ 递推后查表回答。注意最大答案 $1981471878$ 超过 int 范围，需用 long long。

参考代码

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
28
29
30
31
32
33
34
35
36
37#!/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 03:50
# update_at: 2026-10-02 03:50

import sys

N = 1000  # 题面 n 的上界


def build_counts(limit: int) -> list[int]:
    """count[n] = n 经上述规则能生成的全部数的个数（含 n 自己）。

    直接按定义转移是 O(n^2) 的；注意 f(1..n/2) 恰好是 count 的连续前缀，
    所以用前缀和 sum_pre[m] = f(1)+...+f(m) 把转移降为 O(1)。
    """
    count = [0] * (limit + 1)      # f(n)：n 自己算一个生成的数
    sum_pre = [0] * (limit + 1)    # sum_pre[m] = f(1) + f(2) + ... + f(m)
    for n in range(1, limit + 1):
        # n 生成的数 = {n} ∪ {拼接(g, n) : g ∈ m 生成的数, 1<=m<=n/2}；位数可反解，单射不重
        count[n] = 1 + sum_pre[n // 2]
        sum_pre[n] = sum_pre[n - 1] + count[n]
    return count


count = build_counts(N)


def solve() -> None:
    n = int(sys.stdin.read())
    print(count[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/**
 * 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-06 12:16
 * update_at: 2026-10-06 12:16
 */

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 1005;

ll f[MAXN];  // f[i] 表示从 i 出发（含 i 本身）能得到的数的个数
ll s[MAXN];  // s[i] = f[1] + f[2] + ... + f[i]，即 f 的前缀和

int main() {
    int n;
    cin >> n;

    // 递推：f[i] = 1 + (1..i/2 每个数左边拼上 i 之后各自的产物数)
    // 即 f[i] = 1 + s[i/2]，再用前缀和把转移降到 O(1)
    f[0] = 0;
    s[0] = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = 1 + s[i / 2];
        s[i] = s[i - 1] + f[i];
    }

    cout << f[n] << endl;
    return 0;
}