[BZOJ4180]字符串计数 - A-Failure的博客

题目

Description

SD有一名神犇叫做Oxer，他觉得字符串的题目都太水了，于是便出了一道题来虐蒟蒻yts1999。

他给出了一个字符串T，字符串T中有且仅有4种字符 ‘A’, ‘B’, ‘C’, ‘D’。现在他要求蒟蒻yts1999构造一个新的字符串S，构造的方法是：进行多次操作，每一次操作选择T的一个子串，将其加入S的末尾。

对于一个可构造出的字符串S，可能有多种构造方案，Oxer定义构造字符串S所需的操作次数为所有构造方案中操作次数的最小值。

Oxer想知道对于给定的正整数N和字符串T，他所能构造出的所有长度为N的字符串S中，构造所需的操作次数最大的字符串的操作次数。

蒟蒻yts1999当然不会做了，于是向你求助。

Input

第一行包含一个整数N，表示要构造的字符串长度。

第二行包含一个字符串T，T的意义如题所述。

Output

输出文件包含一行，一个整数，为你所求出的最大的操作次数。

Sample Input

5
ABCCAD

Sample Output

HINT

【样例说明】

例如字符串”AAAAA”，该字符串所需操作次数为5，不存在能用T的子串构造出的，且所需操作次数比5大的字符串。

【数据规模和约定】

对于100%的数据，$1 ≤ N ≤ 10^18，1 ≤ \vert T\vert ≤ 10^5$。

题解

可能是省选前最后一篇题解了~~可能是这辈子最后一篇题解了~~

首先考虑给定串$S$，该以什么方式构造

根据贪心，应该用$S$在$T$的$SAM$上面跑，如果匹配不了就返回根节点，表示加入一个子串（操作数$+1$）

为什么是对的呢？假设$a$是$b$的子串，那么$b$往后能匹配到的$a$肯定也可以，但$a$能匹配到的$b$不一定可以，这样就要求划分出来的当前要匹配的串尽可能的短

把$SAM$中的表示字符$c$的空节点向根的$c$儿子连一条权值为$1$的边，这样问题就转化成了要求在$SAM$这个图上跑$N$条边得到的权值和的最大值

发现根的$a$儿子转移到$b$儿子肯定是从离$a$最近的没有$b$儿子的节点转移过去的，所以可以把这个图化简，最后能化成一个$4$个点的完全图

这样就可以二分答案，然后用矩乘检验答案是否正确了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=2e5+5;
struct p{
	LL a[4][4];
	void clear()
	{
		for(int i=0;i<4;++i)
		  for(int j=0;j<4;++j)
		    a[i][j]=1e18;
	}
}a;
int n;
LL N;
char s[MAX];
p operator* (p A,p B)
{
	p ans;
	ans.clear();
	for(int i=0;i<4;++i)
	  for(int j=0;j<4;++j)
	    for(int k=0;k<4;++k)
	      ans.a[i][j]=min(ans.a[i][j],A.a[i][k]+B.a[k][j]);
	return ans;
}
p Pow(p a,LL b)
{
	p ans;
	memset(ans.a,0,sizeof(ans.a));
	for(;b;b>>=1,a=a*a)
	  if(b&1) ans=ans*a;
	return ans;
}
struct SAM{
	int l,r,L;
	int len[MAX],fa[MAX],qu[MAX],d[MAX];
	int son[MAX][4];
	bool use[MAX];
	SAM() {l=r=1;}
	void ins(int x)
	{
		int tt=r;
		len[r=++l]=++L;
		for(;tt&&!son[tt][x];tt=fa[tt])
		  son[tt][x]=r;
		if(!tt) return void(fa[r]=1);
		int qwq=son[tt][x];
		if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
		len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[qwq]=fa[r]=l;
		for(int i=0;i<4;++i)
		  son[l][i]=son[qwq][i];
		for(int i=tt;son[i][x]==qwq;i=fa[i])
		  son[i][x]=l;
	}
	void Solve(int x)
	{
		int hl=1,tl=1,cnt=0;
		qu[1]=son[1][x],d[son[1][x]]=0;
		while(hl<=tl)
		{
			if(cnt==4) return;
			int tt=qu[hl++];
			for(int i=0;i<4;++i)
			  if(!son[tt][i])
			  {
			  	if(a.a[x][i]==1e18) a.a[x][i]=d[tt]+1,++cnt;
			  }
			  else if(!use[son[tt][i]]) use[son[tt][i]]=1,d[son[tt][i]]=d[tt]+1,qu[++tl]=son[tt][i];
		}
	}
}_S;
bool look(LL mid)
{
	p b=Pow(a,mid);
	LL val=1e18;
	for(int i=0;i<4;++i)
	  for(int j=0;j<4;++j)
	    val=min(val,b.a[i][j]);
	return val<N;
}
int main()
{
	scanf("%lld%s",&N,s+1),n=strlen(s+1),a.clear();
	for(int i=1;i<=n;++i)
	  _S.ins(s[i]-'A');
	_S.Solve(0),_S.Solve(1),_S.Solve(2),_S.Solve(3);
	LL l=1,r=N,ans;
	while(l<=r)
	{
		LL mid(l+r>>1);
		if(look(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return printf("%lld",ans+1),0;
}

题目