[HNOI2008]GT考试

发表于 | 分类于

题目

阿申准备报名参加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位的数。 N<=10^9,M<=20,K<=1000

OUTPUT

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

SAMPLE

INPUT

4 3 100
111

OUTPUT

81

解题报告

这道题一开始真心没有什么思路，后来我跟两个dalao一起商（luan）谈（gao）了一个来小时，终于搞了出来= =

首先，我们我们考虑两个串（从短到长）
第一个串为不断增加的准考证号，第二个串为不吉利的号码，第一个串的后缀与第二个串的前缀为重复部分，那么我们很容易得出递推关系

先扯出来，考虑两个集合，一个集合为不吉利的号码，一个集合为吉利的号码。我们只考虑后缀（正确性显然，因为长度长的串一定是由长度短的串递推过来的，所以如果前面有不吉利串，一定被前面的串卡掉了），当后缀包含了m个不吉利串，该串一定是不吉利的。那么，后缀包含0~m-1个不吉利串的前缀的串一定是吉利的。所以，我们把求不吉利的串 转化为 求 后缀包含不吉利串0~m-1 的 串 的 方案数

然而与字符串有啥关系？
考虑这样一个不吉利串

123124

当你的后缀带了2时，你怎么知道你的后几位是12还是12312？所以，加一位不吉利数不代表直接在后面加了一位。

那么，问题来了，如何表示这些奇（chun）奇（de）怪（bu）怪（xing）的转移？
考虑一个递推矩阵，设dp[i][j]为第i个号码匹（zhuan）配（yi）到第j个不吉利数字的方案数，设a[k][i]为k位后加一个数转移到j的方案数，我们可以轻易的得出递推关系：
dp[i][j]=∑dp[i-1][k]*a[k][j]
用KMP构造初始矩阵，矩阵快速幂得到递推结果。

为什么是矩阵快速幂？
这个问题很简单。我们知道，矩阵乘是这样写的：

1
2
3
4
5
6
7
8
9
10
martrix tmp;
for(int i=0;i<n;i++)
	for(int j=0;j<n;j++){
		tmp.data[i][j]=0;
		for(int k=0;k<n;k++){
			tmp.data[i][j]+=(a.data[i][k]*b.data[k][j]);
			tmp.data[i][j]%=mod;
		}
	}
return tmp;

那么问题就简单起来了，考虑一个3*3的初始矩阵，第i行，第j列表示从第i位加一个数字转移到第j为数字的方案数，那么以该矩阵的平方的第一行第一列的数为例，（设初始矩阵为a，该矩阵为x）：
x[1][1]=a[1][1]×a[1][1]+a[1][2]×a[2][1]+a[1][3]×a[3][1];
因为是平方得到的矩阵，所以代表了转移两步的状态，我们知道，x[1][1]代表了从第一位经两步转移到第一位的方案数，由加法原理可知：
1->1(经两步)=(1->1->1)+(1->2->1)+(1->3->1)
而又由乘法原理可知：
1->2->1=(1->2)×(2->1)
那么正确性就很显然了，由矩阵快速幂的递推关系可知，最终结果即为第一行的数的和
至于KMP，把10个数字扔进去乱搞就是了= =
记得要模k= =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,mod;
char s[25];
int kp[25];
inline void get_kp(){
    kp[0]=0;
    kp[1]=0;
    int k(0);
    for(int i=2;i<=m;i++){
        while(k&&s[k]!=s[i-1])
            k=kp[k];
        if(s[k]==s[i-1])
            k++;
        kp[i]=k;
    }
}
struct node{
    int data[25][25];
    node(){
        memset(data,0,sizeof(data));
    }
    node operator*(node &a){
        node tmp;
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++){
                tmp.data[i][j]=0;
                for(int k=0;k<m;k++){
                    tmp.data[i][j]+=(data[i][k]*a.data[k][j]);
                    tmp.data[i][j]%=mod;
                }
            }
        return tmp;
    }
    node operator*=(node &a){
        *this=*this*a;
        return *this;
    }
}a,sing;
ostream& operator<<(ostream &out,node &a){
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++)
            out<<a.data[i][j]<<' ';
        out<<endl;
    }
    return out;
}
int main(){
    scanf("%d%d%d%s",&n,&m,&mod,s);
    get_kp();
    for(int i=0;i<m;i++)
        for(int j=0;j<=9;j++){
            int k(i);
            while(k&&(j+'0')!=s[k])
                k=kp[k];
            if(j+'0'==s[k])
                k++;
            if(k!=m){
                a.data[i][k]++;
                a.data[i][k]%=mod;//cout<<'*';
            }
        }//cout<<a<<endl;
    /*for(int i=0;i<m;i++){
        for(int j=0;j<m;j++)
            cout<<a[i][j]<<' ';
        cout<<'\n';
    }*/
    for(int i=0;i<m;i++)
        sing.data[i][i]=1;
    int tmp(n);
    while(tmp){
        if(tmp&1)
            sing*=a;
        a*=a;
        //cout<<tmp<<endl;
        //cout<<a<<endl<<sing<<endl;
        tmp>>=1;
    }
    int ans(0);
    for(int i=0;i<m;i++){
        ans=(ans+sing.data[0][i])%mod;
        //cout<<ans<<endl;
    }
    cout<<ans;
    //while(1);
}

ps：2017-6-14 晚 讲题用题解
pss：调矩阵快调死了= =，最后发现初始矩阵求错了= =