Description

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

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

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

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

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

Solution

如果S字符串我们已经知道,那么求操作次数就是一个贪心的过程:因为走到后缀自动机上每一个节点的路径对应原串的一个子串,在后缀自动机上一直走,直到不可以走为止,然后重新开始匹配

基于这个思路,我们可以二分一个操作次数\(mid\),然后用 \(mid\) 个原串的子串构造一个长度最小的串\(S\),然后比较与\(n\)的关系即可

考虑构造的方法:

设 \(f[i][j]\) 表示以字符\(i\)开头的子串后面接上一个以\(j\)开头的子串,使得\(i\)开头的和\(j\)开头的两个子串接在一起不是原串的子串的情况下,\(i\)后面接的这个子串最少是多长

显然我们只需要用\(f\)数组转移\(mid\)次,取最小的一个串即可,这个过程每一步都是相同的,可以用矩阵快速幂优化或倍增\(floyd\)优化一下.

考虑预处理\(f\)数组:

设\(g[i][j]\)表示在后缀自动机上的\(i\)节点,最少走几步可以使后面接上一个以\(j\)开头的子串,接好的串不出现在原串中.

\(g[i][j]=min(g[son][j]+1)\)

\(g[i][j]=0\) 如果\(i\)节点没有\(j\)这个儿子

\(f[i][j]=g[ch[1][i]][j]\),1的\(i\)儿子往后走的串一定是以\(i\)开头的子串

#include
    
     using namespace std;typedef long long ll;const int N=2e5+10;const ll inf=1e18+10;ll n;char S[N];int cur=1,cnt=1,len[N],fa[N],ch[N][5];inline void ins(int c){  int p=cur;cur=++cnt;len[cur]=len[p]+1;  for(;!ch[p][c];p=fa[p])ch[p][c]=cur;  if(!p)fa[cur]=1;  else{    int q=ch[p][c];    if(len[q]==len[p]+1)fa[cur]=q;    else{      int nt=++cnt;len[nt]=len[p]+1;      memcpy(ch[nt],ch[q],sizeof(ch[q]));      fa[nt]=fa[q];fa[q]=fa[cur]=nt;      for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;    }  }}int sa[N],c[N],f[N][6];inline void priwork(){  memset(f,127/3,sizeof(f));  for(int i=1;i<=cnt;i++)c[len[i]]++;  for(int i=1;i<=cnt;i++)c[i]+=c[i-1];  for(int i=cnt;i;i--)sa[c[len[i]]--]=i;  for(int i=cnt;i;i--){    int x=sa[i];    for(int j=0;j<4;j++){      if(!ch[x][j])f[x][j]=1;      for(int k=0;k<4;k++)    f[x][j]=min(f[x][j],f[ch[x][k]][j]+1);    }  }}struct node{  ll a[5][5];  node(){memset(a,0,sizeof(a));}  void Clear(node &x,ll y){    for(int i=0;i<5;i++)      for(int j=0;j<5;j++)x.a[i][j]=y;  }  inline node operator *(const node &p){    node ret;Clear(ret,inf);    for(int i=1;i<=4;i++)      for(int j=1;j<=4;j++)    for(int k=1;k<=4;k++)      ret.a[i][j]=min(ret.a[i][j],a[i][k]+p.a[k][j]);    return ret;  }  inline node ksm(node x,ll k){    node sum;    while(k){      if(k&1)sum=sum*x;      x=x*x;k>>=1;    }    return sum;  }};inline bool check(ll mid){  node S;  for(int i=1;i<=4;i++)    for(int j=1;j<=4;j++)      S.a[i][j]=f[ch[1][i-1]][j-1];  S=S.ksm(S,mid);  ll ret=inf;  for(int i=1;i<=4;i++)    for(int j=1;j<=4;j++)      ret=min(ret,S.a[i][j]);  return ret>=n;}int main(){  freopen("pp.in","r",stdin);  freopen("pp.out","w",stdout);  cin>>n;  scanf("%s",S);  int le=strlen(S);  for(int i=0;i
     
      >1;    if(check(mid))ans=mid,r=mid-1;    else l=mid+1;  }  cout<
      
       <