自动搬运

查看原文

来自洛谷，原作者为

	naturelyf > 最后在线时间：2025年7月24日8时49分 <

搬运于2025-08-24 22:18:42，当前版本为作者最后更新于2024-11-14 15:14:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题外话

这套题考的模拟赛，三四题都稍显抽象（没考第一题），就二和五题能做一下，但还被背刺了，DFS 直接爆栈了，学校 OJ 翻译不全真是晦气是道好题。

题目大意

给定 $n$ 组人，每组选一人，要求前一组人的姓名必须是后一组的连续子串，求有多少种合法答案。

解题思路

考虑建图。我们可以将问题看作一第一组为起点，走到最后一组，算做一种解，理论可行，开始实践。

代码思路

暴力

首先考虑暴力，强行判断是不是下一组的连续子串，最后简单动态规划统计方案，也可以用记忆化。期望时间复杂度 $O(nk^3)$，代码如下（有注释）：

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int N=2000,MOD=1e9+7;
string s[51][1500];
int n,k;
bool check(string a,string b){
	int l=a.size();
	int fl=0;
	for(int i=0,j=0;i<l;i++,j++){
		if(a[i]!=b[j]){
			fl++;
			break;	
		}
	}//这里是看看是第一个不同还是最后一个不同
	for(int i=0,j=1;i<l;i++,j++){
		if(a[i]!=b[j]){
			fl++;
			break;	
		}
	}
	if(fl==2)return false;
	return true;
}
vector<int> edge[N*N];
int f[N*N];
void add(int u,int v){
	edge[u].push_back(v);
}
int dfs(int u){
	if(f[u])return f[u];
	for(int v:edge[u]){
		f[u]+=dfs(v);
		f[u]%=MOD;
	}
	f[u]%=MOD;
	return f[u];
}//状态转移方程式太难辣，直接记忆化
signed main(){
	freopen("trener.in","r",stdin);
	freopen("trener.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=k;i++)f[i]=1;
	for(int i=1;i<=k;i++)add(i,0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++)
			cin>>s[i][j];
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=k;j++){
			string s1=s[i][j];
			for(int p=1;p<=k;p++)
				if(check(s1,s[i+1][p])){
					add(p+i*k,j+(i-1)*k);
				}//从下向上连边，方便搜索。
		}//这里相当于将二位平铺成一维，方便建图。
	}
//	for(int i=0;i<=n*k;i++){
//		for(int j:edge[i])
//			cout<<i<<" "<<j<<'\n';
//	}
	int ans=0;
	for(int i=k*n;i>k*(n-1);i--)ans+=dfs(i),ans%=MOD;
//	for(int i=1;i<=n*k;i++)
//	cout<<f[i]<<" ";
	cout<<ans;
	return 0;
}

优化

打完之后恭喜你，获得 $50$ 分！仔细观察就能发现大有优化的余地。输入是 $O(nk^2)$，没有优化空间，枚举也是如此，只有判断相等开销大并且可以优化，回想我们学过的方法，有没有什么能 $O(1)$ 判断字符串相同呢，对啦，就是哈希，想到这点十分开心，直接把代码打出来：

#include<bits/stdc++.h>
#define int long long

#define ull unsigned long long

using namespace std;
const int N=51*1510,mod=1e18+9,MOD=1e9+7,base=131;
string s;
int n,k;
ull Hash[52][1510][3];
int HASH(string a){
	ull pr=base,res=0;
	int l=a.size();
	for(int i=0;i<l;i++){
		res=res+pr*(ull)(a[i]-'a'+1)%mod;
		res%=mod;
		pr*=base;
		pr%=mod;
	}
	return res;
}
bool check(int x,int y,int xx,int yy){
	if(Hash[x][y][2]==Hash[xx][yy][0]||Hash[x][y][2]==Hash[xx][yy][1])
		return true;
	return false;
}
vector<int> edge[N];
int f[N];
void add(int u,int v){
	edge[u].push_back(v);
}
int dfs(int u){
	if(f[u])return f[u];
	for(int v:edge[u]){
		f[u]+=dfs(v);
		f[u]%=MOD;
	}
	f[u]%=MOD;
	return f[u];
}
int in[N];
signed main(){
	freopen("trener.in","r",stdin);
	freopen("trener.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=k;i++)f[i]=1,in[i]=1;
	for(int i=1;i<=k;i++)add(i,0);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++){
			cin>>s;
			Hash[i][j][2]=HASH(s);
			if(i==1){
				Hash[i][j][0]=base*(ull)(s[0]-'a'+1);
				Hash[i][j][1]=base*(ull)(s[0]-'a'+1);
				continue;
			}
			char c=s.front();
			s.erase(s.begin());
			Hash[i][j][0]=HASH(s);
			s.insert(s.begin(),c);
			s.pop_back();
			Hash[i][j][1]=HASH(s);
		}
	for(int i=1;i<n;i++){
		for(int j=1;j<=k;j++){
			if(!in[j+(i-1)*k])continue;
			for(int p=1;p<=k;p++)
				if(check(i,j,i+1,p)){
					add(p+i*k,j+(i-1)*k);
					in[p+i*k]=1;
				}
		}
	}
//	for(int i=0;i<=n*k;i++){
//		for(int j:edge[i])
//			cout<<i<<" "<<j<<'\n';
//	}
	int ans=0;
	for(int i=k*n;i>k*(n-1);i--)ans+=dfs(i),ans%=MOD;
	cout<<ans;
	return 0;
}

$Hash[i][j][0]$ 存的是后几位的哈希值，$Hash[i][j][1]$ 存的是前几位的，$Hash[i][j][2]$ 存的是整个串的哈希值，这样就可以优化掉一个 $k$ 了。这也是我的考场代码，自信以为可以 $200$ 分的，但是被背刺了。

正解（能过）

仔细思考，这个代码为什么 MLE，原因可能有三：一， vector 动态数组自动二倍空间直接炸了；二，想要省力全开 long long 炸了；三，记忆化爆栈。于是开始找问题，第一步先优化掉 vector 用链式前向星存图，没有效果，然后开始精挑细选换类型，依旧错了，所以只能是记忆化爆栈。

找到问题了，考虑优化。我们发现在建新层的时候不会对原先的图有更改，于是可以选择边建图边计算，这样不仅可以节约存图的空间，还不用调用大量递归以至于爆栈，代码如下：

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int N=51*1510,mod=1e9+9,MOD=1e9+7,base=131;
string s;
int n,k;
ull Hash[52][1510][3];
vector<int> edge;
int HASH(string a){
	ull pr=base,res=0;
	int l=a.size();
	for(int i=0;i<l;i++){
		res=res+pr*(ull)(a[i]-'a'+1)%mod;
		res%=mod;
		pr*=base;
		pr%=mod;
	}
	return res;
}
bool check(int x,int y,int xx,int yy){
	if(Hash[x][y][2]==Hash[xx][yy][0]||Hash[x][y][2]==Hash[xx][yy][1])
		return true;
	return false;
}
int f[N];
int in[N];
signed main(){
//	freopen("trener.in","r",stdin);
//	freopen("trener.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=k;i++)f[i]=1,in[i]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++){
			cin>>s;
			Hash[i][j][2]=HASH(s);
			if(i==1){
				Hash[i][j][0]=base*(ull)(s[0]-'a'+1);
				Hash[i][j][1]=base*(ull)(s[0]-'a'+1);
				continue;
			}
			char c=s.front();
			s.erase(s.begin());
			Hash[i][j][0]=HASH(s);
			s.insert(s.begin(),c);
			s.pop_back();
			Hash[i][j][1]=HASH(s);
		}
	for(int i=1;i<n;i++){
		for(int j=1;j<=k;j++){
			if(!in[j+(i-1)*k])continue;
			for(int p=1;p<=k;p++)
				if(check(i,j,i+1,p)){
					edge.push_back(p+i*k);
					in[p+i*k]=1;
				}
			for(int v:edge)
				f[v]+=f[j+(i-1)*k]%MOD;
			edge.clear();
		}//现在这里的edge存的就是这个点能走到下一层的哪个位置
	}
	int ans=0;
	for(int i=k*n;i>k*(n-1);i--)ans+=f[i],ans%=MOD;
	cout<<ans;
	return 0;
}

完结撒花！