整数划分问题

众所周知,整数划分问题是一类计算将正整数 $n$ 无序拆分成若干可相同的正整数之和的划分数的问题,存在一类普适性的 DP 解法以及针对划分数问题的五边形数定理……

先来看一道小学奥数题。

给出 $n$ 个小球和 $m$ 个盒子,分别计算在以下情况中,将小球放入盒子(盒子不能是空)的方案数:

  1. 小球和盒子都有标号
  2. 小球有标号,盒子无标号
  3. 小球无标号,盒子有标号
  4. 小球和盒子都没有标号

显然,问题 1 可以通过简单容斥来求,即我们钦点有 $k$ 个盒子是空的,得到答案是 $\sum\limits_{k=0}^m (-1)^k \dbinom{m}{k} (m-k)^n$。注意到这本质上是第二类斯特林数乘上盒子数的阶乘(见通项公式),即 $m!\begin{Bmatrix}n\newline m \end{Bmatrix}$。

对于问题 2 ,这显然是第二类斯特林数 $\begin{Bmatrix}n\newline m \end{Bmatrix}$ 的定义(组合意义?)。

对于问题 3,因为小球不可区分,所以我们考虑插板。因为盒子不空,所以答案是 $\dbinom{n-1}{m-1}$。

至此前三个问题都在 $O(nm)$ 的时间内解决掉了,但是第四个问题呢?显然我们不能直接对 3 除一个 $m!$ 了事,一个最明显的反例就是得到的结果甚至不一定是整数!

我们考虑 DP。

整数划分 DP

问题 4 可以被如下转化:

给定正整数 $n$ ,求将 $n$ 分解为 $m$ 个正整数之和的方案数。两种方案不同当且仅当 $m$ 个正整数构成的集合不相同。
$n, m\le 5000$

设 $f[i,k]$ 为考虑将 $i$ 划成 $k$ 个正整数的方案数。对于当前的状态,我们可以将其划成两种情况:

  1. 当前划分包含数字 1,方案是 $f[i-1,k-1]$
  2. 当前划分不含数字 1,考虑对划分出的每个数字减 1,方案数不变,得到方案数是 $f[i-k,k]$

因此转移:
$$ f[i,k]=f[i-1,k-1]+f[i - k, k] $$ 时间复杂度 $O(nm)$。

代码:

1
2
3
4
memset(f, 0, sizeof(f)), f[0][0] = 1;
for(int j = 1; j <= n; j++)
for(int i = j; i <= n; i++)
f[i][j] = f[i - 1][j - 1] + f[i - j][j];

一个变形

考虑这样一个问题:

给定正整数 $n$ ,求将 $n$ 分解为若干个正整数之和的方案数。两种方案不同当且仅当划分出的正整数构成的集合不相同。
$Subtask1, n \le 5000$
$Subtask2,n\le 10^5$

  • Subtask1

考虑 DP,注意到这本质上就是一个完全背包计数:有 $n$ 个物品 $1,2,…,n$,选出一些让和为 $n$,物品可以取多次。然后就可以 $O(n^2)$ 快乐DP了,代码略。

  • Subtask2

注意到我们有两种求划分数的 DP:第一类状态设计为 $f[i,k]$ 考虑将 $i$ 划成 $k$ 个正整数的方案数,复杂度是 $O(nk)$,即划分个数乘上划分值域;第二类是完全背包计数,复杂度是 $O(nV)$,即元素个数乘上划分值域。

考虑复杂度均摊,设阈值 $B$,我们把能用的数字划分为 $[1,B]$ 和 $[B+1,n]$ 两部分。第一部分一共有 $B$ 个能用的数字,跑完全背包计数,复杂度 $O(nB)$;第二部分不会选择超过 $\frac{n}{B}$ 个,跑第一种 DP,复杂度 $O(\frac{n^2}{B})$。最后可以模拟卷积合并 DP 结果,取 $B = \lceil\sqrt{n}\rceil$,总复杂度 $O(n\sqrt{n})$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int x, y, n, P, f[CN], g[CN][400];
int add(int a, int b) {return a + b >= P ? a + b - P : a + b;}
int work(){
int B = ceil(sqrt(n));
memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g));
f[0] = 1;
for(int i = m; i <= B; i++) for(int j = i; j <= n; j++)
f[j] = add(f[j], f[j - i]);
g[0][0] = 1;
for(int i = 1; i <= n; i++) for(int j = 1; j <= min(B, i); j++)
g[i][j] = add(g[i - 1][j - 1], g[i - j][j]);
int ans = 0;
for(int i = 1; i <= n; i++) for(int j = 1; j <= min(B, i); j++)
if(i + j * B <= n) // 每个数都 +B
g[i + j * B][0] = add(g[i + j * B][0], g[i][j]);
for(int i = 0; i <= n; i++) // 合并状态
ans = add(ans, 1ll * f[i] * g[n - i][0] % P);
return ans;
}

实际上这个问题是一类经典问题,被称作整数拆分问题,另一种解法是五边形数定理。

五边形数定理

  • 五边形数
    形如 $p_n = p_{n-1}+3n-2$ 的数字被称作是五边形数,通项是 $p_n=\dfrac{n(3n-1)}{2}$。

五边形数定理指出:
$$ \phi(x) = \prod\limits_{k\ge 1}(1-x^k)=\sum\limits_{k=-\infty}^{+\infty}(-1)^kx^{p_k} $$ 其中 $p_k$ 是五边形数。
设 $f_n$ 为 $n$ 的拆分数,$F(x)$ 是 $f_n$ 的 OGF,有:
$$ F(x)=1/\phi(x) $$ 即:
$$ (1-x-x^2+x^5+x^7-…)(1+f_1x+f_2x^2+f_3x^3+…)=1 $$ 比较系数得:
$$\begin{aligned} &f_n-f_{n-1}-f_{n-2}+f_{n-5}+f_{n-7}-…=0 \newline \Leftrightarrow &f_n=f_{n-1}+f_{n-2}-f_{n-5}-f_{n-7}\end{aligned}$$ 其中数列 $1,2,5,7,12,15,…$ 对应广义五边形数 $p_1,p_{-1},p_2,p_{-2},…$。

然后我们就可以愉快的递推 $f[]$ 了,可以证明这样做的复杂度为 $O(n\sqrt{n})$。

代码:

1
2
3
4
5
6
7
8
9
10
int add(int a, int b) {return a + b >= P ? a + b - P : a + b;}
int p(int x) {return x * (3 * x - 1) / 2;}
memset(f, 0, sizeof(f)), f[0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; ;j++){
int k = p(j); if(k > i) break;
f[i] = add(f[i], j & 1 ? f[i - k] : P - f[i - k]);
k = p(-j); if(k > i) break;
f[i] = add(f[i], j & 1 ? f[i - k] : P - f[i - k]);
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×