分拆数

1. 分拆数定义

正整数 $n$ 的一个分拆是将 $n$ 表示为若干正整数的无序和。分拆数 $p(n)$ 表示 $n$ 的不同分拆方式的数量。
示例：
$p(4) = 5$ ，因为 $4$ 的分拆为：
$4, \quad 3+1, \quad 2+2, \quad 2+1+1, \quad 1+1+1+1.$

2. 生成函数

分拆数的生成函数由欧拉给出：
$\sum_{n=0}^{\infty} p(n) x^n = \prod_{k=1}^{\infty} \frac{1}{1 - x^k},$
其中 $p(0) = 1$ 。

3. 递推公式（五边形数定理）

欧拉的五边形数定理导出递推关系：
$p(n) = \sum_{k \neq 0} (-1)^{k-1} p\left(n - \frac{k(3k-1)}{2}\right),$
求和对所有非零整数 $k$ （正负）进行，且当 $n < 0$ 时 $p(n) = 0$ 。
注： $\frac{k(3k-1)}{2}$ 是广义五边形数。

4. 渐近公式（Hardy-Ramanujan）

当 $n \to \infty$ 时，分拆数满足：
$p(n) \sim \frac{1}{4n\sqrt{3}} \exp\left(\pi \sqrt{\frac{2n}{3}}\right).$

5. 限制部分的分拆数

若要求分拆中每个部分不超过 $m$ ，其生成函数为：
$\sum_{n=0}^{\infty} p_{\le m}(n) x^n = \prod_{k=1}^{m} \frac{1}{1 - x^k}.$

6. 共轭分拆与Ferrers图

每个分拆对应一个Ferrers图，共轭分拆通过交换行和列得到。
示例：分拆 $4 = 3 + 1$ 的共轭为 $4 = 2 + 1 + 1$ 。

7. 其他变体

奇分拆：所有部分为奇数，生成函数：
$\prod_{k=1}^{\infty} \frac{1}{1 - x^{2k-1}}.$
不同部分分拆：各部分互不相同，生成函数：
$\prod_{k=1}^{\infty} (1 + x^k).$

例题

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

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int p[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,mod;
    cin>>n>>mod;
    p[0]=p[1]=1;
    for(int i=2;i<=n;i++){
        int k=1;
        while(1){
            int tmp=0;
            if((3*k*k+k)/2<=i) tmp=p[i-(3*k*k+k)/2]%mod;
            if((3*k*k-k)/2<=i) tmp=(tmp+p[i-(3*k*k-k)/2]%mod)%mod;
            if((3*k*k-k)/2>i) break;
            if(k&1) p[i]+=tmp%mod;
            else p[i]+=(mod-tmp%mod)%mod;
            p[i]=(p[i]%mod+mod)%mod;
            k++;
        }
        //cout<<p[i]<<'\n';
    }
    cout<<p[n]<<'\n';
    return 0;
}

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

分拆数

分拆数