bzoj1009 KMP+矩阵dp

时间：2024-11-11 17:35:38

https://www.lydsy.com/JudgeOnline/problem.php?id=1009

　阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(<=Xi<=),他不希望准考证号上出现不吉利的数字。

他的不吉利数学A1A2...Am(<=Ai<=)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为

题意

KMP我会，矩乘dp我也会，组合起来原本应该是双倍的快乐，为什么会这样(＞﹏＜)

看起来很像是一道AC自动机（KMP）的题目，N，M的数据范围很像快速矩阵幂，这就触及到我的知识盲区了

事实上确实如此，我们考虑一个最裸的线性dp

dp[i][j]表示这个串的前i位匹配到前j个字符的种数

对于每一位的递推事实上可以通过枚举0到9找到之后的最大匹配，从前面开始递推出答案。

找到最大匹配可以用kmp的next数组加速一下。

递推可以通过矩阵加速一下。由于只有最后M位数才会对下一位产生递推关系，所以我们只要建一个M * M的矩阵加速即可

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());

for(;isdigit(c);now=now*+c-'',c=getchar());return now;}

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = ;

const int INF = 0x3f3f3f3f;

int mod = 1e9 + ;

int N,M,K;

char str[maxn];

struct Mat{

    LL a[][];

    void init(){

        Mem(a,);

    }

}base,ans;

Mat operator * (Mat a,Mat b){

    Mat ans; ans.init();

    for(int i = ; i < M ; i ++){

        for(int j =  ;j < M; j ++){

            for(int k =  ; k < M ; k ++){

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

            }

        }

    }

    return ans;

}

Mat operator ^ (Mat a,int n){

    Mat ans; ans.init();

    for(int i =  ; i < M ; i ++) ans.a[i][i] = ;

    while(n){

        if(n & ) ans = ans * a;

        a = a * a;

        n >>= ;

    }

    return ans;

}

int nxt[maxn];

void KMP_Pre(char x[],int m,int *next){

    int i,j;

    j = next[] = -;

    i = ;

    while(i < m){

        while(j != - && x[i] != x[j]) j = next[j];

        next[++i] = ++j;

    }

}

int main()

{

    Sca3(N,M,mod); ans.init();

    scanf("%s",str); base.init();

    KMP_Pre(str,strlen(str),nxt);

    for(int i =  ; i < M; i ++){

        for(int j = '' ; j <= '' ; j ++){

            int k = i;

            while(str[k] != j && k) k = nxt[k];

            if(str[k] == j) k ++;

            base.a[i][k]++;

        }

    }

    LL sum = ;

    ans.a[][] = ;

    ans = ans * (base ^ N);

    for(int i =  ; i < M ; i ++) sum = (sum + ans.a[][i]) % mod;

    Prl(sum);

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}

相关文章