bzoj 1009 GT考試（dp+KMP）

我的算法和大部分的題解算法有些不同。。。。算法來源參照http://acm.hdu.edu.cn/showproblem.php?pid=3689

那麼這道題的思想可以轉為求，當準考證号的長度為i時不吉利數字比對的長度為j，那麼設f[i][j]表示目前狀态的方案數，則有轉移

f[i][kmp(j-1,k)]+=f[i-1][j-1];
           

j為長度，因為kmp是從0開始的，是以他的位置為j-1，即求出下一個字元為k時的比對位置。那麼最後求出 

 即可

暴力代碼

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
char ss[25];
int nxt[25],l;
int f[1005][25];
void gett()
{
    int t1=0,t2=-1;
    nxt[0]=-1;
    while(t1<l)
    {
        if(t2==-1||ss[t1]==ss[t2])
        {
            t1++,t2++;
            nxt[t1]=t2;
        }else 
        {
            t2=nxt[t2];
        }
    }
}
int kmp(int q,int w)
{
    while((q!=-1)&&((ss[q]-'0')!=w))
    {
        q=nxt[q];
    }
    return q+1;
}
int main()
{
    int n,m,K;
    scanf("%d%d%d",&n,&m,&K);
    scanf("%s",ss);
    l=strlen(ss);
    gett();
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=l;j++)
        {
            for(int k=0;k<=9;k++)
            {
                f[i][kmp(j-1,k)]+=f[i-1][j-1]%K;
                f[i][kmp(j-1,k)]%=K;
            }
        }
    }
    int ans=0;
    for(int j=0;j<l;j++)
    {
        ans+=f[n][j];
        ans%=K;
    }
    printf("%d",ans);
    return 0;
}
           

而我們發現每次轉移的kmp都是固定的，是以可以矩陣乘法求出。

代碼

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
char ss[25];
int nxt[25],l;
int n,m,K;
void gett()
{
    int t1=0,t2=-1;
    nxt[0]=-1;
    while(t1<l)
    {
        if(t2==-1||ss[t1]==ss[t2])
        {
            t1++,t2++;
            nxt[t1]=t2;
        }else 
        {
            t2=nxt[t2];
        }
    }
}
int kmp(int q,int w)
{
    while((q!=-1)&&((ss[q]-'0')!=w))
    {
        q=nxt[q];
    }
    return q+1;
}
struct node 
{
    int f[30][30];
}dp,zy;
node operator *(node a,node b)
{
    node ans1;
    memset(ans1.f,0,sizeof(ans1.f));
    for(int i=0;i<=25;i++)
    {
        for(int j=0;j<=25;j++)
        {
            for(int k=0;k<=25;k++)
            {
                ans1.f[i][j]+=a.f[i][k]*b.f[k][j]%K;
                ans1.f[i][j]%=K;
            }
        }
    }
    return ans1;
}
void ksm(node a,int b)
{
    while(b)
    {
        if(b%2==1)
        {
            dp=a*dp;
        }
        b=b/2;
        a=a*a;
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&K);
    scanf("%s",ss);
    l=strlen(ss);
    gett();
    for(int j=1;j<=l;j++)
    {
        for(int k=0;k<=9;k++)
        {
            zy.f[kmp(j-1,k)][j-1]++;
        }
    }
    dp.f[0][0]=1;
    ksm(zy,n);
    int ans=0;
    for(int i=0;i<l;i++)
    {
        ans+=dp.f[i][0];
        ans%=K;
    }
    printf("%d",ans);
    return 0;
}