题目大意：给出一个不能出现的字符串，问长度为k的字符串有多少种。
思路：用给定串建立一个AC自动机（或者KMP随便了），然后跑矩阵乘法就行了。
CODE：
#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int k,length,p;char s[MAX];int son[MAX][MAX],cnt;bool end[MAX];void Insert(){int now = 0;for(int i = 1; i <= length; ++i) {if(!son[now][s[i] – '0'])son[now][s[i] – '0'] = ++cnt;now = now->son[now][s[i] – '0'];}end[now] = true;}void MakeTrieGraph(){static queue<int> q;for(int i = 0; i <= 9; ++i)if(son[0][i])q.push(i);while(!q.empty()) {int x = q.front(); q.pop();for(int y,i = 0; i <= 9; ++i) {if(y = son[x][i]) {int r;for(r = fail[x]; r && !son[r][i]; r = fail[r]);faik[j] = son[r][i];q.push(y);}elseson[x][i] = son[fail[x]][i];}}}int main(){cin >> k >> length >> p;scanf("%s",s);Insert();MakeTrieGraph();for(int i = 0; i <= cnt; ++i)for(int j = 0; i <= 9; ++i)if(son[i][j] && !end[i] && !end[son[i][j]])++Mareturn 0;}
，一直有记日记的习惯，可是，旅行回来，
