【XSY2779】最小表示串 KMP DP polya定理

时间：2022-06-22 05:27:19

题目描述

　　给你一个字符串\(s\)，问你有多少个串是最小表示串且字典序\(\leq s\)

　　\(|s|\leq 1000\)

题解

　　先把\(s\)变成比\(s\)小的最大的最小表示串。方法是从后枚举每一个字符，如果这个字符不是'a'，就把这个字符变成这个字符的前驱，并把后面所有字符字符变成'z'，然后判断是不是最小表示串。

　　可以用kmp去判断。如果\(\exists i,s_{i+1}>s_{fail_i+1}\)，那么这个串就不是最小表示串。

　　运用polya定理，把问题转化为求有多少个长度为\(i\)的字符串的最小表示串\(<s\)。最后把答案加上\(1\)。

　　如果一个字符串的最小表示串字典序比\(s\)小，那么就在这个串左旋到第一次字典序小于\(s\)的时候统计。

　　有两种情况：

　　情况1：\(???s_1s_2\ldots s_mr????\)

　　情况2：\(s_{k+1}\ldots s_mr????s_1s_2\ldots s_k\)

　　这两种情况都要求\(r<s_{m+1}\)

　　先看第一种情况。

　　枚举前面\(?\)的数量和\(m\)，要\(O(n^2)\)的时间。

　　后面的\(?\)可以任意取，但前面的不行。

　　考虑暴力枚举所有情况，然后拿\(s\)去和这个串做KMP。

　　如果前面匹配时有对应位置比\(s_i\)小的情况，那么显然是不合法的。

　　如果前面的\(?\)匹配完后\(s\)中的匹配长度不为\(0\)，那么\(s_1s_2\ldots s_m\)就不是第一次匹配了。（因为\(s\)是最小表示串，所以它的后缀一定大于整个串。）

　　设\(f_{i,j}\)为有\(i\)个\(?\)，从\(s_j\)开始匹配，匹配完后匹配长度为\(0\)的方案数。

　　如果这一位匹配，那么方案数就是\(f_{i-1,j+1}\)

　　如果不匹配，那么这一位肯定比\(s_j\)大，那就是\(('z'-s_j)f_{i-1,1}\)

\[f_{i,j}=f_{i-1,j+1}+('z'-s_j)f_{i-1,1}
\]

　　这样第一部分就做完了。

　　接下来看第二种情况。

　　枚举\(k,m\)，拿\(s\)去和\(s_{k+1}\ldots s_m\)跑KMP。

　　假设当前匹配长度为\(l\)。

　　但是这次在匹配完后有两种情况。

　　如果在\(r\)处匹配上了，方案数就是后面\(?\)部分的方案数。

　　如果失配了，那么有\(s_{l+1}<r<s_{m+1}\)（如果\(r<s_{l+1}\)，那么左旋\(k-l\)次就比\(s\)小了）。

　　第二部分也做完了。

　　做一次的时间复杂度是\(O(n^2)\)

　　但是要做很多次，时间复杂度还是\(O(n^2)\)的。

　　还有一点细节。如果\(s="abacab"\)，当要求的字符串的循环节长度为\(2\)的时候，后面有一部分\(s_{3\ldots 4}\)比第一部分\(s_{1\ldots 2}\)大，那么第一部分的所有循环同构串都是合法的。

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll p=1000000007;

ll fp(ll a,ll b)

{

    ll s=1;

    for(;b;b>>=1,a=a*a%p)

        if(b&1)

            s=s*a%p;

    return s;

}

int gcd(int a,int b)

{

    return b?gcd(b,a%b):a;

}

char s[1010];

int a[2010];

int n;

ll f[1010][1010];

int fail[2010];

ll pw[1010];

ll g[1010];

int chk(int x)

{

    int i;

    for(i=x+1;i<=n;i++)

        if(a[i]>a[(i-1)%x+1])

            return 1;

    return 0;

}

ll gao(int x)

{

    ll ans=0;

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

        for(int j=1;j<=x-i;j++)

            ans=(ans+f[i][1]*(a[j]-1)%p*pw[x-i-j])%p;

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

    {

        int k=0;

        for(int j=0;j<=x-1-i;j++)

        {

            for(;k&&a[j+i]!=a[k+1];k=fail[k]);

            if(j&&a[j+i]==a[k+1])

                k++;

            if(a[k+1]<a[j+i+1]-1)

                ans=(ans+(a[j+i+1]-a[k+1]-1)*f[x-1-i-j][1])%p;

            if(a[k+1]<=a[j+i+1]-1)

                ans=(ans+f[x-1-i-j][k+2])%p;

        }

    }

    return ans;

}

int check()

{

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

        a[i+n]=a[i];

    fail[1]=0;

    int j=0;

    for(int i=2;i<=2*n;i++)

    {

        while(j&&a[j+1]!=a[i])

            j=fail[j];

        if(a[j+1]==a[i])

            j++;

        fail[i]=j;

    }

    for(int i=1;i<2*n;i++)

        if(a[i+1]<a[fail[i]+1])

            return 0;

    return 1;

}

void solve()

{

    scanf("%s",s+1);

    n=strlen(s+1);

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

        a[i]=s[i]-'a'+1;

    pw[0]=1;

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

        pw[i]=pw[i-1]*26%p;

    for(int i=n;i>=1;i--)

    {

        if(i!=n&&a[i]>1)

            a[i]--;

        if(check())

            break;

        a[i]=26;

    }

    memset(f,0,sizeof f);

    f[0][1]=1;

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

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

        {

            f[i][j]=f[i-1][1]*(26-a[j])%p;

            f[i][j]=(f[i][j]+f[i-1][j+1])%p;

        }

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

        if(n%i==0)

        {

            g[i]=gao(i);

            if(chk(i))

            {

                if(i%(i-fail[i])==0)

                    g[i]+=i-fail[i];

                else

                    g[i]+=i;

            }

            g[i]%=p;

        }

    ll ans=0;

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

        ans=(ans+g[gcd(i,n)])%p;

    ans=ans*fp(n,p-2)%p;

    ans++;

    ans=(ans+p)%p;

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

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("string.in","r",stdin);

    freopen("string.out","w",stdout);

#endif

    int t;

    scanf("%d",&t);

    while(t--)

        solve();

    return 0;

}

相关文章