「自然数拆分Lunatic版」自然数拆分

题目描述

给定自然数 $N$ ，把它拆成若干正整数之和，方案不考虑顺序、加数可重复，且至少拆成两个数。输入一个整数 $N$ ，输出方案数对 $2147483648$ 取模的结果。 $1 \le N \le 4000$ 。

样例输入 7，样例输出 14。

思路

把加数 $i$ 看成体积为 $i$ 的无限物品，背包容量为 $N$ ，统计恰好装满的方案数，即完全背包计数；一维数组正序更新 $f[j] += f[j-i]$ ，最后 $f[N]-1$ 去掉单加数方案 $N=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
32
33
34
35
36
37
38
39#!/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-01 20:22
# update_at: 2026-10-01 20:22

import sys

MOD = 1 << 31   # 题面模数 2147483648 = 2^31，不是常用的 1e9+7
MASK = MOD - 1  # 模数是 2 的幂，非负数下 & MASK 与 % MOD 等价，省掉内层的除法开销


def partitions(n: int) -> int:
    """把 n 无序拆成若干个正整数之和的方案数，加数可重复、至少两个。

    完全背包计数：加数 i 是体积为 i 且数量无限的物品，dp[j] 是和恰为 j 的方案数。
    """
    dp = [0] * (n + 1)
    dp[0] = 1                       # 空拆分：所有转移的起点

    # 外层 i = 本轮起允许使用的最大加数，答案按“最大加数”分层以避免顺序重复
    for i in range(1, n + 1):
        # 内层正序 → dp[j-i] 已含本轮结果，加数 i 可重复取，这是完全背包的标志
        for j in range(i, n + 1):
            dp[j] = (dp[j] + dp[j - i]) & MASK

    # dp[n] 里只有 1 个方案是单加数拆分 n = n，题面要求至少两个数，扣掉它
    return (dp[n] - 1) & MASK


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

typedef long long ll;

const int MAXN = 4005;           // N 最大 4000
const unsigned int MOD = 1u << 31; // 模数 2147483648 = 2^31

unsigned int f[MAXN];            // f[j] 表示凑出和 j 的方案数

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

    int n;
    if (!(cin >> n)) return 0;

    f[0] = 1;                      // 和为 0 只有空选一种方案
    for (int i = 1; i <= n; ++i) {   // 依次允许使用加数 i
        for (int j = i; j <= n; ++j) {
            // 完全背包：正序更新，f[j-i] 已包含可再用 i 的信息
            f[j] = (f[j] + f[j - i]) & (MOD - 1);
        }
    }

    // 减去不退化的单加数方案 N = N
    unsigned int ans = (f[n] + MOD - 1) & (MOD - 1);
    cout << ans << "\n";
    return 0;
}

「自然数拆分Lunatic版」 自然数拆分

目录

题目描述

思路

参考代码

「自然数拆分Lunatic版」自然数拆分