1009: [HNOI2008]GT考試
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1067 Solved: 642
[Submit][Status][Discuss]
Description
阿申准備報名參加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位的數。 100%數據N<=10^9,M<=20,K<=1000 40%數據N<=1000 10%數據N<=6
Output
阿申想知道不出現不吉利數字的號碼有多少種，輸出模K取余的結果.
Sample Input
4 3 100
111
Sample Output
81
HINT
KMP+矩陣乘法，值得一提的是矩陣Dp那段是第一次自己推的……
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define MAXM (20+10)
int n,m,F;
struct M
{
int a[MAXM][MAXM];
M(){memset(a,0,sizeof(a));}
int& operator()(int i,int j){return a[i][j];}
friend M operator*(M a,M b)
{
M c;
For(k,m)
For(i,m)
For(j,m)
{
c(i,j)=(c(i,j)+a(i,k)*b(k,j))%F;
}
return c;
}
void print()
{
For(i,m)
{
For(j,m) cout<<a[i][j]<<' ';cout<<endl;
}
}
}a0;
int next[MAXM]={0};
char p[MAXM];
void kmp()
{
int j=0;
Fork(i,2,m)
{
while (j&&p[j+1]!=p[i]) j=next[j];
if (p[j+1]==p[i]) j++;
next[i]=j;
}
}
M c;
M pow(M a,long long b)
{
For(i,m) c(i,i)=1;
while (b)
{
if (b%2) c=c*a;
a=a*a;
b>>=1;
}
return c;
}
int a[MAXM]={0},ans[MAXM]={0};
int main()
{
//freopen("bzoj1009.in","r",stdin);
scanf("%d%d%d%s",&n,&m,&F,p+1);
kmp();
//For(i,m) cout<<next[i]<<' ';
// a0 0..m-1
For(j,m) //0->m-1
{
//f[i][j]->f[i+1][k]
//-> f[j]->f[k]
//-> a0[k][j]
Rep(num,10)
{
if (num==p[j]-48) //j+1
{
if (j<m) a0(j+1,j)++;
}
else
{
int t=next[j-1];
while (t&&p[t+1]-48!=num) t=next[t];
if (p[t+1]-48==num) t++;
a0(t+1,j)++;
}
}
}
//a0.print();cout<<endl;
a0=pow(a0,n-1);
//a0.print();
a[1]=9,a[2]=1;
long long ans=0;
For(i,m) ans=(ans+a0(i,1)*9+a0(i,2))%F;
cout<<ans<<endl;
return 0;
}
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define MAXM (20+10)
int n,m,F;
struct M
{
int a[MAXM][MAXM];
M(){memset(a,0,sizeof(a));}
int& operator()(int i,int j){return a[i][j];}
friend M operator*(M a,M b)
{
M c;
For(k,m)
For(i,m)
For(j,m)
{
c(i,j)=(c(i,j)+a(i,k)*b(k,j))%F;
}
return c;
}
void print()
{
For(i,m)
{
For(j,m) cout<<a[i][j]<<' ';cout<<endl;
}
}
}a0;
int next[MAXM]={0};
char p[MAXM];
void kmp()
{
int j=0;
Fork(i,2,m)
{
while (j&&p[j+1]!=p[i]) j=next[j];
if (p[j+1]==p[i]) j++;
next[i]=j;
}
}
M c;
M pow(M a,long long b)
{
For(i,m) c(i,i)=1;
while (b)
{
if (b%2) c=c*a;
a=a*a;
b>>=1;
}
return c;
}
int a[MAXM]={0},ans[MAXM]={0};
int main()
{
//freopen("bzoj1009.in","r",stdin);
scanf("%d%d%d%s",&n,&m,&F,p+1);
kmp();
//For(i,m) cout<<next[i]<<' ';
// a0 0..m-1
For(j,m) //0->m-1
{
//f[i][j]->f[i+1][k]
//-> f[j]->f[k]
//-> a0[k][j]
Rep(num,10)
{
if (num==p[j]-48) //j+1
{
if (j<m) a0(j+1,j)++;
}
else
{
int t=next[j-1];
while (t&&p[t+1]-48!=num) t=next[t];
if (p[t+1]-48==num) t++;
a0(t+1,j)++;
}
}
}
//a0.print();cout<<endl;
a0=pow(a0,n-1);
//a0.print();
a[1]=9,a[2]=1;
long long ans=0;
For(i,m) ans=(ans+a0(i,1)*9+a0(i,2))%F;
cout<<ans<<endl;
return 0;
}
