[CF 461E] Appleman and a Game

作法：

考慮給定字串$s$之後要如何用最少步湊出$s$。這只要取一個最長的$s$的前綴，滿足他是$t$的子字串，把他拼上去之後重複這個過程就好了，因為如果我們取的是比較短的子字串，那麼可以用「把第一個子字串伸長，第二個子字串的前面截掉」來把原本的湊法換成剛才講的湊法。因此當我們想要算長度為$n$的$s$最差狀況下要幾次才能湊出來，可以考慮取某個$t$的子字串$U$，滿足他的後面再加上$c$之後就不會是$t$的子字串了（$c$是$ABCD$中的某一個），那麼就可以在$s$的最前面寫上$U$這個字串，並且約定下一個字元放的是$c$，這樣湊出$s$的第一步就是選$t$的$U$這個子字串並放上去了。由這個就可以想到，令$dp[i][j]$代表長度為$i$，開頭為$j$的字串最差狀況下要用幾個$t$的子字串湊出來，那麼為了計算$dp[i][j]$，我們需要取一個開頭是$j$的$U$字串放在所求字串的最前面才行（$U$和前面提到的一樣），也就是如果我們記開頭為$j$的$U$字串，且他後面準備要放的字元是$k$時的最短長度為$L[j][k]$，那麼就可以列出轉移式了：$dp[i][j]=max\{ dp[i-L[j][k]][k]+1 \},k=0,1,2,3$。其中我們以$0,1,2,3$分別代表$A,B,C,D$。

而首要工作就是要先求出$L[i][j]$是多少，這可以用後綴自動機加上簡單的DP得到，關於後綴自動機可以參考這篇，寫的蠻詳細的。

再來我們想要求出當$i$很大時的$dp$值。仔細觀察轉移式可以發現，可以把他解讀成當第二維從$j$走到$k$之後，第一維的值就會增加$L[j][k]$，這就有點類似在一張圖上從$j$走到$k$的距離是$L[j][k]$一樣，因此如果考慮構造一張四個點的圖，其中任兩點$j,k$之間連一條有向邊，邊權為$L[j][k]$，那麼問題就轉化成了：從某一個點開始一直走，走到總權重的和$\geq n$時最多走了幾步。而這個問題可以二分搜解決，等於是變成要算出走$m$步後走過的最短距離為多少，這可以用倍增法算出，也就是預先算出「從$i$走了$2^k$步到$j$所走的最短路徑長」就可以了。

code :

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define INF 18446744073709551615ULL
using namespace std;
const int maxn=100000 ;
 
struct node
{
    node *p ;
    int l,dp[4] ;
    node *trans[4] ;
    node(){l=0 ; p=NULL ;}
    node(node *u)
    {
        p=u->p ; l=u->l ;
        for(int i=0;i<4;i++) trans[i]=u->trans[i] ;
        fill(dp,dp+4,maxn) ;
    }
    node(int _l,node *_p)
    {
        l = _l ; p = _p ;
        memset(trans,0,sizeof(trans)) ;
        fill(dp,dp+4,maxn) ;
    }
};
 
node *root ;
void build_SAM(char *A)
{
    node *curnode ;
    root=curnode=new node(0,NULL);//最开始的后缀自动机只有一个节点，长度是0，父亲是空
    for(int i=0;A[i];i++)
    {
        int x=A[i]-'A';//增加一个字符
        node *p=curnode;
        curnode=new node(i+1,NULL);//建立一个Lth为i+1的节点
        for(;p && p->trans[x]==NULL ; p=p->p) p->trans[x]=curnode;//沿祖先向上，寻找插入位置。同时更新Trans
        if(!p)curnode->p=root;//插入到根的下面
        else
        {
            node *q=p->trans[x];
            if (q->l==p->l+1)curnode->p=q;//成为q的孩子
            else
            {
                node *r=new node(q);r->l=p->l+1;//新建一个节点，表示curnode和q的公共前缀
                q->p=r;curnode->p=r;//兄弟
                for (;p && p->trans[x]==q;p=p->p)p->trans[x]=r;//更新第二部分的Trans
            }
        }
    }
}
 
char s[maxn] ;
void DP(node *u)
{
    if(u->dp[0]!=maxn) return ;
    for(int i=0;i<4;i++)
    {
        if(!u->trans[i]) u->dp[i]=1 ;
        else DP(u->trans[i]) ;
    }
    for(int i=0;i<4;i++) if(u->trans[i])
        for(int j=0;j<4;j++)
        u->dp[j]=min(u->dp[j],u->trans[i]->dp[j]+1) ;
}
 
struct P{ULL a[4][4];};
P operator + (const P &x,const P &y)
{
    P z ;
    for(int i=0;i<4;i++) for(int j=0;j<4;j++)
    {
        z.a[i][j]=INF ;
        for(int k=0;k<4;k++)
            z.a[i][j]=min(z.a[i][j],x.a[i][k]+y.a[k][j]) ;
    }
    return z ;
}
 
P len[63] ;
ULL getlen(ULL x)
{
    P p ; memset(p.a,0,sizeof(p.a)) ;
    for(int i=0;i<63 && x;i++) if(x&(1LL<<i))
        p=p+len[i] , x^=(1LL<<i) ;
    ULL ret=INF ;
    for(int i=0;i<4;i++) for(int j=0;j<4;j++)
        ret=min(ret,p.a[i][j]) ;
    return ret ;
}
 
main()
{
    ULL n ; scanf("%I64u%s",&n,s) ;
    if(n==1){printf("1\n") ; return 0 ;}
    build_SAM(s) ;
    DP(root) ;
    for(int i=0;i<4;i++) for(int j=0;j<4;j++)
        len[0].a[i][j]=root->trans[i]->dp[j] ;
    for(int i=1;i<64;i++) len[i]=len[i-1]+len[i-1] ;
 
    ULL l=0 , r=n ;
    while(r-l>1)
    {
        ULL mid=(r+l)/2 ;
        if(getlen(mid)>=n) r=mid ;
        else l=mid ;
    }
    printf("%I64u\n",r) ;
}