Description

题库链接

问你长度为 \(n\) 的可含前导零的数字串中，不含长度为 \(m\) 的子串 \(X\) 有多少个，取模。

\(1\leq n\leq 10^9,1\leq m\leq 20\)

Solution

一个显然的 \(DP\) ，就是令 \(f_{i,j}\) 表示已经生成出的串长为 \(i\) 位，后 \(j\) 位与 \(X\) 串的前 \(j\) 位匹配的方案数。

那么 \(f_{i,j}=\sum_{x=1}^m f_{i-1,x}\cdot[x 可以转移到 j]\) 。

由于 \(n\) 过大，我们可以用矩阵加速。在构造矩阵时可以用 \(KMP\) 中的 \(next\) 数组的思想来简化计算过程，省去了暴力的计算。

Code

//It is made by Awson on 2018.3.14

#include <bits/stdc++.h>

#define LL long long

#define dob complex<double>

#define Abs(a) ((a) < 0 ? (-(a)) : (a))

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

#define writeln(x) (write(x), putchar('\n'))

#define lowbit(x) ((x)&(-(x)))

using namespace std;

void read(int &x) {

    char ch; bool flag = 0;

    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());

    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());

    x *= 1-2*flag;

}

void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }

void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }

int n, m, k, nxt[25];

char ch[25];

struct mat {

    int a[25][25];

    mat() {memset(a, 0, sizeof(a)); }

    mat operator * (const mat &b) const {

    mat ans;

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

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

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

            ans.a[i][j] = (ans.a[i][j]+a[i][p]*b.a[p][j]%k)%k;

    return ans;

    }

}S, T;

void build() {

    for (int i = 2; i <= m; i++) {

    int j = nxt[i-1];

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

    if (ch[j+1] == ch[i]) nxt[i] = j+1;

    }

    for (int i = 1; i <= m; i++) {

    for (char j = '0'; j <= '9'; j++) {

        if (j == ch[i]) continue;

        int p = nxt[i-1];

        while (p && j != ch[p+1]) p = nxt[p];

        if (j == ch[p+1]) ++p; ++T.a[i-1][p];

    }

    ++T.a[i-1][i];

    }

}

mat quick_pow(mat a, int b) {

    mat ans = a; --b;

    while (b) {

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

    b >>= 1, a = a*a;

    }

    return ans;

}

void work() {

    read(n), read(m), read(k); scanf("%s", ch+1); build();

    S.a[0][0] = 1; S = S*quick_pow(T, n); int ans = 0;

    for (int i = 0; i < m; i++) ans += S.a[0][i]; writeln(ans%k);

}

int main() {

    work(); return 0;

}