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

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

g(i,j,k)g(i,j,k)表示“每个位置有ii类元素可选,且序列中必须包含指定的jj类元素的,长度为kk的序列的个数”。形式化地讲,我们需要统计满足以下条件的序列的个数:p[1,k],apS (S=i);bTS (T=j),p[1,k],ap=b\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,,j0,1,2,\dots,jTT中的元素没有被包含在序列中的序列的个数,然后乘上容斥系数累加既是答案。也即: g(i,j,k)=x=0j(1)x(jx)(ix)kg(i,j,k)=\sum\limits_{x=0}^{j}(-1)^x\dbinom{j}{x}(i-x)^{k}。通俗地讲,我们在 jj 个元素中选择 xx 个,并强制使得它们不出现在序列中,其余元素任选。除去组合数的预处理时间,复杂度为O(j)\mathrm{O}(j)。参阅AtCoder ABC 194 F – Digits Paradise in Hexadecimal可以使用上述计算而非DP求解(虽然DP更加简洁直观)

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 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(i,j,k)的值,且三个参数值域都较小,每一次都暴力计算却又难以承受。考虑在相邻两项之间转移。我们考虑一个序列的最后一项填写什么,也即尝试从g(?,?,k)g(?,?,k)转移到g(?,?,k+1)g(?,?,k+1)。我们发现,最后一项有两种可能:一种是之前从未出现过的元素bb’,且有bT,bTb’ \in T’, b’ \notin T另一种则分两类,一类是元素aSa \in S另一类则是元素bTb \in T,但是bb之前出现在序列中。但这两类的元素归根结底都已经在转移前的ii种元素中出现过,无论填哪一个都无关紧要。因此对于第二种情况,我们容易想到,有g(i,j,k)i×g(i,j,k1)g(i,j,k)\leftarrow i\times g(i,j,k-1),也即“填写一个已经出现过的元素”。

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

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

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

例如,通过{b1,b2,b1,b2}\{b_1,b_2,b_1,b_2\},我们能够生成{b1,b2,b1,b2,b3}\{b_1,b_2,b_1,b_2,{\color{red}b_3}\}{b1,b3,b1,b3,b2}\{b_1,{\color{blue}b_3},b_1,{\color{blue}b_3},{\color{red}b_2}\}{b3,b2,b3,b2,b1}\{{\color{blue}b_3},b_2,{\color{blue}b_3},b_2,{\color{red}b_1}\}

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

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 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; } }
  • 2022年3月4日