bzoj 1009: [HNOI2008]GT考试 -- KMP+矩阵-白红宇

bzoj 1009: [HNOI2008]GT考试 -- KMP+矩阵

阅读量：5243 次

发布时间：2019-06-14

本文共 925 字，大约阅读时间需要 3 分钟。

1009: [HNOI2008]GT考试

Time Limit: 1 Sec Memory Limit: 162 MB

Description

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

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

Input

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

Output

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

Sample Input

4 3 100

111

Sample Output

HINT

设a[k][j]为k位后面加一个字母转移到j的方案数，于是：

我们发现k后面加一个字母转移到j可以用kmp实现。

这个式子是线性的，可以用矩阵优化。

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define inf 1000000007#define ll long long#define N 22#define F(i,r) for(i=0;i
            
             >=1; }}char s[N];int nxt[N],ans;int main(){ scanf("%d%d%d%s",&n,&m,&p,s+1); for(int i=2,j=0;i<=m;i++) { while(j&&s[i]!=s[j+1]) j=nxt[j]; if(s[j+1]==s[i]) j++; nxt[i]=j; } for(int i=0;i