【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
