【矩阵加速】【数论】【KMP】[BZOJ1009][HNOI2008]GT考试

题目描述

Description

阿申准备报名参加GT考试,准考证号为N位数X1X2….Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2…Am(0<=Ai<=9)有M位,不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为0

Input

第一行输入N,M,K.接下来一行输入M位的数。 100%数据N<=10^9,M<=20,K<=1000 40%数据N<=1000 10%数据N<=6

Output

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

Sample Input

4 3 100
111

Sample Output

81

题目分析

首先我们令 dp(i,j) 表示当前我们枚举到第 i 位的时候我们枚举的后缀最长和不吉利的字符串的前缀已经匹配了 j 个的时候的方案数量,那么我们的答案就是

i=0m1dp(n,i)
那么我们可以发现我们令 p(i,j) 表示从不吉利的字符串第 i 个字符后添加一个数字就可以从 i 个匹配变成 j 个匹配的可以填写的数字的个数那么我们显然有
dp(i,j)=k=0m1(dp(i1,k)×p(k,j))
那么我们的p显然可以进行预处理,那么我们发现 p 是可以表示成一个矩阵的同时我们发现 dp 也可以表示成一个矩阵那么我们显然有
DPi=DPi1×P
那么我们就有
DPn=DPn1×P=DP0×Pn
使用矩阵加速进行优化

代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 22;
int MOD, Fail[MAXN+10];
char s[MAXN+10];
struct Matrix {
    int Ma[MAXN+10][MAXN+10], n, m;
    void Clear(int u, int un=0, int um=0){
        n = un, m = um;
        for(int i=0;i<un;i++)
            for(int j=0;j<um;j++)
                Ma[i][j] = 0;
        if(u) for(int i=0;i<un;i++)
            Ma[i][i] = 1;
    }
    Matrix operator* (const Matrix& ma) {
        Matrix ret ;
        ret.Clear(0, n, m);
        for(int i=0;i<n;i++){
            for(int j=0;j<ma.m;j++){
                for(int k=0;k<ma.n;k++){
                    ret.Ma[i][j] += Ma[i][k] * ma.Ma[k][j];
                    ret.Ma[i][j] %= MOD;
                }
            }
        }
        return ret;
    }
};
Matrix Mpow(Matrix m, int p){
    Matrix ret;
    if(p == 0){
        ret.Clear(1, 2, 2);
        return ret;
    }else if(p == 1) return m;
    ret = Mpow(m, p/2);
    if(p%2 == 0) return ret * ret;
    return (ret * ret) * m;
}
int main(){
    int n, m;
    scanf("%d%d%d", &n, &m, &MOD);
    scanf("%s", s+1);
    Matrix mtr;
    mtr.Clear(0, m, m);
    mtr.Ma[0][0] = 9;
    mtr.Ma[0][1] = 1;
    for(int i=1;i<m;i++){
        int us = Fail[i];
        while(us){
            if(s[us+1] == s[i+1])
                break;
            us = Fail[us];
        }
        if(s[us+1] == s[i+1])
            Fail[i+1] = us+1;
        else Fail[i+1] = 0;
        for(int j=0;j<=9;j++){
            int u = i;
            while(u&&s[u+1] != j+'0') u = Fail[u];
            if(s[u+1] == j+'0') mtr.Ma[i][u+1] = (mtr.Ma[i][u+1] + 1) % MOD;
            else mtr.Ma[i][0] = (mtr.Ma[i][0] + 1) % MOD;
        }
    }
    Matrix ans = Mpow(mtr, n);
    int anst = 0;
    for(int i=0;i<m;i++)
        anst = (anst + ans.Ma[0][i]) % MOD;
    printf("%d\n", (anst+MOD)%MOD);

    return 0;
}
相关文章
相关标签/搜索