【例4.6】数的计数(Noip2001)

题目描述

输入自然数 $n$ （ $n \leqslant 1000$ ）。可以反复在 $n$ 的左边添写一个不超过当前最左边那个数一半的自然数，直到不能再添为止；问包括 $n$ 本身在内一共能得到多少个数。输入一行 $n$ ，输出个数。样例输入 6，输出 6，对应 $6, 16, 26, 126, 36, 136$ 。

思路

设 $f(i)$ 表示从 $i$ 出发能生成的数的个数（含 $i$ 本身），则左边可补 $x \in [1, \lfloor i/2 \rfloor]$ ，即 $f(i) = 1 + \sum_{x=1}^{\lfloor i/2 \rfloor} f(x)$ 。把相邻两式相减，求和被消掉，得到 $f(i) = f(i-1)$ （ $i$ 为奇数）或 $f(i) = f(i-1) + f(i/2)$ （ $i$ 为偶数），边界 $f(0) = f(1) = 1$ ；从 $2$ 到 $n$ 顺序递推，时间 $O(n)$ 。

参考代码

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#!/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-09-30 04:54
# update_at: 2026-09-30 04:54

import sys


def count_forms(n: int) -> int:
    """返回自然数 n 按规则能生成的所有数的个数（含 n 本身）。

    记 f(i) 为 i 能生成的数的个数：i 本身算一个，再加上「左边补一个不超过 i/2 的
    数 x」得到的全部数，每个 x 贡献 f(x) 个，故 f(i) = 1 + sum(f(1..i//2))。
    与前一式作差：i 为奇数时 i//2 == (i-1)//2，不新增可用的前半段；
    i 为偶数时多出一项 f(i//2)，于是 f(i) = f(i-1) + (i 为偶数 ? f(i//2) : 0)。
    """
    f = [1] * (n + 1)                      # f[0] = f[1] = 1：0 和 1 都只能算自身
    for i in range(2, n + 1):
        f[i] = f[i - 1] + (f[i // 2] if i % 2 == 0 else 0)
    return f[n]


def solve() -> None:
    n = next(iter(map(int, sys.stdin.buffer.read().split())))
    print(count_forms(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/**
 * 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-05 09:11
 * update_at: 2026-10-05 09:11
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 1005; // n <= 1000，多开几个防止越界

ll f[MAXN]; // f[i]：从 i 出发能生成的不同数的个数（含 i 本身）

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

    // f[0] = f[1] = 1：0 和 1 左边都补不了正整数，只能算自己
    f[0] = 1;
    f[1] = 1;
    // 差分后的递推：奇数不变，偶数多出 f[i/2]
    for (ll i = 2; i <= n; i++) {
        if (i % 2 == 0) {
            f[i] = f[i - 1] + f[i / 2];
        } else {
            f[i] = f[i - 1];
        }
    }

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

【例4.6】数的计数(Noip2001)

目录

题目描述

思路

参考代码