BZOJ1009 GT考试

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可以为0

Input

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

Output

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

Sample Input

4 3 100
111

Sample Output

81

---

水题

用KMP求出转移矩阵（不反对暴力）

直接矩阵快速幂

---

/* Stay hungry, stay foolish. */

#include<iostream>

#include<algorithm>

#include<queue>

#include<string>

#include<map>

#include<vector>

#include<set>

#include<sstream>

#include<stack>

#include<ctime>

#include<cmath>

#include<cctype>

#include<climits>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<bitset>

#include<complex>

using namespace std;

/*

#define getchar() getc()

char buf[1<<15],*fs,*ft;

inline char getc()  {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft)?0:*fs++;}

*/

template <class _T> inline void read(_T &_x) {

	int _t; bool _flag=false;

	while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;

	if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';

	while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';

	if(_flag) _x=-_x;

}

typedef long long LL;

const int maxm = 30;

int n, m, mod;

struct Matrix {

	int v[maxm][maxm], n, m;

	Matrix() {memset(v, 0, sizeof v); }

	Matrix(int a, int b):n(a), m(b) {memset(v, 0, sizeof v); }

	void init() {for (int i = 0; i <= n && i <= m; ++i) v[i][i] = 1; }

	Matrix operator * (Matrix B)const {

		Matrix C(n, B.m);

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

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

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

					(C.v[i][j] += v[i][k] * B.v[k][j]) %= mod;

		return C;

	}

	Matrix operator ^ (int t) {

		Matrix ans(n, m), x = *this;

		ans.init();

		for ( ; t; t >>= 1, x = x * x)

			if (t & 1) ans = ans * x;

		return ans;

	}

	inline void print() {

		for (int i = 0; i <= n; ++i) {

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

				printf("%d ", v[i][j]);

			}

			puts("");

		}

	}

};

int nxt[maxm];

int main() {

	//freopen("test.in","r",stdin);

	//freopen(".out","w",stdout);

	read(n), read(m), read(mod);

	char s[maxm];

	scanf("%s", s + 1);

	nxt[1] = 0;

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

		j = nxt[i - 1];

		while (j && s[j + 1] != s[i]) j = nxt[j];

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

		nxt[i] = j;

	}

	Matrix x(m, m);

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

		for (int j = 0, k; j <= 9; ++j) {

			k = i;

			while (k && s[k + 1] - '0' != j) k = nxt[k];

			if (s[k + 1] - '0' == j) ++k;

			if (k != m) (++x.v[k][i]) %= mod;

		}

	}

	x = x ^ n;

	int sum = 0;

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

		(sum += x.v[i][0]) %= mod;

	cout << sum << endl;

	return 0;

}