Description：

求长为 $n$ 的，不包含另一个长为 $m$ 的数字，可以有前导零的数字有多少。

$1\le n \le 10^9$ $1\le m \le 20$

Solution：

看上去是一个数位 $DP$ ， $10^9$ 的范围想到矩阵加速，用 $KMP$ 预处理出从 $m$ 的第 $i$ 位后加一个数字 $j$ 后能到达 $m$ 的位置 $p[i][j]$ ，就是不断跳 $nxt$ 直到下一个数字为 $j$ 或跳到 $0$ ，于是就可以矩阵加速了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,mod;

#define MAXL 21

int get()

{

    char c = getchar();

    while(!isdigit(c))c = getchar();

    return c - '0';

}

int t[MAXL];

int nxt[MAXL];

void makenext()

{

    nxt[1] = 0;

    for(int i = 2,j = 0;i <= m;++i)

    {

        while(t[i] != t[j + 1] && j != 0)j = nxt[j];

        if(t[i] == t[j + 1])++j;

        nxt[i] = j;

    }

    return;

}

int p[MAXL][10];

struct matrix

{

    int w[MAXL][MAXL];

    matrix(){memset(w,0,sizeof(w));}

    friend matrix operator * (matrix a,matrix b)

    {

        matrix c;

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

        {

            for(int j = 0;j < m;++j)

            {

                c.w[i][j] = 0;

                for(int k = 0;k < m;++k)

                {

                    c.w[i][j] = (c.w[i][j] + a.w[i][k] * b.w[k][j] % mod) % mod;

                }

            }

        }

        return c;

    }

    friend matrix operator ^ (matrix a,int b)

    {

        matrix res = a;--b;

        while(b > 0)

        {

            if(b & 1)res = res * a;

            a = a * a;

            b = b >> 1;

        }

        return res;

    }

}f;

int main()

{

    scanf("%d%d%d",&n,&m,&mod);

    for(int i = 1;i <= m;++i)t[i] = get();

    makenext();

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

    {

        for(int c = 0;c <= 9;++c)

        {

            int j = i;

            while(t[j + 1] != c && j != 0)j = nxt[j];

            if(t[j + 1] == c)++j;

            p[i][c] = j;

        }

    }

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

    {

        for(int k = 0;k <= 9;++k)

        {

            if(p[i][k] < m)++f.w[i][p[i][k]];

        }

    }

    matrix res = f ^ n;

    int ans = 0;

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

    {

        ans = (ans + res.w[0][i]) % mod;

    }

    cout << ans << endl;

    return 0;

}