bzoj1009（kmp，dp，矩陣乘法，快速幂）

Description

　　阿申準備報名參加GT考試，準考證号為N位數X1X2….Xn(0<=Xi<=9),他不希望準考證号上出現不吉利的數字。

他的不吉利數學A1A2…Am(0<=Ai<=9)有M位，不出現是指X1X2…Xn中沒有恰好一段等于A1A2…Am. A1和X1可以為

Input

　　第一行輸入N,M,K.接下來一行輸入M位的數。 N<=10^9,M<=20,K<=1000

Output

　　阿申想知道不出現不吉利數字的号碼有多少種，輸出模K取餘的結果.

Sample Input

4 3 100

111

Sample Output

81

看上去很像容斥…

考慮dp

fi,j f i , j 表示前 i i 位，比對了jj位的方案數

考慮下一位，有可能繼續比對，有可能部分失陪，有可能全部失配

根據 next n e x t 數組構造轉移矩陣 快速幂優化即可

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i = linkk[x];i;i = e[i].n)
#define P pair<int,int>
#define Pil pair<int,ll>
#define Pli pair<ll,int>
#define Pll pair<ll,ll>
#define pb push_back 
#define pc putchar
#define file(k) memset(k,0,sizeof(k))
#define ll long long
int n , len , pp;
char s[];
int Next[];
struct martix{
    int f[][];
}G,A;
int read()
{
    int sum = ;char c = getchar();bool flag = true;
    while( c < '0' || c > '9' ) {if(c == '-') flag = false;c = getchar();}
    while( c >= '0' && c <= '9' ) sum = sum *  + c -  , c = getchar();
    if(!flag)  sum = -sum;
    return sum;
} 
void init()
{
    n = read();len = read();pp = read();
    scanf("%s",s+);
    int j = ;
    rep(i,,len)
    {
        while(j && s[j+] != s[i]) j = Next[j];
        if(s[j+] == s[i]) j++;
        Next[i] = j;
    }
    return;
}
bool vis[];
void make_martix()
{
    rep(i,,len-)
    {
        file(vis);
        int sum = ;
        if(!vis[s[i+] - '0']) 
        {
            G.f[i][i+]++;
            vis[s[i+] - '0'] = true;
            sum++;
        }
        int j = i;
        while(j)
        {
            j = Next[j];
            if(!vis[s[j+] - '0'])
            {
                G.f[i][j+]++;
                vis[s[j+] - '0'] = true;
                sum++;
            }
        }
        G.f[i][] =  - sum;
    }
    G.f[len][len] = ;
    A.f[][] = ;
    return;
}
void re(martix &now)
{
    rep(i,,len)
        rep(j,,len)
            now.f[i][j] = i==j?:;
    return;
}
martix mul(martix a,martix b,int n,int m,int p)//n*p 和 p*m
{
    martix ans;
    rep(i,,n)
        rep(j,,m)
        {
            ans.f[i][j] = ;
            rep(k,,p)
                ans.f[i][j] = (ans.f[i][j] + a.f[i][k] * b.f[k][j] % pp)%pp;   
        }
    return ans;
}
martix Pow(martix a,int k)
{
    martix now;
    re(now);
    while(k)
    {
        if(k & )
            now = mul(now , a , len , len , len);
        a = mul(a , a , len , len , len);
        k >>= ;
    }
    return now;
}
int main()
{
    init();
    make_martix();
    G = Pow(G,n);
    A = mul(A,G,,len,len);
    int ans = ;
    rep(i,,len-) ans = (ans + A.f[][i])%pp;
    printf("%d\n",ans); 
    return ;
}