[NOIP2001 普及组] 数的计算(改)

题目描述

给定正整数 $n$ 。合法数列定义：仅含 $n$ 的数列合法；在合法数列末尾追加一个正整数 $y$ ，要求 $y$ 不超过末项的一半，得到的新数列仍合法。求合法数列总数，结果只保留最低 $5$ 位（不足 $5$ 位直接输出）。 $1 \leqslant n \leqslant 10^5$ 。

输入一行一个整数 $n$ ；输出一行一个整数表示答案。

样例输入：6，样例输出：6。

思路

设 $f(i)$ 表示首项为 $i$ 的合法数列个数，则 $f(i)=1+\sum_{j=1}^{\lfloor i/2\rfloor}f(j)$ ，其中 $1$ 对应数列 $[i]$ 自身。用前缀和 $s(i)=s(i-1)+f(i)$ 把求和变成 $s(\lfloor i/2\rfloor)$ ，递推即可。答案对 $100000$ 取模。

参考代码

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"""[NOIP2001 普及组] 数的计算(改) —— 前缀和优化线性 DP。

设 f[i] = 首项为 i 的合法数列个数，s[i] = f[1]+...+f[i]。
数列 [i] 本身合法；其后每一段都是首项 j∈[1, i//2] 的合法数列前拼 i，
故 f[i] = 1 + s[i//2]，前缀和数组把转移压到 O(1)。
答案对 100000 取模（题目只保留 5 位）。总复杂度 O(n)。
"""
import sys


def main() -> None:
    n: int = int(sys.stdin.read())
    mod: int = 100000
    f: list[int] = [0] * (n + 1)   # f[i]：首项为 i 的合法数列个数
    s: list[int] = [0] * (n + 1)   # s[i]：f[1..i] 的前缀和（已取模）
    f[1] = s[1] = 1
    for i in range(2, n + 1):
        f[i] = (s[i // 2] + 1) % mod          # 1 表示数列 [i] 自身
        s[i] = (s[i - 1] + f[i]) % mod
    print(f[n])


if __name__ == "__main__":
    main()

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-06 16:42
 * update_at: 2026-10-06 16:43
 */
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

const ll MOD = 100000; // 结果只保留最低 5 位

ll n;
ll f[100005]; // f[i] 表示首项为 i 的合法数列个数
ll s[100005]; // s[i] 表示 f[1..i] 的前缀和

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    f[1] = 1; // 数列 [1] 自身合法
    s[1] = 1;
    for (ll i = 2; i <= n; i++) {
        // 数列 [i] 自身贡献 1；后面可以接首项为 1..i/2 的任意合法数列
        f[i] = (1 + s[i / 2]) % MOD;
        s[i] = (s[i - 1] + f[i]) % MOD;
    }

    cout << f[n] << "\n";
    return 0;
}

[NOIP2001 普及组] 数的计算(改)

目录

题目描述

思路

参考代码