本文共 2461 字，大约阅读时间需要 8 分钟。
阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000
阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.
/* Stay hungry, stay foolish. */#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include 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 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;}
转载于:https://www.cnblogs.com/akhpl/p/7116136.html