bzoj 1009 [HNOI2008]GT考试

Description

　　阿申准备报名参加GT考试，准考证号为N位数X1X2….Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2…Am(0<=Ai<=9)有M位，不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为0

Input

　　第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000

Output

　　阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.

Sample Input

4 3 100

111

Sample Output

81

题解

这题可以用kmp做的，但是ac自动机就是kmp的多串情况。

其实部分分就是刚才那道bzoj1030。dp方程状态都一模一样

#include <cstdio>
#include <cstring>
#include <queue>
#define N 1010
using namespace std;
int n,m,sz,mod,k,root,ans,ch[N][26],is_end[N],fail[N],pos[N],f[N][N];
char s[N],t[N];
void insert(char s[])
{
    int len=strlen(s+1),now=root;
    for (int i=1;i<=len;now=ch[now][s[i]-'0'],i++)
        if (!ch[now][s[i]-'0']) ch[now][s[i]-'0']=++sz;
    is_end[now]=1;
}
void make_fail()
{
    queue<int>que;
    for (int i=0;i<=9;i++)
        if (ch[root][i]) que.push(ch[root][i]);
    while(!que.empty())
    {
        int now=que.front();que.pop();
        for (int i=0;i<=9;i++)
            if (ch[now][i])
                is_end[ch[now][i]]|=is_end[ch[fail[now]][i]],
                fail[ch[now][i]]=ch[fail[now]][i],
                que.push(ch[now][i]);
            else
                ch[now][i]=ch[fail[now]][i];
    }
}
main()
{
    scanf("%d%d%d",&n,&m,&mod);
    scanf("%s",s+1);
    insert(s);
    make_fail();
    f[0][root]=1;
    for (int i=1;i<=n;i++)
        for (int j=0;j<=sz;j++)
            for (int k=0;k<=9;k++)
                if (!is_end[ch[j][k]])
                    (f[i][ch[j][k]]+=f[i-1][j])%=mod;
    for (int i=0;i<=sz;i++)
        (ans+=f[n][i])%=mod;
    printf("%d\n",ans%mod);
}

这就是40分。剩下的怎么做呢？一看数据范围就知道是矩乘

发现这个式子是可以矩乘的，直接在矩阵里面把所有父亲和儿子连下就好了。

#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
#define N 2010
using namespace std;
int n,m,sz,mod,k,root,ans,ch[N][26],is_end[N],fail[N],f[N][N];
char s[N],t[N];
struct matrixs
{
    int m[25][25];
    void clear(){memset(m,0,sizeof m);}
    matrixs operator * (const matrixs &a) const
    {
        matrixs ans={};
        for (int i=1;i<=n;i++)
            for (int k=1;k<=n;k++)
                if (m[i][k])
                    for (int j=1;j<=n;j++)
                        ans.m[i][j]=(ans.m[i][j]+(ll)m[i][k]*a.m[k][j])%mod;
        return ans;
    }
    matrixs matrix_pow(ll p)
    {
        matrixs ans,a=(*this);ans.clear();
        for (int i=1;i<=n;i++) ans.m[i][i]=1;
        for (;p;a=a*a,p>>=1)
            if (p&1) ans=ans*a;
        return ans;
    }
};
void insert(char s[])
{
    int len=strlen(s+1),now=root;
    for (int i=1;i<=len;now=ch[now][s[i]-'0'],i++)
        if (!ch[now][s[i]-'0']) ch[now][s[i]-'0']=++sz;
    is_end[now]=1;
}
void make_fail()
{
    queue<int>que;
    for (int i=0;i<=9;i++)
        if (ch[root][i]) que.push(ch[root][i]);
    while(!que.empty())
    {
        int now=que.front();que.pop();
        for (int i=0;i<=9;i++)
            if (ch[now][i])
                is_end[ch[now][i]]|=is_end[ch[fail[now]][i]],
                fail[ch[now][i]]=ch[fail[now]][i],
                que.push(ch[now][i]);
            else
                ch[now][i]=ch[fail[now]][i];
    }
}
main()
{
    scanf("%d%d%d%s",&n,&m,&mod,s+1);
    insert(s);
    make_fail();
    matrixs m;m.clear();
    int t=n;n=sz+1;
    for (int i=0;i<=sz;i++)
        for (int j=0;j<=9;j++)
            if (!is_end[ch[i][j]])
                m.m[ch[i][j]+1][i+1]++;
    matrixs an=m.matrix_pow(t);
    int ans=0;
    for (int i=1;i<=n;i++)
        ans=(ans+an.m[i][1])%mod;
    printf("%d\n",ans);
}