【CF461E】Appleman and a Game 倍增floyd

【CF461E】Appleman and a Game

题意：你有一个字符串t（由A,B,C,D组成），你还需要构造一个长度为n的字符串s。你的对手需要用t的子串来拼出s，具体来说就是每次找一个t的子串放在已经拼出来的串的后面。你想要最大化你的对手拼出s的所需次数，你的对手是绝顶聪明的。输出这个次数。

$n\le 10^{18},|t|\le 10^5$

题解：先从对手的角度考虑，每次它肯定是尽可能的延伸已有的字符串，一直延伸到t中不存在这个子串为止。所以我们可以每次向s中加入[a,b)，使得t中不存在[a,b]。我们可以把问题转换成：如果想让对手至少拼i次，我们需要的s最短可以是多少。到时候二分这个答案即可。

设f[i][a][b]表示让对手至少拼i次，且s从字符a还开始，下一个字符是b时，s的最短长度。那么我们可以找出最小的l，满足t中不包含所有从a开始以b结束的子串。因为长度为l的串有$4^{l-2}$种（去掉a,b），而t中长度为l的串只有$|t|-l$个，所以l只需要枚举到$\log t$即可，具体过程可以用Trie树来搞。所以f[i][a][b]=l-1。

接着上倍增floyd即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=100010;

ll n,ans;

int m,tot;

char str[maxn];

int ch[maxn*20][4],cnt[4][4][22];

struct M

{

	ll v[4][4];

	M () {memset(v,0x3f,sizeof(v));}

	ll * operator [] (const int &a) {return v[a];}

	M operator * (const M &a) const

	{

		M b;

		int i,j,k;

		for(i=0;i<4;i++)	for(j=0;j<4;j++)	for(k=0;k<4;k++)	b.v[i][j]=min(b.v[i][j],v[i][k]+a.v[k][j]);

		return b;

	}

	inline bool check()

	{

		int i,j;

		for(i=0;i<4;i++)	for(j=0;j<4;j++)	if(v[i][j]<n)	return 1;

		return 0;

	}

}f[64],g,h;

int main()

{

	scanf("%lld%s",&n,str),m=strlen(str);

	int i,j,u,a,b,mx;

	tot=1;

	for(i=0;i<m;i++)

	{

		a=str[i]-'A';

		for(u=1,j=i;j<m&&j<i+20;j++)

		{

			b=str[j]-'A';

			if(!ch[u][b])	ch[u][b]=++tot,cnt[a][b][j-i]++;

			u=ch[u][b];

		}

	}

	for(a=0;a<4;a++)	for(b=0;b<4;b++)

	{

		for(j=1;cnt[a][b][j]==(1<<((j-1)<<1));j++);

		f[0][a][b]=j;

	}

	memset(g.v,0,sizeof(g.v));

	//if(n>=100)	for(a=0;a<4;a++)	for(b=0;b<4;b++)	printf("%d %d:%lld\n",a,b,f[0][a][b]);

	for(mx=0;f[mx].check();mx++)	f[mx+1]=f[mx]*f[mx];

	for(i=mx-1;i>=0;i--)

	{

		h=g*f[i];

		if(h.check())	g=h,ans|=1ll<<i;

	}

	printf("%lld",ans+1);

	return 0;

}//260048835025948762 AAAABAACAADA