随记 – 三月四日 – DP求解强制包含部分元素的序列计数问题

被这玩意卡了一上午——前天CSP-S模拟的T4需要用到这类问题的转移。为什么题解TMD是错的？

即$g(i,j,k)$表示“每个位置有$i$类元素可选，且序列中必须包含指定的$j$类元素的，长度为$k$的序列的个数”。形式化地讲，我们需要统计满足以下条件的序列的个数：$\forall p \in [1,k], a_p \in S\space(|S|=i); \forall b \in T \subseteq S\space(|T|=j), \exists p \in [1,k], a_p=b$。

通过容斥原理，我们可以计算出至少有$0,1,2,\dots,j$个$T$中的元素没有被包含在序列中的序列的个数，然后乘上容斥系数累加既是答案。也即： $$g(i,j,k)=\sum\limits_{x=0}^{j}(-1)^x\dbinom{j}{x}(i-x)^{k}$$。通俗地讲，我们在 $j$ 个元素中选择 $x$ 个，并强制使得它们不出现在序列中，其余元素任选。除去组合数的预处理时间，复杂度为$\mathrm{O}(j)$。参阅AtCoder ABC 194 F – Digits Paradise in Hexadecimal，可以使用上述计算而非DP求解（虽然DP更加简洁直观）。

1
2
3
4
5
6
7
8
from math import *
def C (x, y):
    return 0 if x < y else factorial(x)//factorial(y)//factorial(x-y)
def calc (i, j, k):
    res = 0
    for x in range (0, j + 1):
        res += ((-1)**x) * C(j,x) * ((i-x)**k)
    return res

但一些题目需要计算大量$g(i,j,k)$的值，且三个参数值域都较小，每一次都暴力计算却又难以承受。考虑在相邻两项之间转移。我们考虑一个序列的最后一项填写什么，也即尝试从$g(?,?,k)$转移到$g(?,?,k+1)$。我们发现，最后一项有两种可能：一种是之前从未出现过的元素$b’$，且有$b’ \in T’, b’ \notin T$；另一种则分两类，一类是元素$a \in S$，另一类则是元素$b \in T$，但是$b$之前出现在序列中。但这两类的元素归根结底都已经在转移前的$i$种元素中出现过，无论填哪一个都无关紧要。因此对于第二种情况，我们容易想到，有$g(i,j,k)\leftarrow i\times g(i,j,k-1)$，也即“填写一个已经出现过的元素”。

我们重点讨论的是第一类情况。似乎非常容易想到，“新出现的元素$b_{j+1}$在之前的序列中都没有在$S,T$出现过，直接使用$g(i-1,j-1,k-1)$转移就可以了”。这是错误的。我们总是考虑$b_1,b_2,\dots,b_j$已经出现在原来的序列中，现在顺次加入$b_{j+1}$，则它在序列中的首次出现总是在$b_{1\dots j}$之后。考虑以下序列：$j=2,\{a_1,b_1,b_2,a_1,b_1,{\color{red}b_3}\}$，无论如何$b_3$都没有在$b_{1,2}$之前出现，但实际上我们还需要统计这样的序列：$\{a_1,b_1,{\color{red}b_3},a_1,b_1,{\color{blue}b_2}\}$，这在刚才的转移中绝无可能出现。同时，又由于我们是顺次考虑包含前$j$个$b$元素，所以不会出现“DP转移时$b_3$在$b_2$之前被考虑”。得想个办法才行。

“交换”是一个不错的想法。确切地来说，由于现在强制包含$b_{1\dots j+1}$，所以它们的顺序可以由我们随意安排。但我们总不可能把这至少$j+1$个元素的位置全部拎出来遍历一遍——耗时将是灾难性的。一个不那么直观的想法，就是选择一个$p \in [1,j]$，让$b_p$“提到最后一位上”且只在第$k$位出现（这是第一类情况本身的硬性要求，否则会包含在第二种情况的转移里），同时让$b_{j+1}$替换先前所有出现的$b_p$。说白了，就是从$j+1$个$b$元素中挑一个孤儿放到最后，其他$j$个元素的安排不变。

考虑它是否正确。考虑这$j+1$个$b$元素在序列中的分布。如果最后出现的元素出现了不止一次，则会在第二种转移中涉及；反之，我们考虑$T$中最开始出现的$j$个元素中编号最大的那个。如果它是$b_j$，说明$b_{j+1}$确实是顺次添加到序列末尾的，也就是错误的第一种转移唯一包含的情况；反之，我们截取这个序列中前$k$个元素，显然它缺少了某个$b_{1\dots j}$中元素的恰好一个，设其为$b_q$。如果我们将$b_{j+1}$全部替换成$b_q$，则可以确定一种唯一的包含在$g(i,j,k)$的序列，它包含$b_{1\dots j}$；而我们正在考虑的原始序列，也唯一包含在$g(i+1,j+1,k+1)$中。显然，没有其他任何方式能够再由同一位置、同一替换元素生成这两个序列。我们建立了一种从$g(i+1,j+1,k+1)$中末尾唯一序列到$g(i,j,k)$所有元素的映射，有$j+1$个序列会对应到每个$g(i,j,k)$序列上。所以原式成立。

例如，通过$\{b_1,b_2,b_1,b_2\}$，我们能够生成$\{b_1,b_2,b_1,b_2,{\color{red}b_3}\}$，$\{b_1,{\color{blue}b_3},b_1,{\color{blue}b_3},{\color{red}b_2}\}$，$\{{\color{blue}b_3},b_2,{\color{blue}b_3},b_2,{\color{red}b_1}\}$。

时间复杂度$\mathrm{O}(n^3)$。

1
2
3
4
5
6
7
8
9
10
11
void calc_g () {
	for (int i = 0; i <= n; ++i)
		g[i][0][0] = 1;
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k < n; ++k) {
				if (i < n && j < n)
					(g[i + 1][j + 1][k + 1] += (j + 1ll) * g[i][j][k] % P) %= P;
				(g[i][j][k + 1] += i * g[i][j][k] % P) %= P;
			}
}