分拆数

定义

把正整数分解成若干正整数的和

定理

① N拆分成不同整数的和的拆分数(不允许重复) 等于 N拆分成奇数的拆分数(允许重复)

② N拆分成一些重复次数不超过 k 次的整数的和的拆分数等于 N拆分成不被 k+1 整除的数的和的拆分数

③ N拆分成k个数的和的拆分数等于 N拆分成最大数为k的拆分数

④ N拆分成最多不超过k个数的和的拆分数等于 N拆分成最大数不超过k的拆分数

⑤ N拆分成不超过k个数的和的拆分数等于 N+k拆分成恰好k个数的拆分数

可重复的整数拆分

模版

暴力 $O(n^2)$五边形数定理 $O(n*\sqrt n)$ 模数任意多项式求解 $O(n*\log n)$

C++
dp[0] = 1;
for (int i = 1 ; i <= n ; i++) {
    for (int j = i ; j <= n ; j++) {
        dp[j] += dp[j - i];
    }
}

C++
i64 ans[100005], temp[100005];
int main() {
    int n, P;
    cin >> n >> P;
    int sqr = sqrt(n);
    ans[0] = temp[0] = 1;
    for (int i = 1 ; i <= sqr ; i++) {
        for (int k = 0 ; k < 2 ; k++) {
            for (int j = i ; j <= n - i * i ; j++) {
                temp[j] = (temp[j] + temp[j - i]) % P;
            }
        }
        for (int j = i * i ; j <= n ; j++) {
            ans[j] = (ans[j] + temp[j - i * i]) % P;
        }
    }
    cout << ans[n] << "\n";
    return 0;
}

将 $n$ 拆成 $m$ 个正整数

C++
{ 多项式基础模版 }
int n, m;
cin >> n >> m;
cout << other::Partition(n, m);

例题

#6268. 分拆数 - LibreOJ

P6189 [NOI Online #1 入门组] 跑步 - 洛谷

k部分拆数

将 $n$ 分成恰有 $k$ 个部分的分拆，成为 $k$ 部分拆数，记作 $P(n,k)$ $$ P(n,k)=\sum_{j=0}^kP(n-k,j) $$

\[ P(n,k)=P(n-1,k-1)+P(n-k,k) \]

暴力递推 $O(n*k)$

C++
P[0][0] = 1;
for (int i = 1 ; i <= n ; i++) {
    for (int j = 1 ; j <= k ; j++) {
        if (i >= j) {
            P[i][j] = P[i - j][j] + P[i - 1][j - 1];
        }
    }
}

互异拆分数

$pd_n$ ，自然数 $n$ 的各部分互不相同的分拆方法数。

暴力 $O(\sqrt{n*k})$

C++
int n;
cin >> n;
PD[0][0] = 1;
int ans = 0;
int mx = sqrt(n) + 100;
for (int j = 1 ; j < mx ; j++) {
    for (int i = 0 ; i < mx ; i++) {
        PD[i][j & 1] = 0;
    }
    for (int i = 0 ; i <= n ; i++) {
        if (i >= j) {
            PD[i][j & 1] = PD[i - j][j & 1] + PD[i - j][(j - 1) & 1];
        }
    }
    ans += PD[n][j & 1];
}

奇拆分数

$po_n$，自然数 $n$ 各部分都是奇数的分拆方法数。 $$ po_n=pd_n $$ $pde_n$，自然数 $n$ 各部分都是偶数的互异分拆方法数。

$pdo_n$，自然数 $n$ 各部分都是奇数的互异分拆方法数。 $$ pd_n=pde_n+pdo_n $$