【BZOJ1009】【HNOI2008】GT考试

这是一个值得庆祝的时刻！

BZOJ rank终于进2000辣！

另外这道题的题号还是我的生日！

这道题还是挺难的

首先我们可以想出一种dp的思路

用f[i][j]表示到前i位匹配到不jiry串第j位的方案数

那么转移就是枚举下一位c，假设加上了这个c之后匹配到第k位，那么f[i+1][k]+=f[i][j]。

f[0][0]=1，f[0][j]=0(j≠0)

特判i为m时强制只能转移到m。

判断加上c后到匹配第几位可以用KMP预处理。

考虑优化，可以发现转移和i无关，那么用a[j][k]表示匹配到第j位能够转移到匹配到第k位的数字c的取值数

那么用单位矩阵*a矩阵的n次方，也就是a矩阵自乘n次，答案即为

$$\sum_{i=0}^{m-1}a[0][i]$$

矩阵快速幂套一下即可。

总而言之，这道题还是很综合的。

// <1009.cpp> - 05/20/16 18:13:22
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return res;
}
int g1(){
    char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    return ch-'0';
}
const int MAXN=30;
const int INF=1e9;
int m,MOD;
int s[MAXN],next[MAXN];
struct matrix{
    int a[MAXN][MAXN];
    matrix(){memset(a,0,sizeof(a));}
    int* operator [](int x){return a[x];}
    matrix operator *(matrix b){
        matrix ans;
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                for(int k=0;k<m;k++)(ans[i][j]+=a[i][k]*b[k][j])%=MOD;
        return ans;
    }
}a;
int main(){
    int n=gi();m=gi();MOD=gi();
    for(int i=1;i<=m;i++)s[i]=g1();
    int o=0;
    for(int i=2;i<=m;i++){
        while(o&&s[i]!=s[o+1])o=next[o];
        if(s[i]==s[o+1])o++;
        next[i]=o;
    }
    for(int i=0;i<m;i++)
        for(int now=0;now<10;now++){
            int o=i;
            while(o&&now!=s[o+1])o=next[o];
            a[i][o+(now==s[o+1])]++;
        }
    matrix ans;ans[0][0]=1;
    while(n){
        if(n&1)ans=ans*a;
        a=a*a;
        n>>=1;
    }
    int ANS=0;
    for(int i=0;i<m;i++)ANS=(ANS+ans[0][i])%MOD;
    printf("%d",ANS);
    return 0;
}

// <1009.cpp> - 05/20/16 18:13:22

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0;char ch=getchar();

while(ch>'9'||ch<'0')ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return res;

}

int g1(){

char ch=getchar();

while(ch>'9'||ch<'0')ch=getchar();

return ch-'0';

}

const int MAXN=30;

const int INF=1e9;

int m,MOD;

int s[MAXN],next[MAXN];

struct matrix{

int a[MAXN][MAXN];

matrix(){memset(a,0,sizeof(a));}

int* operator [](int x){return a[x];}

matrix operator *(matrix b){

matrix ans;

for(int i=0;i<m;i++)

for(int j=0;j<m;j++)

for(int k=0;k<m;k++)(ans[i][j]+=a[i][k]*b[k][j])%=MOD;

return ans;

}

}a;

int main(){

int n=gi();m=gi();MOD=gi();

for(int i=1;i<=m;i++)s[i]=g1();

int o=0;

for(int i=2;i<=m;i++){

while(o&&s[i]!=s[o+1])o=next[o];

if(s[i]==s[o+1])o++;

next[i]=o;

}

for(int i=0;i<m;i++)

for(int now=0;now<10;now++){

int o=i;

while(o&&now!=s[o+1])o=next[o];

a[i][o+(now==s[o+1])]++;

}

matrix ans;ans[0][0]=1;

while(n){

if(n&1)ans=ans*a;

a=a*a;

n>>=1;

}

int ANS=0;

for(int i=0;i<m;i++)ANS=(ANS+ans[0][i])%MOD;

printf("%d",ANS);

return 0;

}