[bzoj1009][HNOI2008]GT考试

Description

阿申准备报名参加\(GT\)考试，准考证号为\(N\)位数\(X_1X_2...X_n\),他不希望准考证号上出现不吉利的数字。
他的不吉利数学\(A_1A_2...A_m\)有\(M\)位，不出现是指\(X_1X_2....X_n\)中没有恰好一段等于\(A_1A_2...A_m\). \(A_1,X_1\)可以为\(0\).

Input

第一行输入\(N,M,K\).接下来一行输入\(M\)位的数。

Output

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

Sample Input

4 3 100 
111

Sample Output

81

HINT

\(0\;\leq\;X_i,A_i\;\leq\;9,N\;\leq\;10^9,M\;\leq\;20,K\;\leq\;1000\)

Solution

\(f[i][j]\)表示已填好前\(i\)位,此时匹配到\(A_j\)的方案数.

\(g[i][j]\)表示现在匹配到\(A_i\),填下一个数后匹配到\(A_j\)的方案数.

\(f[i][j]=\sum_{k=0}^{m-1}f[i-1][k]\;\times\;g[k][j]\).

\(g[i][j]\)可用\(kmp\)预处理出.

\(n=10^9\),矩乘优化即可.
\(\;\;\;\;\;\begin{bmatrix}f[i][0]&f[i][1]&...&f[i][m-1]\end{bmatrix}\)
\(\\\)
\(=\begin{bmatrix}g[0][0]&g[0][1]&...&g[0][m-1]\\g[1][0]&g[1][1]&...&g[1][m-1]\\...&...&...&...\\g[m-1][0]&g[m-1][1]&...&g[m-1][m-1]\end{bmatrix}\times\begin{bmatrix}f[i-1][0]&f[i-1][1]&...&f[i-1][m-1]\end{bmatrix}\)

#include 
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#include
#define M 25
using namespace std;
struct matrix{
    int a[M][M],n,m;
}a,b;
int g[M][M],nxt[M],n,m,k,ans;
char c[M];
inline void get_next(){
    for(int i=2,j=0;i<=m;++i){
        while(j&&c[i]!=c[j+1]) j=nxt[j];
        j+=(c[i]==c[j+1]);
        nxt[i]=j;
    }
    b.n=b.m=m;
    for(int i=0,l;i>=1;
    }
    return c;
}
inline void init(){
    scanf("%d%d%d%s",&n,&m,&k,c+1);
    if(!m){
        ans=1;
        for(int i=1;i<=n;++i)
            ans=ans*10%k;
        printf("%d\n",ans);return;
    }
    get_next();
    a.n=1;a.m=m;
    a.a[0][0]=1;
    a=mul(a,po(b,n));
    for(int i=0;i