划分数求法

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

给定一个整数

n

，求有多少种划分方式。

如

4=3+1=2+1+1

。

一、 $O(n^2)$ 算法

设把

i

划分成

j

个数有

f(i,j)

种分法。

1.完全背包

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

f(i,j)=f(i-k,j-1)

由于我们并不在意具体取了多少次，所以可以把

j

去掉。时间复杂度为

O(nk)

。

k

为数字种类数。

2.构造法

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

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

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

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

所以我们得到转移方程：

f(i,j)=f(i,j-1)+f(i-j,j)

时间复杂度为

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)

。

代码：

CPP

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。

文章操作

一、 $O(n^2)$ 算法

1.完全背包

2.构造法

二、 $O(n\sqrt n)$ 算法

代码：

相关推荐

评论

划分数求法

文章操作

一、O(n2)O(n^2)O(n2) 算法

1.完全背包

2.构造法

二、O(nn)O(n\sqrt n)O(nn​) 算法

代码：

相关推荐

评论

一、 $O(n^2)$ 算法

二、 $O(n\sqrt n)$ 算法