递归

当 $m=1$ 时，显然只有全为 $1$ 的划分，$f(n,1) = 1$
当 $n=m$ 时，$n$ 的所有划分中包含 $n$ 的方案只有一种是${n}$，所以显然有 $f(n,n) = 1+f(n,n-1)$
当 $n < m$ 时，显然等价于 $f(n,n)$
当 $n > m$ 时，分划分元素中含 $m$ 和不含 $m$ 两种情况。含 $m$ ： ${m,{ x_1,x_2,…,x_k}}$ ，其中 $\sum x_i = n-m$ ，所以 ${ x_1,x_2,…,x_k}$ 是 $n-m$ 的 $m$ 划分，即 $f(n-m,m)$ . 不含$m$ ：此时 $f(n,m)=f(n,m-1)$ . 所以 $f(n,m)=f(n-m,m) + f(n,m-1)$ .

综上: $f(n,m)=\left \{\begin{array}{ll} {1} & {n=m=1} \\ {f(n,n)} & {n<m}\\ {1+f(n,n-1)} & {n=m} \\ {f(n-m,m) + f(n,m-1)} & {n>m>1} \end{array} \right.$ 所以有以下代码:

int f(int n, int m){
    if(n == 1 || m == 1) return 1;
    if(n < m) return f(n, n);
    if(n == m) return 1 + f(n, n-1);
    if(n > m) return f(n-m, m) + f(n, m-1);
}

记忆化减少递归重复运算

int dp[2005][2005];
int f(int n, int m){
    if(dp[n][m]) return dp[n][m];
    if(m == 1 || n == 1) return dp[n][m] = 1;
    if(n < m) return dp[n][m] = f(n, n);
    if(n == m) return dp[n][m] = 1 + f(n, n-1);
    if(n > m) return dp[n][m] = f(n-m, m) + f(n, m-1);
}

也可以修改成迭代方式 , 减少递归调用的常数

int F(int n, int m){
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i; j++) {
            if(j==1 || i==1) dp[i][j]=1;
            else {
                if(j == i) dp[i][j] = dp[i][j-1] + 1;
                else if(i-j < j) dp[i][j] = dp[i-j][i-j] + dp[i][j-1];
                else dp[i][j] = dp[i-j][j] + dp[i][j-1];
            }
        }
    return dp[n][m];
}

现在能解决 $n<5e3$ 量级的数据. 如果询问多次的话 , 采用记忆化方法也非常快 , 不过因为数组大小的限制 , 对于大数据还不可行 .

母函数法

母函数的具体定义和求法以后会补充。在此先针对本题看一下用法。

对于 $n$ 的一种划分，数字 $i$ 可能出现 $1$ ~ $k$ 次 $(k\leq \frac{n}{i})$，用 $x^i$ 代表数字 $i$ ，$x^{ik}$ 表示数字 $i$ 出现了 $k$ 次。

则所有的情况： $\begin{align*} G(x) &= (1+x+x^2+...+x^n)(1+x^2+x^4+...)...(1+x^n)\\ &= g(x,1)g(x,2)...g(x,n) \\ &= a_0 + a_1x+...+a_nx^n \end{align*}$

其中 $g(x,i)$ 表示数字 $i$ 在划分中出现次数的所有可能情况。因为 $x^ax^b = x^{a+b}$ 所以 $x^i$ 就代表了数字 $i$ 的划分，系数 $a_i$ 就是数字 $i$ 的划分种类数。那么 $f(n,n) = a_n$ 。

现在的问题转化成求多项式系数问题，$n$ 个多项式相乘，朴素做法 $O(n^3)$ ，FFT $O(n^2logn)$ 。

在此仅给出朴素做法，单次处理 $O(n^3) $ ，询问 $O(1)$ ：

int c1[maxn], c2[maxn];
int F(int n){
    for(int i=0; i<=n; i++) c1[i] = 1, c2[i] = 0;
    for(int i=2; i<=n; i++) {
        for(int j=0; j<=n; j++) for(int k=0; k+j<=n; k+=i)
            c2[k+j] = (c2[k+j] + c1[j]) % mod;
        for(int j=0; j<=n; j++) c1[j] = c2[j], c2[j] = 0;
    }
    return c1[n];
}

五边形数定理

第 $n$ 个五边形数：$f(n) = \frac{n(3n-1)}{2}$ ，即序列为：1, 5, 12, 22, 35, 51, 70, …

五边形数的生成函数： $g(x) = \frac{x(2x+1)}{(1-x)^3} = x+5x^2+12x^3+22x^4+...$ 欧拉函数的展开式： $\prod_{n=1}^{\infty}(1-x^n) = \prod_{k=-\infty}^{\infty}(-1)^kx^{\frac{k(3k-1)}{2}} = \prod_{k=0}^{\infty}(-1)^kx^{\frac{k(3k\mp1)}{2}}$ 即 $(1-x)(1-x^2)(1-x^3)...=1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}+...$ 留下来的次方恰为广义五边形数。

欧拉函数的倒数是分割函数的母函数，即： $\frac{1}{\varphi(x)} = \sum_{i=0}^{\infty}p(k)x^k \quad\quad p(k) = f(k,k)$ 将上式带入： $(1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}+...)(1+p(1)x+p(2)x^2+...) = 1$ 在 n>0 时，等式右侧的系数均为0，比较等式二侧的系数，可得 $p(n)-p(n-1)-p(n-2)+p(n-5)+p(n-7)+...=0$ 因此得到求 $p(n)$ 递归式 $p(n) = p(n-1)+p(n-2)-p(n-5)-p(n-7)+...$ 代码 $O(n\sqrt{n})$ ：

int p[maxn], a[maxn<<1];
int F(int n){
    // 预处理计算广义五边形数
    for(int i=0; i<maxn; i++) a[i<<1] = i*(3*i-1)/2, a[i<<1|1] = i*(3*i+1)/2;
    p[0] = p[1] = 1; p[2] = 2;
    for(int i=3; i<=n; i++) {
        int k = 0, f;
        for(int j=2; a[j]<=i; j++){
            f = k&2;
            if(!f) p[i] = (p[i] + p[i-a[j]] + mod) % mod;
            else p[i] = (p[i] - p[i-a[j]] + mod) % mod;
            k ++; k %= 8;
        }
    }
    return p[n];
}

参考网站

整数拆分问题的四种解法

百度词条：整数拆分

wiki：整数拆分