M_sea

洛谷3193 [HNOI2008]GT考试
LuoguBZOJ分析先不管$n\leq10^9$。设$f[i][j]$表示前$i$位,匹配不吉利数字匹配到了第$...
扫描右侧二维码阅读全文
08
2019/01

洛谷3193 [HNOI2008]GT考试

Luogu

BZOJ

分析

先不管$n\leq10^9$。

设$f[i][j]$表示前$i$位,匹配不吉利数字匹配到了第$j$位的方案数。

然后$\large ans=\sum\limits_{i=0}^{m-1}f[n][i]$。

发现不好转移。设$g[i][j]$表示不吉利数字中前$i$位转移到前$j$位的方案数。

可以得到:$\large f[i][j]=\sum\limits_{k=0}^{m-1}f[i-1][k]\times g[k][j]$

考虑$g$怎么求出来。按照$\mathrm{\color{black}{y}\color{red}{ch}}$的说法,“用KMP搞一下下一位匹配到哪个字符”即可。

然后,转移显然可以用矩阵快速幂优化,于是就可以过了。

复杂度不知道。反正能过

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=20+10;

int n,m,MOD;
char a[MAXN];

int nxt[MAXN];
int g[MAXN][MAXN];

inline void getNext() {
    nxt[0]=-1;
    for (re int i=1;i<=m;++i) {
        int j=nxt[i-1];
        while (j!=-1&&a[j+1]!=a[i]) j=nxt[j];
        nxt[i]=j+1;
    }
}

inline void KMP() {
    nxt[0]=0;
    for (re int i=0;i<m;++i)
        for (re int j='0';j<='9';++j) {
            int k=i;
            while (a[k+1]!=j&&k>0) k=nxt[k];
            if (a[k+1]==j) ++k;
            if (k<m) ++g[i][k];
        }
}

struct Matrix {
    int s[MAXN][MAXN];
    Matrix() { memset(s,0,sizeof(s)); }
} F,G;

inline Matrix Mul(Matrix a,Matrix b) {
    Matrix c;
    for (re int i=0;i<m;++i)
        for (re int j=0;j<m;++j)
            for (re int k=0;k<m;++k)
                c.s[i][j]=(c.s[i][j]+a.s[i][k]*b.s[k][j])%MOD;
    return c;
}

inline Matrix FastPow(Matrix a,int b) {
    Matrix c;
    for (re int i=0;i<m;++i) c.s[i][i]=1;
    for (;b;b>>=1,a=Mul(a,a))
        if (b&1) c=Mul(c,a);
    return c;
}

int main() {
    n=read(),m=read(),MOD=read(); scanf("%s",a+1);
    getNext(); KMP();
    for (re int i=0;i<=m;++i)
        for (re int j=0;j<=m;++j)
            G.s[i][j]=g[i][j];
    F.s[0][0]=1;
    F=Mul(F,FastPow(G,n));
    int ans=0;
    for (re int i=0;i<m;++i) ans=(ans+F.s[0][i])%MOD;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 05 : 44 PM

2 条评论

  1. smy

    不要g数组啊qwq

    1. M_sea
      @smy

      不会您那种做法qwq

发表评论 取消回复