P11030 『DABOI Round 1』Blessings Repeated 题解

chenxi2009 · 2024-09-11 15:32:07 · 题解

Upd 2024.11.26：压行改进码风

专栏沉浸式阅读

闲话：怎么这么多写矩阵乘法的呢？那就让我来给一个通俗的写法吧…

这是一篇保姆级的简单题解。

前置知识：组合数学，一点动态规划思想，搜索，乘法逆元

思路

令 n=\vert S\vert,m=\vert T\vert。\ 首先我们可以在 O(nm) 的时间内求出 S 的子序列中等于 T 的序列数量。

如果你不想思考，这里有思考过程：

令 f_{i,j} 为 S_{1\cdots i} 的子序列中等于 T_{1\cdots j} 的序列数量。\ 易得递推：

复杂度 O(n^2m)。

令

易得新的递推式：

复杂度 O(nm)。\ 第二重循环倒序可以压掉第一维。空间复杂度 O(m)。

继续正文

用这个方法，我们可以得出 T 的所有子串在 S 里面对应的子序列个数，复杂度为 O(nm^3)。

这个时候，我们已经离答案非常接近了。\ 因为我们发现对于每一个重复 k 次的 S 构成的字符串里等同于 T 的子序列，都是由把 T 分成若干个子串，在不同位置的 S 中取了分别等同于各个子串的子序列构成的。

样例理解

以题目样例 #1 为例：

2
stocyhorz
cyh

我们可以把 T 分成一个子串 T_{1,2,3}，在第一个 S 中取该子串和在第二个 S 中取该子串，有 2 种方案；\ 我们可以把 T 分成两个子串 T_{1,2},T_3，即 cy 与 h，在第一个 S 中取第一个子串，第二个 S 中取第二个子串，有 1 种方案；\ 我们可以把 T 分成两个子串 T_1,T_{2,3}，即 c 与 yh，在第一个 S 里面取第一个子串，第二个 S 中取第二个子串，有 1 种方案；\ 我们可以把 T 分成三个子串，但是我们没有足够的 S 去分配三个子串，因而没有方案。\ 综上所述，共有 4 种方案。

以题目输出 #2 为例：

4
c
ccc

唯一有方案的分割方式是把 T=ccc 分割成三个子串 c，分配给 k= 4 个 S=c，有 4 种方案。

如果你还没有想到正解？

从最小的问题开始思考：

不妨先假定我们已经确定了一种分配方案，将 T 分割为了 p 个子串 T_{1\cdots r_1},T_{r_1+1\cdots r_2}\cdots T_{r_{p-1}+1\cdots m}。

令 h_{l,r} 为先前我们所计算的，一个 S 中等同于 T_{l\cdots r} 的子序列个数。

对于选好了 p 个不同位置上的 S，我们在第一个选取的 S 中取了 T_{1\cdots r_1}，有 h_{1,r_1} 种方案；在第二个选取的 S 中取了 T_{r_1+1\cdots r_2} 有 h_{r_1+1,r_2} 种方案……

最终根据乘法原理，共有

种方案。特殊地，我们令其中 r_0=0,r_p=n。

但是我们还没有确定 p 个 S 的位置啊？

从 k 个 S 里面选 p 个 S，显然这一步的方案数是 C_k^p。递推求组合数明显会超时，我们采用它的公式法：

其中 x! 表示 x 的阶乘。

取模操作中怎么处理分母中的 m!？

加入乘法逆元后同余问题的各项性质不会被打破。\ 通俗地说，我们把 \frac{1}{m!} 当做 m!^{998244351} 处理即可。

综上，对于将 T 分割为 p 个子串 T_{1\cdots r_1},T_{r_1+1\cdots r_2}\cdots T_{r_{p-1}+1\cdots m}，有

种方案。

但是我们还没有确定分割方案？

打住。

看看数据范围：m\le 10。\ 于是搜索分割方案，累加答案即可。

总复杂度

动归求 h 数组复杂度：O(nm^3)\ 搜索累加答案复杂度：O(m!\times m)。\ 总复杂度：O(nm^3+m!\times m)。\