自然数拆分

AcWing-279-自然数拆分

分析

见《进阶指南》第278页。

完全背包求方案数。

实现

#include <iostream>
using namespace std;

typedef unsigned int UI;
const UI N = 4010, M = 2147483648;
int n;
UI f[N];

int main () {
    cin >> n;

    f[0] = 1;
    for (int i = 1; i <= n; ++ i) {
        int v = i;
        for (int j = v; j <= n; ++ j)
            f[j] = (f[j] + f[j - v]) % M;
    }
    cout << f[n] - 1 << endl;
    return 0;
}