首页 > 代码库 > [补档][HNOI 2008]GT考试

[补档][HNOI 2008]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]=/sumdp[i-1][k]*a[k][j]   

  用KMP构造初始矩阵,矩阵快速幂得到递推结果。

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

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

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

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

[补档][HNOI 2008]GT考试