题解：【COCI2019-2020#6】 Trener

题目链接

本人于三月二十四日模拟赛本题中使用 \(\mathcal O(n^2 k + n k^2)\) 哈希+DP，因神秘常数原因竟打不过 \(\mathcal O(n^2 k^2)\)，甚至被卡的TLE飞起，怒挂五十分。赛后交了一页的TLE，最后换成自然溢出才能过，铭记贰点贰叁。

不会吧不会吧不会还有人这个题写 \(\mathcal O(n^2 k + n k^2)\) 吧。

平凡的做法其他题解说的很清楚了，注意到我们 \(O(k^2)\) 的判断前后缀是否相等其实没有必要，这里可以将哈希值从小到大排序并记下编号，使用双指针优化只扫一遍，将前后缀相同的记录在一起，然后再去重累加上答案，时间复杂度 \(\mathcal O(n^2 k + n(k + n \log k))\)，瓶颈在于排序。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
using namespace std;

bool Mbe;

namespace LgxTpre
{
	static const int MAX=1510;
	static const int INF=4557430888798830399;
	static const int mod=1e9+7;
	static const int bas=151;
	
	inline void Madd(int &a,int b) {a=a+b>=mod?a+b-mod:a+b;}
	inline void Mdel(int &a,int b) {a=a-b<0?a-b+mod:a-b;}
	inline int  Cadd(int a,int b)  {return a+b>=mod?a+b-mod:a+b;}
	
	int n,k,ans,len;
	string s;
	ull suf[MAX][MAX],pre[MAX][MAX],all[MAX][MAX],tmp1[MAX],tmp2[MAX];
	int dp[MAX][MAX],vis[MAX],id[MAX],idd[MAX],cas[MAX],num;
	vector<int> buc[MAX];
		
	inline void lmy_forever()
	{
		cin>>n>>k;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=k;++j)
			{
				cin>>s; len=s.size();
				for(int h=0;h<len;++h) 
				{
					all[i][j]=all[i][j]*bas+s[h];
					if(h!=0) pre[i][j]=pre[i][j]*bas+s[h];
					if(h!=len-1) suf[i][j]=suf[i][j]*bas+s[h];
				}
			}
		for(int i=1;i<=k;++i) dp[1][i]=1;
		for(int i=1;i<n;++i)
		{
			for(int j=1;j<=k;++j) buc[j].clear(),id[j]=idd[j]=j;
			sort(idd+1,idd+k+1,[i](int a,int b){return all[i][a]<all[i][b];});
			for(int j=1;j<=k;++j) tmp1[j]=all[i][idd[j]];
			sort(id+1,id+k+1,[i](int a,int b){return pre[i+1][a]<pre[i+1][b];});
			for(int j=1;j<=k;++j) tmp2[j]=pre[i+1][id[j]];
			for(int j=1,iter=1;j<=k;++j)
			{
				while(iter<=k&&tmp2[iter]<tmp1[j]) ++iter;
				for(int con=iter;con<=k&&tmp2[con]==tmp1[j];++con) buc[idd[j]].pb(id[con]); 
			}
			sort(id+1,id+k+1,[i](int a,int b){return suf[i+1][a]<suf[i+1][b];});
			for(int j=1;j<=k;++j) tmp2[j]=suf[i+1][id[j]];
			for(int j=1,iter=1;j<=k;++j)
			{
				while(iter<=k&&tmp2[iter]<tmp1[j]) ++iter;
				for(int con=iter;con<=k&&tmp2[con]==tmp1[j];++con) buc[idd[j]].pb(id[con]); 
			}
			for(int j=1;j<=k;++j)
			{
				num=0;
				for(auto it:buc[j]) if(!vis[it]) vis[it]=1,cas[++num]=it;
				buc[j].clear();
				for(int p=1;p<=num;++p) vis[cas[p]]=0,buc[j].pb(cas[p]);
			}
			for(int j=1;j<=k;++j)
				if(dp[i][j])
					for(auto it:buc[j])
						Madd(dp[i+1][it],dp[i][j]);	
		}
		for(int i=1;i<=k;++i) Madd(ans,dp[n][i]);
		cout<<ans<<endl;
		return;
	}
}

bool Med;

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	fprintf(stderr,"%.3lf MB\n",(&Med-&Mbe)/1048576.0);
	LgxTpre::lmy_forever();
	cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
	return (0-0);
}

事实上我们也可以不使用哈希。对于这种多个字符串记录相同前后缀数量的问题，我们更容易想到使用 \(\text{Trie}\) 树操作。我们记以当前节点的答案数量为 \(cnt_i\)，依次将每个字符串插入 \(\text{Trie}\) 树，然后直接在 \(\text{Trie}\) 树中查找其前后缀的位置并累加 \(cnt\) 的值。这里注意当查找前后缀所在的节点最后相同时，说明出现了重复，我们只累加一遍。由于在 \(\text{Trie}\) 树上多个串共用一个节点位置，所以我们最后统计的答案实则为累加一个串前后缀 \(cnt\) 操作的增量。时间复杂度 \(\mathcal O(n^2 k)\)，瓶颈在于读入。

#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
using namespace std;

bool Mbe;

namespace LgxTpre
{
	static const int MAX=1510*1510;
	static const int INF=4557430888798830399;
	static const int mod=1e9+7;
	
	inline void Madd(int &a,int b) {a=a+b>=mod?a+b-mod:a+b;}
	inline void Mdel(int &a,int b) {a=a-b<0?a-b+mod:a-b;}
	inline int  Cadd(int a,int b)  {return a+b>=mod?a+b-mod:a+b;}
	
	int n,k,ans;
	int now,pre,suf;
	
	string s;
	int ch[MAX][30],cnt[MAX],tot=1;
	inline int insert()
	{
		int len=s.size(),now=1;
		for(int i=0;i<len;++i)
		{
			int to=s[i]-'a';
			if(!ch[now][to]) ch[now][to]=++tot;
			now=ch[now][to];
		}
		return now;
	}
	inline int find(int cas)
	{
		int len=s.size(),now=1;
		for(int i=cas;i<len-(1-cas);++i)
		{
			int to=s[i]-'a';
			if(!ch[now][to]) return 0;
			now=ch[now][to];
		}
		return now;
	}
		
	inline void lmy_forever()
	{
		cin>>n>>k; cnt[1]=1;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=k;++j)
			{
				cin>>s;
				now=insert();
				pre=find(0);
				suf=find(1);
				if(i==n) Mdel(ans,cnt[now]);
				if(pre==suf) Madd(cnt[now],cnt[pre]);
				else Madd(cnt[now],Cadd(cnt[pre],cnt[suf]));
				if(i==n) Madd(ans,cnt[now]);
			}
		cout<<ans<<endl;
		return;
	}
}

bool Med;

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	fprintf(stderr,"%.3lf MB\n",(&Med-&Mbe)/1048576.0);
	LgxTpre::lmy_forever();
	cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
	return (0-0);
}

最后放一张评测图片，高下立判：