自动搬运

查看原文

来自洛谷，原作者为

	chenxi2009 身如柳絮随风扬。|粉福见专栏。|红名且勾支持互

搬运于2025-08-24 23:03:38，当前版本为作者最后更新于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}$ 的序列数量。
易得递推：

$$f_{i,j}=f_{i-1,j}+\sum_{k=1}^{i-1}f_{k,j-1} (S_i=T_j) $$$$f_{i,j}= f_{i-1,j} (S_i\ne T_j)$$

复杂度 $O(n^2m)$。

令

$$g_{i,j}=\sum_{k=1}^{j}f_{i,k}$$

易得新的递推式：

$$g_{i,j}=g_{i-1,j}+g_{i-1,j-1}(S_i=T_j)$$ $$g_{i,j}=g_{i-1,j}(S_i\ne T_j)$$

复杂度 $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}$ 种方案……

最终根据乘法原理，共有

$$\prod_{i=1}^{p} h_{r_{i-1}+1,r_i}$$

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

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

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

$$C_n^m=\frac{n!}{m!(n-m)!}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!} $$

其中 $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}$，有

$$C_k^p\times \prod_{i=1}^{p} h_{r_{i-1}+1,r_i}$$

种方案。

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

打住。

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

总复杂度

动归求 $h$ 数组复杂度：$O(nm^3)$
搜索累加答案复杂度：$O(m!\times m)$。
总复杂度：$O(nm^3+m!\times m)$。
$m$ 个组合数可以预处理得出，其中逆元可以打表，复杂度不计。

显然跑不满，最慢测试点 5ms

代码

参考程序

#include<bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
int n,m,len,jd[11],inv[11] = {0,1,499122177,332748118,748683265,598946612,166374059,855638017,873463809,443664157,299473306};
long long k,jc[11],c[11],ans,f[11][11],g[11];
char s[5001],t[11];
void sch(int w){ //搜索 T 的分割方案 
	if(w == len + 1){
		long long cnt = c[len];
		for(int i = 1;i <= len;i ++) cnt = cnt * f[jd[i - 1] + 1][jd[i]] % MOD;
		ans = (ans + cnt) % MOD;
		return; 
	}
	if(w == len){
		jd[w] = m,sch(w + 1);
		return;
	}
	for(int i = jd[w - 1] + 1;i <= m - len + w;i ++) jd[w] = i,sch(w + 1);
	return;
}
int main(){
	scanf("%lld%s%s",&k,s + 1,t + 1);
	n = strlen(s + 1),m = strlen(t + 1);
	c[1] = k % MOD;
	for(int i = 2;i <= m;i ++) c[i] = c[i - 1] * (k % MOD - i + 1) % MOD * inv[i] % MOD; //预处理组合数 
	for(int l = 1;l <= m;l ++){
		for(int r = l;r <= m;r ++){ //计算 T 的每个子串对应的 h 数组值，这里用 f 存储 
			memset(g,0,sizeof(g));
			g[0] = 1;
			for(int i = 1;i <= n;i ++) for(int j = r;j >= l;j --) if(t[j] == s[i]) g[j - l + 1] = (g[j - l + 1] + g[j - l]) % MOD;
			f[l][r] = g[r - l + 1];
		}
	}
	for(len = 1;len <= m;len ++) sch(1);
	printf("%lld",ans);
	return 0;
}

总结：一道颇具思维趣味性的题目，做法本身没有蓝题难度但是思维可以有，显然仍具优化空间，本题解只提供了一个基础的做法权当抛砖引玉，欢迎大家改进本蒟蒻的做法！

闲话：赛时 RP 爆表，第一次成绩这么好！