BZOJ4180:字符串计数(SAM,二分,矩阵乘法)

Description

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

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

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

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

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

Input

第一行包含一个整数N，表示要构造的字符串长度。

第二行包含一个字符串T，T的意义如题所述。

Output

输出文件包含一行，一个整数，为你所求出的最大的操作次数。

Sample Input

5
ABCCAD

Sample Output

HINT

【样例说明】

例如字符串"AAAAA"，该字符串所需操作次数为5，不存在能用T的子串构造出的，且所需操作次数比5大的字符串。

【数据规模和约定】

对于100%的数据，1 ≤ N ≤ 10^18，1 ≤ |T| ≤ 10^5。

Solution

一篇写的很好的博客

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 #define N (200009)

 #define LL long long

 using namespace std;

 LL n,id;

 char s[N];

 queue<int>Q;

 int dis[N],vis[N];

 struct Matrix

 {

     LL m[][];

     Matrix(){memset(m,,sizeof(m));}

     Matrix operator * (const Matrix &b) const

     {

         Matrix c;

         for (int i=; i<; ++i)

             for (int j=; j<; ++j)

                 c.m[i][j]=1e18;

         for (int k=; k<; ++k)

             for (int i=; i<; ++i)

                 for (int j=; j<; ++j)

                     c.m[i][j]=min(c.m[i][j],m[i][k]+b.m[k][j]);

         return c;

     }

 }A,G;

 Matrix Qpow(Matrix a,LL b)

 {

     Matrix ans;

     for (int i=; i<; ++i) ans.m[i][i]=;

     while (b)

     {

         if (b&) ans=ans*a;

         a=a*a; b>>=;

     }

     return ans;

 }

 struct SAM

 {

     int son[N][],fa[N],step[N];

     int p,q,np,nq,last,cnt;

     SAM(){last=cnt=;}

     void Insert(int x)

     {

         p=last; np=last=++cnt; step[np]=step[p]+;

         while (p && !son[p][x]) son[p][x]=np, p=fa[p];

         if (!p) fa[np]=;

         else

         {

             q=son[p][x];

             if (step[q]==step[p]+) fa[np]=q;

             else

             {

                 nq=++cnt; step[nq]=step[p]+;

                 memcpy(son[nq],son[q],sizeof(son[q]));

                 fa[nq]=fa[q]; fa[q]=fa[np]=nq;

                 while (son[p][x]==q) son[p][x]=nq, p=fa[p];

             }

         }

     }

     void Build_Matrix()

     {

         for (int i=; i<; ++i)

             for (int j=; j<; ++j)

                 A.m[i][j]=1e18;

         for (int s=; s<; ++s)

         {

             while (!Q.empty()) Q.pop();

             memset(vis,false,sizeof(vis));

             vis[son[][s]]=true;

             Q.push(son[][s]); dis[son[][s]]=;

             while (!Q.empty())

             {

                 int x=Q.front(); Q.pop();

                 for (int i=; i<; ++i)

                     if (son[x][i] && !vis[son[x][i]])

                         vis[son[x][i]]=true,Q.push(son[x][i]),dis[son[x][i]]=dis[x]+;

                     else A.m[s][i]=min(A.m[s][i],(LL)dis[x]);

             }

         }

     }

 }SAM;

 LL check(LL x)

 {

     LL Min=1e18;

     G=Qpow(A,x);

     for (int i=; i<; ++i)

         for (int j=; j<; ++j)

             Min=min(Min,G.m[i][j]);

     return Min>=n;

 }

 int main()

 {

     scanf("%lld%s",&n,s);

     for (int i=,l=strlen(s); i<l; ++i)

         SAM.Insert(s[i]-'A');

     SAM.Build_Matrix();

     LL l=,r=1e18,ans;

     while (l<=r)

     {

         LL mid=(l+r)>>;

         if (check(mid)) ans=mid,r=mid-;

         else l=mid+;

     }

     printf("%lld\n",ans);

 }

巴特西