划分数求法

roger_yrj · 2025-08-05 15:46:10 · 算法·理论

划分数是一个非常常见的问题。

给定一个整数 n，求有多少种划分方式。

如 4=3+1=2+1+1。

一、O(n^2) 算法

设把 i 划分成 j 个数有 f(i,j) 种分法。

1.完全背包

直接 DP 每个数字取了多少次

由于我们并不在意具体取了多少次，所以可以把 j 去掉。时间复杂度为 O(nk)。k 为数字种类数。

2.构造法

在构造法中，为了方便，我们允许划分出 0。f'(n+m,m)=f(n,m)

我们考虑一个划分序列可以怎么构造出来

1. 序列后面加一个 0。
2. 把序列所有数 +1。

容易证明，每个拆分序列都会被有且仅有一个构造方式构造出来

所以我们得到转移方程：

时间复杂度为 O(nm)。m 为拆分序列最大长度。

二、O(n\sqrt n) 算法

我们发现，当取的数字很多时，取的数字就很小；取的数字很大时，取的数字就很少。所以我们能不能结合以上两种算法呢？

我们取一个临界值 B。

我们考虑分开处理只取 [1,B) 的情况和只取 [B,n] 的情况。再把两边的答案拼在一起就是最终答案。

只选 [1,B) 时，取的数字很小，用背包的方法就能 O(nB) 求出答案。

只选 [B,n) 时，取的数字很少，不会超过 n/B 个，用构造法就能 O(\dfrac{n^2}{B}) 求出答案。

拼在一起是 O(n) 的，所以总的时间复杂度为 O(nB+\dfrac{n^2}{B})\ge O(n\sqrt n)，B=\sqrt(n)。

代码：

int B=sqrt(n);
f[0]=1;
for(int i=1;i<B;i++)
  for(int j=i;j<=n;j++)
    f[j]=(1ll*f[j]+f[j-i])%mod;
g[0]=1;
for(int i=1;i<=n/B;i++){
    for(int j=0;j<=n;j++){
        if(j>=i)g[j]=(1ll*g[j]+g[j-i])%mod;
        if(j+i*B<=n)ans=(1ll*ans+1ll*g[j]*f[n-(j+i*B)])%mod;
    }
}

注意代码中因为要省空间所以使用了滚动数组，数组 g 交换了两维。

还有一种方法是五边形数，可是我不会qwq。