自动搬运

查看原文

来自洛谷，原作者为

	wangkelin123 各奋愚公之愿，即可移山；共怀精卫之心，不难填海。人生须奋斗，失败是成功之母，奋斗乃万物之父。成功之花总是扎根于奋斗的土壤。

搬运于2025-08-24 22:41:00，当前版本为作者最后更新于2025-07-18 10:57:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看到题解里有很多都是爆搜的，但是这并没有什么技术含量。这里我发一个 DP 题解。

题目

这个题面写的很绕，但其实就想表达：有多少个连续子串满足长度为 $k$，并且有 $m$ 个字符串都包括此子串。

解法

哈希必不可少，运用前缀和的方法（可参照这题）算出每个字符串中长度为 $k$ 的不同连续子串的数量 $p_{i,tot_i}$，以及每种连续字串的个数 $cnt_{i,H}$。

接下来便是 DP 环节。$f_{i,j,H}$ 表示以 $i$ 为结尾（必选 $i$），选了 $j$ 个，哈希值为 $H$ 的子串的选择方案有多少种。

第一重循环当然是遍历字符串，下一重就是遍历此字符串中长度为 $k$ 的子串的哈希值 $H$（前面处理过），初始值 $f_{i,1,H}\gets cnt_{i,H}$。接着遍历选的个数（最大值为 $m$），最后一重循环遍历 $lst$，范围为 $1\le lst<i$。

DP 的方法即为把所有的 $lst$ 的方案数乘 $cnt_{i,H}$ 后加起来，也就是：

$$f_{i,j,H}=\sum _ {lst = 1} ^ {i-1} f_{lst,j-1,H}\times cnt_{i,H} $$

最后把所有的 $f_{i,m,H}$ 加起来（可以在 DP 中 $j$ 的循环内操作）即为答案。

设所有长度为 $k$ 的哈希最大值（自然溢出后）为 $H$， 则时间复杂度为 $O(n^2m\log H)$。

注意取模！

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N=1e5+5,base=131,mod=1e9+7;
int n,m,k;
ll ans;
ull pre[N],h[10][N],p[10][N],tot[10];
string s;
map<ull,ll>cnt[10],f[10][10];//f[i][j][H]表示前i个串（以i为结尾），选了j个，哈希值为H的数量 
map<ull,bool>vis;
ull Hash(int l,int r,int i){
	return h[i][r]-h[i][l-1]*pre[r-l+1];
	//123456789 4567->1234567-123*10^4
}
int main(){
	cin>>n>>m>>k; 
	pre[0]=1;
	for(int i=1;i<=1e5;i++) pre[i]=pre[i-1]*base;
	for(int i=1;i<=n;i++){
		cin>>s;
		for(int j=1;j<=s.size();j++) h[i][j]=h[i][j-1]*base+(s[j-1]-'A'+1);
		vis.clear();
		for(int j=1;j+k-1<=s.size();j++){
			ull H=Hash(j,j+k-1,i);
			cnt[i][H]++;
			if(!vis[H]){
				p[i][++tot[i]]=H;
				vis[H]=true;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int q=1;q<=tot[i];q++){
			ull H=p[i][q];
			f[i][1][H]=cnt[i][H];
			for(int j=1;j<=m;j++){
				for(int lst=1;lst<i;lst++){
					f[i][j][H]=(f[i][j][H]+f[lst][j-1][H]*cnt[i][H]%mod)%mod;
				}
				if(j==m) ans=(ans+f[i][j][H])%mod;
			}
		}
	}
	cout<<ans;
	return 0;
}