Description

阿申准备报名参加 GT 考试，准考证号为 $N$ 位数 $X_1,X_2…X_n(0\le X_i\le9)$，他不希望准考证号上出现不吉利的数字。 他的不吉利数字 $A_1,A_2…A_m(0\le A_i\le 9)A_1,A_2…A_m(0≤A_i≤9)$ 有 $M$ 位，不出现是指 $X_1,X_2…X_n$ 中没有恰好一段等于 $A_1,A_2…A_m$，$A_1$ 和 $X_1$ 可以为 $0$。

Solution

我过的挺玄学。

先考虑 DP。$f_{i,j}$​ 表示准考证前 $i$​ 位数未出现不吉利数字，且当前已经与不吉利数字匹配 $j$​​ 位（即后 $j$ 位与不吉利数字前 $j$ 位相同）的方案数。

一看就是个 KMP，构建出 $\text{fail}$​ 数组，又发现 $n\leq10^9$，往矩阵快速幂的方面去靠一靠。

发现当已经匹配 $p$ 位时，下一位有 $9$ 种选择，于是枚举这九种选择，利用 $\text{fail}$ 数组，可以快速转移到选择之后匹配到第几位。

于是发现这是个刷表转移，把这个刷表转成矩阵就成为了初始矩阵。

于是快速幂一下就做完了。

但要注意构造矩阵时的细节。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using std::cout;
using std::endl;

const int maxn = 110, maxm = 22;
int mod;
int n, m, k;

struct matrix
{
    int n, m;
    long long a[maxn][maxn];
    matrix() : n(0), m(0) { memset(a, 0, sizeof(a)); }
    matrix(int _n, int _m) : n(_n), m(_m) { memset(a, 0, sizeof(a)); }
    matrix(int _n, int _m, long long _a[maxn][maxn]) : n(_n), m(_m)
    {
        for (int i = 1; i <= _n; i++)
            for (int j = 1; j <= _m; j++)
                a[i][j] = _a[i][j];
    }
    matrix operator*(const matrix b)
    {
        matrix res(n, b.m);
        for (int i = 1; i <= n; i++)
            for (int k = 1; k <= m; k++)
                for (int j = 1; j <= b.m; j++)
                    res.a[i][j] += a[i][k] * b.a[k][j] % mod, res.a[i][j] %= mod;
        return res;
    }
    void print()
    {
        for (int i = 1; i <= n; i++, puts(""))
            for (int j = 1; j <= m; j++)
                printf("%lld ", a[i][j]);
    }
    matrix qpow(int x)
    {
        return qpow(*this, x);
    }
    matrix qpow(matrix a, int x)
    {
        matrix res = a;
        x--;
        for (; x; x >>= 1)
        {
            if (x & 1)
                res = res * a;
            a = a * a;
        }
        return res;
    }
} base;

char s[maxm];
int fail[maxm];
int a[maxm][maxm];

void get_fail()
{
    for (int i = 2, j = 0; i <= m; i++)
    {
        while (j && s[j + 1] != s[i])
            j = fail[j];
        if (s[j + 1] == s[i])
            j++;
        fail[i] = j;
    }
}

void init()
{
    for (int i = 1; i <= m; i++)
    {
        for (char num = '0'; num <= '9'; num++)
        {
            int j = i - 1;
            while (j && s[j + 1] != num)
                j = fail[j];
            if (s[j + 1] == num)
                j++;
            if (j != m)
                base.a[i][j + 1]++;
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &mod);
    scanf("%s", s + 1);
    get_fail();
    init();
    base.n = m, base.m = m;
    //base.print();
    matrix ans = base.qpow(n);
    long long res = 0;
    //ans.print();
    for (int i = 1; i <= m; i++)
        res += ans.a[1][i], res %= mod;
    printf("%lld\n", res);
}