[cf461E]Appleman and a Game

考虑我的每一次添加操作，要满足：1.该串是t的子串；2.该串不能与下一次的串开头字母构成t的子串。那么，设f[i][j][k]表示拼i次，第i次填入的开头字母是j，第i+1填入的开头字母是k的最短长度。

状态转移方程：f[i][j][k]=min(f[i-1][j][t]+f[1][t][k])，这个东西可以用矩阵乘法来搞（把加改成min即可）。

这样求出的最后一个存在j和k满足f[i][j][k]<n的i即为答案，因为f[i][j][k]的值一定随i的增长而增长，因此可以二分i并判断是否存在。

之后还要预处理出f[1][i][j]，这个东西暴力枚举显然是$o(n^{2})$的，但是发现判断f[1][i][j]不合法当且仅当所有以i为开头以j为结尾且长度为f[1][i][j]的串都是t的子串，而t中长度固定的串不超过|t|个，而这样的串有$4^{f[1][i][j]}$个，如果满足$4^{f[1][i][j]}>|t|$则f[1][i][j]一定不合法，大约有$f[1][i][j]\leq 20$。

接下来计算就很简单来，可以对s中所有长度小于等于20的子串建一棵trie树并统计一下就可以。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct ji{
    ll a[5][5];
}a,b,c;
ll n,k;
int V,tr[2000005][5],f[5][5][100005];
char s[100005];
void ins(int k){
    for(int i=k,j=1;(i<k+20)&&(s[i]);j=tr[j][s[i++]-'A'])
        if (!tr[j][s[i]-'A']){
            tr[j][s[i]-'A']=++V;
            f[s[k]-'A'][s[i]-'A'][i-k]++;
        }
}
ji cheng(ji a,ji b){
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)c.a[i][j]=n+1;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                c.a[i][k]=min(c.a[i][k],a.a[i][j]+b.a[j][k]);
    return c;
}
void ksm(ji a,ll n){
    while (n){
        if (n&1)b=cheng(b,a);
        a=cheng(a,a);
        n/=2;
    }
}
bool pd(ji a){
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if (a.a[i][j]<n)return 1;
    return 0;
}
int main(){
    scanf("%lld%s",&n,s);
    V=1;
    for(int i=0;s[i];i++)ins(i);
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++){
            for(int k=1;f[i][j][k]==(1<<(2*k-2));k++)a.a[i][j]=k;
            a.a[i][j]++;
        }
    k=n;
    for(ll i=0;i<k;){
        memset(b.a,0,sizeof(b.a));
        ll j=(i+k+1>>1);
        ksm(a,j);
        if (pd(b))i=j;
        else k=j-1;
    }
    printf("%lld",k+1);
}