BZOJ 1009 GT考试

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

HINT

Source

利用“不吉利数字”构建ac自动机（我好像小题大做了，一个串好像没有必要），构建初始矩阵，接着矩阵乘法即可。

初始矩阵a[i][j]表示走一步从i节点走到j节点的方案数。

code：

 #include<vector>

 #include<queue>

 #include<cstring>

 #include<cstdio>

 #include<cstdlib>

 using namespace std;

 #define maxm 25

 char buf[maxm];

 int n,m,rhl,ans;

 struct node

 {

     int a[maxm*maxm][maxm*maxm],n,m;

     node() {memset(a,,sizeof(a));n = m = ;}

     friend node operator *(node x,node y)

     {

         node z; z.n = x.n; z.m = y.m;

         int i,j,k;

         for (i = ;i <= z.n;++i)

             for (j = ;j <= z.m;++j)

                 for (k = ;k <= x.m;++k)

                     (z.a[i][j] += (long long)x.a[i][k]*(long long)y.a[k][j]%rhl)%=rhl;

         return z;

     }

     inline node quick(node x,int k)

     {

         node ret; ret.n = x.n; ret.m = x.m;

         for (int i = ;i <= ret.n;++i) ret.a[i][i] = ;

         for (;k;k>>=,x = x*x)

             if (k & )

                 ret = ret*x;

         return ret;

     }

     inline void calc() { for (int i = ;i <= m;++i) (ans += a[][i])%=rhl; }

 }s;

 struct trie

 {

     int next[maxm][],fail[maxm],L,root;

     bool end[maxm];

     inline int newnode()

     {

         memset(next[L],-,sizeof(next[L]));

         return ++L-;

     }

     inline void init() {L = ; root = newnode();}

     inline void insert()

     {

         int len = strlen(buf),now = root,i;

         for (i = ;i < len;++i)

         {

             if (next[now][buf[i]-''] == -) next[now][buf[i]-''] = newnode();

             now = next[now][buf[i]-''];

         }

         end[now] = true;

     }

     inline void build()

     {

         int now = root,i; queue <int> team;

         fail[root] = root;

         for (i = ;i < ;++i)

             if (next[now][i] == -) next[now][i] = root;

             else fail[next[now][i]] = root,team.push(next[now][i]);

         while (!team.empty())

         {

             now = team.front(); team.pop();

             for (i = ;i < ;++i)

                 if (next[now][i] == -) next[now][i] = next[fail[now]][i];

                 else fail[next[now][i]] = next[fail[now]][i],team.push(next[now][i]);

         }

     }

     inline void ready()

     {

         vector <int> son[maxm]; queue <int> team; int i,now,v,nn;

         for (i = ;i < L;++i) if (fail[i] != i) son[fail[i]].push_back(i);

         team.push(root);

         while (!team.empty())

         {

             now = team.front(); team.pop();

             nn = son[now].size();

             for (i = ;i < nn;++i)

             {

                 v = son[now][i];

                 if (end[now]) end[v] = true;

                 team.push(v);

             }

         }

     }

     inline void make()

     {

         int i,j; s.n = s.m = L;

         for (i = ;i < L;++i)

         {

             if (end[i]) continue;

             for (j = ;j < ;++j)

                 if (!end[next[i][j]]) s.a[i+][next[i][j]+]++;

         }

     }

 }ac;

 int main()

 {

     freopen("1009.in","r",stdin);

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

     scanf("%d %d %d\n",&n,&m,&rhl);

     ac.init();

     scanf("%s",buf); ac.insert();

     ac.build(); ac.ready(); ac.make();

     s = s.quick(s,n); s.calc();

     printf("%d",ans);

     fclose(stdin); fclose(stdout);

     return ;

 }