跳至正文

1 条题解

  • 0
    @ 2026-10-8 19:19:22

    【本题解由站长编写】

    把 n 划分成若干个正整数之和的方案数,顺序不同算同一种。整数划分 DP 必须用完全背包(硬币交换)写法:外层枚举「份数 j」从 1 到 n,内层正序枚举「总和 i」从 j 到 n,有 dp[i] += dp[i-j]。⚠️ 循环顺序不能反——若外层枚举金额、内层枚举份数,算出来的是有序组合数(n=77 会得到 7.7×10^22 量级),而不是不区分顺序的划分。⚠️ 评测把「只有它自己」也算一种:n=77 期望 10619863,而纯 ≥2 项的划分是 10619862,恰好差 1,所以不要减 1。n≤100 时 p(100)=190569292 仍超 int32,必须用 long long。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        int n;
        cin >> n;
        vector<long long> dp(n + 1, 0);
        dp[0] = 1;
        // 完全背包写法:外层份数,内层正序枚举总额
        for (int j = 1; j <= n; j++)
            for (int i = j; i <= n; i++)
                dp[i] += dp[i - j];
        cout << dp[n] << endl;   // 不减 1:评测把只有自身那一种也算进去
        return 0;
    }
    
    • 1

    信息

    ID
    4184
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者