Description

阿申准备报名参加 GT 考试, 准考证号为 \(n\) 位数 \(x_1 x_2 \ldots x_n (0 \leq x_i \leq 9)\), 他不希望准考证号上出现不吉利的数字.

他的不吉利数字 $a_1 a_2 a_m (0 a_i 9) 有 \(m\) 位, 不出现是指 \(x_1 x_2 \ldots x_n\) 中没有恰好一段等于 \(a_1 a_2 \ldots a_m\).\(a_1\) 和 \(x_1\) 可以为 \(0\).

Input

第一行输入 \(n, m, k\). 接下来一行输入 \(m\) 位的数.

Output

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

Sample Input

4 3 100
111

Sample Output

81

Data Range

对于所有的数据, 满足:\(n \leq 10^9, m \leq 20, k \leq 1000\)

Explanation

膜一发黄学长题解:

矩阵乘法的题题解写起来都十分麻烦......

而且很多东西只能意会......

\(f[i, j]\) 表示前 \(i\) 个准考证号匹配到不吉利串第 \(j\) 个的方案

然后你需要把一个答案矩阵 \(f[i, j]\) 转移到 \(f[i+1, j]\)

举个例子, 样例, 比如当前匹配到了第 \(2\) 位, 也就是说前 \(i\) 位的结尾是 \(11\)

对于第 \(i+1\) 个字符, 如果是 \(1\) 的话, 接着匹配到不吉利串第 \(3\) 位, 不是 \(1\) 的话 就匹配到第 \(0\) 位了

也就是说前 \(i\) 位匹配到了不吉利串 \(j\) 位, 加入 \(i+1\) 这个字符, 有不同情况, 有一些会转移到 \(j+1\), 一些会转移到其他的, 写成一些形如 \(f[i+1, k] += f[i, j]\) 的式子......

\[f[i+1, 3] += f[i, 2]\]

\[f[i+1, 0] += f[i, 2]\]

即枚举 \(i+1\) 可能出现的字符, 然后看 \(n\) 个 \(f[i, j]\) 分别转移到哪去, 就在转移矩阵 的这个转移路径上+1

按照这个思路用 kmp 写出转移矩阵, 事实上暴力应该就行了

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxm = 25;
lli modr;

struct Matrix {
    int sz; lli dat[maxm][maxm];
    Matrix(void) { sz = 0; memset(dat, 0, sizeof(dat)); }
    Matrix(int sz_) { sz = sz_; memset(dat, 0, sizeof(dat)); }
};
Matrix operator * (Matrix a, Matrix b)
{
    Matrix c(a.sz);
    rep(i, 0, a.sz) rep(j, 0, b.sz) {
        c.dat[i][j] = 0;
        rep(k, 0, a.sz)
            c.dat[i][j] = (c.dat[i][j] +
                a.dat[i][k] * b.dat[k][j]) % modr;
    }
    return c;
}
Matrix operator ^ (Matrix b, lli pw)
{
    Matrix a(b.sz);
    for (int i = 0; i < a.sz; i++)
        a.dat[i][i] = 1;
    while (pw > 0) {
        if (pw & 1 == 1)
            a = a * b;
        b = b * b;
        pw >>= 1;
    }
    return a;
}

lli n; int m;
char str[maxm];
int pre[maxm]; // KMP-Purposes only

int main(int argc, char** argv)
{
    scanf("%lld%d%lld", &n, &m, &modr);
    scanf("%s", str + 1);
    for (int i = 1; i <= m; i++)
        str[i] -= '0';
    // Preprocessing prefix function with KMP algorithm
    for (int i = 2, j = 0; i <= m; i++) {
        while (j > 0 && str[j + 1] != str[i])
            j = pre[j];
        if (str[j + 1] == str[i])
            j++;
        pre[i] = j;
    }
    // Constructing matrix of migration
    Matrix mov(m);
    for (int i = 0; i < m; i++)
        for (int j = 0; j <= 9; j++) {
            int t = i;
            while (t > 0 && str[t + 1] != j)
                t = pre[t];
            if (str[t + 1] == j)
                t++;
            if (t != m)
                mov.dat[t][i] = (mov.dat[t][i] + 1) % modr;
        }
    // Getting result.
    Matrix mat = mov ^ n;
    int sum = 0;
    for (int i = 0; i < m; i++)
        sum = (sum + mat.dat[i][0]) % modr;
    printf("%d\n", sum);
    return 0;
}