题目链接：hdu4651 Partition

动规做法

设 f[n][m] 为 n 个球放到 m 个盒子里的方案数。则 n 的整数拆分方案等于 f[n][n]。

• 如果只有一个盘子或者没有小球，方案数自然为 1
• 如果小球比盒子要少，小球肯定是放不满盒子的，由于盒子相同，可以得到转移 f[i][j]=f[i][i]
  如果小球比盒子要多，就分为将盘子放满和没放满两种情况，即 f[i][j]=f[i-j][j]+f[i][j-1]

for (int i = 0; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j == 1 || i == 0) f[i][j] = 1;
            else if (i < j) f[i][j] = f[i][i];
            else f[i][j] = f[i - j][j] + f[i][j - 1];
        }
    }

五边形数

五边形数：$1,5,12,22,35,51,70,…$

f(n)=\frac{n(3n-1)}{2}

广义五边形数：

f(0),f(1),f(-1),f(2),f(-2),…：即0,1,2,5,7,12,…

定义欧拉函数：

\varphi(x)=\prod_{n=1}^{\infty}(1-x^n)

五边形数定理：

\begin{aligned}
\varphi(x)&=(1-x)(1-x^2)(1-x^3)…\cr
&=1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}-…
\end{aligned}

展开后留下来的次方项恰为广义五边形数，且由奇数生成的五边形数次方项系数为 -1、偶数生成的次方项系数为 1.

考虑整数拆分的生成函数：

\prod_{i=1}^{\infty}\left(\sum_{j=0}^{\infty}x^{ij}\right)=\frac{1}{\varphi(x)}

(1-x-x^2+x^5+x^7-x^{12}-x^{15}+…)(1+p_1x+p_2x^2+p_3x^3+\cdots)=1

p_n=p_{n-1}+p_{n-2}-p_{n-5}-p_{n-7}+p_{n-12}+\cdots

利用多项式求逆

// 多项式求逆模版见前面
// 直接递推出广义五边形数再对其生成函数求逆
void init() {
    for(int i = 1; ; i > 0 ? i = -i : i = -(--i)) {
        int now = i * (3 * i - 1) / 2;
        if (now > n) break;
        f[++tot] = now;
    }
    a.resize(n+1);
    for (int i = 0; i <= tot; i++) {
        if (i % 4 == 1 || i % 4 == 2) a[f[i]] = Mo - 1;
        else a[f[i]] = 1;
    }
    a = inverse(a);
}
int main() {
    scanf("%d", &n); init();
    for (int i = 1; i <= n; i++) printf("%d\n", a[i]);
    return 0;
}

dp预处理五边形数

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;;
const int N = 1e5 + 50;
int n;
long long ans[N], tmp[N];
void init() {
    int t = 1000;
    for(int i = -1000; i <= 1000; i++) tmp[i + t] = i * (3 * i - 1) / 2;
    ans[0] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 1; j <= i; j++) {
            if (tmp[j + t] <= i) {
                if (j & 1) ans[i] += ans[i - tmp[j + t]];
                else ans[i] -= ans[i - tmp[j + t]];
            }
            else break;
            if (tmp[t - j] <= i) {
                if(j&1) ans[i] += ans[i - tmp[t - j]];
                else ans[i] -= ans[i - tmp[t - j]];
            }
            else break;
        }
        ans[i] = (ans[i] % P + P) % P;
    }
}

int main() {
    scanf("%d", &n); init();
    for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
    return 0;
}

变式

题目：hdu4658

题目大意：

求自然数的整数拆分个数，每个数使用次数不能大于等于 k 次。

\begin{aligned}
F(x)&=\prod_{i=1}^{\infty}\left(\sum_{j=0}^{k-1}x^{ij}\right)\cr
&=\prod_{i=1}^{\infty}\left(\frac{1-x^{ik}}{1-x^i}\right)\cr
&=\frac{\varphi(x^k)}{\varphi(x)}=\varphi(x^k)P(x)\cr
\end{aligned}

\varphi(x^k)=1-x^k-x^{2k}+x^{5k}+x^{7k}-x^{12k}-x^{15k}+\cdots

\therefore F(x)=(1-x^k-x^{2k}+x^{5k}+x^{7k}-x^{12k}-x^{15k}+…)(p_0+p_1x+p_2x^2+p_3x^3+\cdots)

F_n=p_n-p_{n-k}-p_{n-2k}+p_{n-5k}+\cdots

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
const int N = 1e5 + 50;
int T, n, k;
long long ans[N], tmp[N];
void init() {
    int t = 1000;
    for(int i = -1000; i <= 1000; i++) tmp[i + t] = i * (3 * i - 1) / 2;
    ans[0] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 1; j <= i; j++) {
            if (tmp[j + t] <= i) {
                if (j & 1) ans[i] += ans[i - tmp[j + t]];
                else ans[i] -= ans[i - tmp[j + t]];
            }
            else break;
            if (tmp[t - j] <= i) {
                if(j&1) ans[i] += ans[i - tmp[t - j]];
                else ans[i] -= ans[i - tmp[t - j]];
            }
            else break;
        }
        ans[i] = (ans[i] % P + P) % P;
    }
}

long long solve(int n, int k) {
    long long ret = ans[n];
    int t = 1000;
    for (int j = 1; ; j++) {
        if (k * tmp[j + t] <= n) {
            if (j & 1) ret -= ans[n - k * tmp[j + t]];
            else ret += ans[n - k * tmp[j + t]];
        }
        else break;
        if (k * tmp[t - j] <= n) {
            if (j & 1) ret -= ans[n - k * tmp[t - j]];
            else ret += ans[n - k * tmp[t - j]];
        }
        else break;
    }
    return ((ret % P) + P) % P;
}

int main() {
    init();
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        printf("%lld\n", solve(n, k));
    }
    return 0;
}