希望自己能成为日更博主

题目连接：http://poj.org/problem?id=1625 

题目大意：给你n个字母，再给你p个字符串，问有多少个长度为m的只由给出的n个字母构成的字符串，且字符串不能包括给出的p个字符串；

题解：因为这个题不用取模，所以得使用高精度，参考了博客：https://www.cnblogs.com/shangyu/p/3730815.html；这个题和HDU 2243很像，只要把他的矩阵快速幂换成高精度就可以了。dp[i+1][next] = dp[i+1][next]+dp[i][j] ， dp[i][j] 表示长度为 i 在第j个结点的方案数，next为当前j点所能走到的下一个合法的结点。求不含啥啥字符串的个数时，建立ac自动机时都会有end[now]|=end[fail[now]] ，表示如果当前结点fail指向的结点被标记了，那么当前节点也要被标记。

 

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<algorithm>
  4 #include<queue>
  5 #include<string.h>
  6 using namespace std;
  7 
  8 const int base=1e4;
  9 const int DIG=4;
 10 const int maxn = 11100;
 11 const int MX = 1110;
 12 int n,m,p;
 13 int id[2200];
 14 
 15 struct tire{
 16     int nxt[maxn][2200],fail[maxn],end[maxn],tot,root,vis[maxn];
 17     int newNode(){
 18         for(int i=0;i<n;i++) nxt[tot][i] = -1;
 19         end[tot++] = 0;
 20         return tot-1;
 21     }
 22     void Init(){
 23         tot = 0;
 24         root = newNode();
 25     }
 26     void Insert(char *buf){
 27         int len = strlen(buf),i,u = root;
 28         for(i=0;i<len;i++){
 29             int x = id[buf[i]];
 30             if(nxt[u][x]==-1) nxt[u][x] = newNode();
 31             u = nxt[u][x];
 32         }
 33         end[u] = 1;
 34     }
 35     void build(){
 36         queue <int> q;
 37         fail[root] = root;
 38         for(int i=0;i<n;i++){
 39             if(nxt[root][i]==-1) nxt[root][i] = root;
 40             else{
 41                 fail[nxt[root][i]] = root;
 42                 q.push(nxt[root][i]);
 43             }
 44         }
 45         while(!q.empty()){
 46             int now = q.front();
 47             q.pop();
 48             for(int i=0;i<n;i++){
 49                 if(nxt[now][i]==-1) nxt[now][i] = nxt[fail[now]][i];
 50                 else{
 51                     fail[nxt[now][i]] = nxt[fail[now]][i];
 52                     q.push(nxt[now][i]);
 53                 }
 54             }
 55             end[now]|=end[fail[now]];
 56         }
 57     }
 58 }ac;
 59 
 60 struct bignum
 61 {
 62     int a[110],len;
 63     bignum()
 64     {
 65         memset(a,0,sizeof(a));
 66         len=1;
 67     }
 68     bignum(int v)
 69     {
 70         memset(a,0,sizeof(a));
 71         len=0;
 72         do{
 73             a[len++]=v%base;
 74             v/=base;
 75         }while(v);
 76     }
 77     bignum(const char s[])
 78     {
 79         memset(a,0,sizeof(a));
 80         int k = strlen(s);
 81         len = k/DIG;
 82         if(k%DIG) len++;
 83         int cnt = 0;
 84         for(int i = k-1;  i >= 0 ; i-=DIG){
 85             int t = 0;
 86             int kk = i-DIG+1;
 87             if(kk<0) kk =0;
 88             for(int j = kk ; j <= i ; j++)
 89              t = t*10+s[j]-'0';
 90             a[cnt++] = t;
 91          }
 92     }
 93     bignum operator + (const bignum &b) const
 94     {
 95         bignum res;
 96         res.len=max(len,b.len);
 97         int i;
 98         for(i=0;i<res.len;i++)
 99             res.a[i]=0;
100         for(i=0;i<res.len;i++){
101             res.a[i]+=((i<len)?a[i]:0)+((i<b.len)?b.a[i]:0);
102             res.a[i+1]+=res.a[i]/base;
103             res.a[i]=res.a[i]%base;
104         }
105         if(res.a[res.len]>0) res.len++;
106         return res;
107     }
108     void output()
109     {
110         printf("%d",a[len-1]);
111         for(int i=len-2;i>=0;i--)
112             printf("%04d",a[i]);
113         printf("\n");
114     }
115 }dp[110][110];
116 
117 void solve()
118 {
119     for(int i=1;i<=m;i++)
120         for(int j=0;j<=ac.tot;j++)
121             dp[i][j]=bignum(0);
122     dp[0][0]=bignum(1);
123     for(int i=0;i<m;i++){
124         for(int j=0;j<ac.tot;j++){
125             for(int k=0;k<n;k++){
126                 if(ac.end[ac.nxt[j][k]]) continue;
127                 dp[i+1][ac.nxt[j][k]]= dp[i+1][ac.nxt[j][k]]+dp[i][j];
128             }
129         }
130     }
131     bignum ans=bignum(0);
132     for(int j=0;j<ac.tot;j++)
133         ans=ans+dp[m][j];
134     ans.output();
135 }
136 
137 char s1[MX];
138 
139 int main()
140 {
141     scanf("%d%d%d",&n,&m,&p);
142     ac.Init();
143     scanf("%s",s1);
144     for(int i=0;i<n;i++){
145         id[s1[i]]=i;
146     }
147     for(int i=0;i<p;i++)
148         scanf("%s",s1),ac.Insert(s1);
149     ac.build();
150     solve();
151     return 0;
152 }