【动态规划 | 数学】整数划分

把正整数n分成若干个正整数之和的方法数。

http://www.51nod.com/Challenge/Problem.html#problemId=1259

动态规划

答案是g[n]

const int MAXF = 1e3 + 10;
const int MAXG = 2e5 + 10;

int n;
ll f[MAXF], g[MAXG];

void calc() {
    f[1] = 1, f[2] = 2, f[3] = 5, f[4] = 7;
    for(int i = 5; i < MAXF; ++i)
        f[i] = ((3 + 2 * f[i - 2] - f[i - 4]) % MOD + MOD) % MOD;
    g[0] = 1;
    for(int i = 1; i <= MAXG; ++i) {
        for(int j = 1; f[j] <= i; ++j) {
            if((j + 1) >> 1 & 1)
                g[i] = (g[i] + g[i - f[j]]) % MOD;
            else
                g[i] = (g[i] - g[i - f[j]] + MOD) % MOD;
        }
    }
}

(O(nsqrt{n}))

生成函数

(O(nlog n))

易知整数划分的生成函数为

(F(x)=prodlimits_{i=1}^{n}frac{1}{1-x^i})

但是这个很难算，看到右边是乘积的形式，考虑两边取对数

(ln (F(x))=ln (prodlimits_{i=1}^{n}frac{1}{1-x^i}))
(=sumlimits_{i=1}^{n} lnfrac{1}{1-x^i})
(=-sumlimits_{i=1}^{n} ln(1-x^i))

考虑模 (x^n) 下的麦克劳林展开

[ln(1+x)=sumlimits_{i=0}^{n}(-1)^{i+1}frac{x^{n}}{n} ]

代入 (x:=-x^k)
(ln (F(x))=-sumlimits_{k=1}^{n} ln(1-x^k))
(=-sumlimits_{k=1}^{n} sumlimits_{i=1}^{n}(-1)^{i-1}frac{(-x^k)^{i}}{i})
(=sumlimits_{k=1}^{n} sumlimits_{i=1}^{n}frac{x^{ki}}{i})
(=sumlimits_{T=1}^{n} x^T sumlimits_{k=1}^{n} sumlimits_{i=1}^{n}frac{1}{i}[T=ki])
(=sumlimits_{T=1}^{n} x^T sumlimits_{k|T} frac{1}{k})

然后再取指数函数即可。

int n;
int A[MAXN], B[MAXN];

int calc(int n) {
    fill(B, B + n + 1, 0);
    for(int i = 1; i <= n; ++i) {
        int invi = qpow(i, MOD - 2);
        for(int j = i; j <= n; j += i)
            B[j] = qadd(B[j], invi);
    }
    polyexp(B, n + 1, A);
    return A[n];
}

可惜因为对多项式的操作，对模数有一定要求。正常版本是使用FNTT的，不能应对不存在原根的模数（如1e9+7）。

若干个不同正整数之和
http://www.51nod.com/Challenge/Problem.html#problemId=1201