题意：
给出一n种字符的字典，有p个禁用的单词，
问能组成多少个不同的长度为m的合法字符串。(m<=50)
题解：
是不是个我们之前做的题目非常非常像，题意都一样。
直接将上次写的AC自动机+矩阵快速幂的代码交上去。
然后突然发现没有取模，好像直接炸了。即便只有50，但是方案数还是爆__int128了
处理不了，这题还是必须用大数的。
p<=10 我们可以考虑状压实现。
这题还是和之前的题目有点关系的，需要求出可达矩阵，然后根据这个去DP
dp[i][j] 表示第 i 步 在AC自动机 j 这个节点 的方案数目，
然后第 i 步只跟 第 i - 1步的状态有关，然后可以滚动掉这一维。
不用试不滚动的了，会mle的。 别问我怎么知道的！！！！
1 #include <set> 2 #include <map> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <cstdio> 7 #include <string> 8 #include <vector> 9 #include <time.h> 10 #include <cstring> 11 #include <iostream> 12 #include <algorithm> 13 14 #define pi acos(-1.0) 15 #define eps 1e-9 16 #define fi first 17 #define se second 18 #define rtl rt<<1 19 #define rtr rt<<1|1 20 #define bug printf("****** ") 21 #define mem(a, b) memset(a,b,sizeof(a)) 22 #define name2str(x) #x 23 #define fuck(x) cout<<#x" = "<<x<<endl 24 #define sf(n) scanf("%d", &n) 25 #define sff(a, b) scanf("%d %d", &a, &b) 26 #define sfff(a, b, c) scanf("%d %d %d", &a, &b, &c) 27 #define sffff(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d) 28 #define pf printf 29 #define FIN freopen("../date.txt","r",stdin) 30 #define gcd(a, b) __gcd(a,b) 31 #define lowbit(x) x&-x 32 #define IO iOS::sync_with_stdio(false) 33 34 35 using namespace std; 36 typedef long long LL; 37 typedef unsigned long long ULL; 38 const int maxn = 1e6 + 7; 39 const int maxm = 8e6 + 10; 40 const int INF = 0x3f3f3f3f; 41 const int mod = 1e9 + 7; 42 43 struct Matrix { 44 int mat[110][110], n; 45 46 Matrix() {} 47 48 Matrix(int _n) { 49 n = _n; 50 for (int i = 0; i < n; i++) 51 for (int j = 0; j < n; j++) 52 mat[i][j] = 0; 53 } 54 55 Matrix operator*(const Matrix &b) const { 56 Matrix ret = Matrix(n); 57 for (int i = 0; i < n; i++) 58 for (int j = 0; j < n; j++) 59 for (int k = 0; k < n; k++) { 60 int tmp = (long long) mat[i][k] * b.mat[k][j] % mod; 61 ret.mat[i][j] = (ret.mat[i][j] + tmp) % mod; 62 } 63 return ret; 64 } 65 }; 66 67 68 char buf[1000010]; 69 int n, m, p; 70 map<char, int> mp; 71 72 struct Aho_Corasick { 73 int next[110][52], fail[110], End[110]; 74 int root, cnt; 75 76 int newnode() { 77 for (int i = 0; i < 52; i++) next[cnt][i] = -1; 78 End[cnt++] = 0; 79 return cnt - 1; 80 } 81 82 void init() { 83 cnt = 0; 84 root = newnode(); 85 } 86 87 void insert(char buf[]) { 88 int len = strlen(buf); 89 int now = root; 90 for (int i = 0; i < len; i++) { 91 if (next[now][mp[buf[i]]] == -1) next[now][mp[buf[i]]] = newnode(); 92 now = next[now][mp[buf[i]]]; 93 } 94 End[now]++; 95 } 96 97 void build() { 98 queue<int> Q; 99 fail[root] = root; 100 for (int i = 0; i < 52; i++) 101 if (next[root][i] == -1) next[root][i] = root; 102 else { 103 fail[next[root][i]] = root; 104 Q.push(next[root][i]); 105 } 106 while (!Q.empty()) { 107 int now = Q.front(); 108 Q.pop(); 109 if (End[fail[now]]) End[now] = 1; 110 for (int i = 0; i < 52; i++) 111 if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; 112 else { 113 fail[next[now][i]] = next[fail[now]][i]; 114 Q.push(next[now][i]); 115 } 116 } 117 } 118 119 Matrix get_Matrix() { 120 Matrix ret = Matrix(cnt); 121 for (int i = 0; i < cnt; ++i) { 122 for (int j = 0; j < n; ++j) { 123 if (!End[next[i][j]]) ret.mat[i][next[i][j]]++; 124 } 125 } 126 return ret; 127 } 128 129 void debug() { 130 for (int i = 0; i < cnt; i++) { 131 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]); 132 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]); 133 printf("] "); 134 } 135 } 136 } ac; 137 138 const int MAXL = 2500; 139 const int MAXN = 9999; 140 const int DLEN = 4; 141 142 class Big { 143 public: 144 int a[600], len; 145 146 Big(const int b = 0) { 147 int c, d = b; 148 len = 0; 149 memset(a, 0, sizeof(a)); 150 while (d > MAXN) { 151 c = d - (d / (MAXN + 1)) * (MAXN + 1); 152 d = d / (MAXN + 1); 153 a[len++] = c; 154 } 155 a[len++] = d; 156 } 157 158 Big(const char *s) { 159 int t, k, index, L; 160 memset(a, 0, sizeof(a)); 161 L = strlen(s); 162 len = L / DLEN; 163 if (L % DLEN) len++; 164 index = 0; 165 for (int i = L - 1; i >= 0; i -= DLEN) { 166 t = 0; 167 k = i - DLEN + 1; 168 if (k < 0) k = 0; 169 for (int j = k; j <= i; j++) t = t * 10 + s[j] - '0'; 170 a[index++] = t; 171 } 172 } 173 174 Big operator/(const LL &b) const { 175 Big ret; 176 LL down = 0; 177 for (int i = len - 1; i >= 0; i--) { 178 ret.a[i] = (a[i] + down * (MAXN + 1)) / b; 179 down = a[i] + down * (MAXN + 1) - ret.a[i] * b; 180 } 181 ret.len = len; 182 while (ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--; 183 return ret; 184 } 185 186 bool operator>(const Big &T) const { 187 int ln; 188 if (len > T.len) return true; 189 else if (len == T.len) { 190 ln = len - 1; 191 while (a[ln] == T.a[ln] && ln >= 0) ln--; 192 if (ln >= 0 && a[ln] > T.a[ln]) return true; 193 else return false; 194 } else return false; 195 } 196 197 Big operator+(const Big &T) const { 198 Big t(*this); 199 int big = T.len > len ? T.len : len; 200 for (int i = 0; i < big; i++) { 201 t.a[i] += T.a[i]; 202 if (t.a[i] > MAXN) { 203 t.a[i + 1]++; 204 t.a[i] -= MAXN + 1; 205 } 206 } 207 if (t.a[big] != 0) t.len = big + 1; 208 else t.len = big; 209 return t; 210 } 211 212 Big operator-(const Big &T) const { 213 int big; 214 bool flag; 215 Big t1, t2; 216 if (*this > T) { 217 t1 = *this; 218 t2 = T; 219 flag = 0; 220 } else { 221 t1 = T; 222 t2 = *this; 223 flag = 1; 224 } 225 big = t1.len; 226 for (int i = 0; i < big; i++) { 227 if (t1.a[i] < t2.a[i]) { 228 int j = i + 1; 229 while (t1.a[j] == 0) j++; 230 t1.a[j--]--; 231 while (j > i) t1.a[j--] += MAXN; 232 t1.a[i] += MAXN + 1 - t2.a[i]; 233 } else t1.a[i] -= t2.a[i]; 234 } 235 t1.len = big; 236 while (t1.a[t1.len - 1] == 0 && t1.len > 1) { 237 t1.len--; 238 big--; 239 } 240 if (flag) t1.a[big - 1] = 0 - t1.a[big - 1]; 241 return t1; 242 } 243 244 LL operator%(const int &b) const { 245 LL d = 0; 246 for (int i = len - 1; i >= 0; i--) d = ((d * (MAXN + 1)) % b + a[i]) % b; 247 return d; 248 } 249 250 Big operator*(const Big &T) const { 251 Big ret; 252 int i, j, up, temp, temp1; 253 for (i = 0; i < len; i++) { 254 up = 0; 255 for (j = 0; j < T.len; j++) { 256 temp = a[i] * T.a[j] + ret.a[i + j] + up; 257 if (temp > MAXN) { 258 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1); 259 up = temp / (MAXN + 1); 260 ret.a[i + j] = temp1; 261 } else { 262 up = 0; 263 ret.a[i + j] = temp; 264 } 265 } 266 if (up != 0) ret.a[i + j] = up; 267 } 268 ret.len = i + j; 269 while (ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--; 270 return ret; 271 } 272 273 void print() { 274 printf("%d", a[len - 1]); 275 for (int i = len - 2; i >= 0; i--) printf("%04d", a[i]); 276 } 277 }; 278 279 Big dp[2][105]; 280 281 int main() { 282 //FIN; 283 while (~scanf("%d%d%d", &n, &m, &p)) { 284 mp.clear(); 285 scanf("%s", buf); 286 int len = strlen(buf); 287 for (int i = 0; i < len; ++i) mp[buf[i]] = i; 288 ac.init(); 289 for (int i = 0; i < p; ++i) { 290 scanf("%s", buf); 291 ac.insert(buf); 292 } 293 ac.build(); 294 Matrix mat = ac.get_Matrix(); 295 // for (int i = 0; i < mat.n; ++i) { 296 // for (int j = 0; j < mat.n; ++j) { 297 // printf("%d ",mat.mat[i][j]); 298 // } 299 // printf(" "); 300 // } 301 int now=0; 302 dp[now][0] = 1; 303 for (int i = 1; i < mat.n; ++i) dp[now][i] = 0; 304 for (int i = 1; i <= m; ++i) { 305 now^=1; 306 for (int j = 0; j < mat.n; ++j) dp[now][j]=0; 307 for (int j = 0; j < mat.n; ++j) { 308 for (int k = 0; k < mat.n; ++k) { 309 if (mat.mat[j][k]) dp[now][k] = dp[now][k] + dp[now^1][j] * mat.mat[j][k]; 310 } 311 } 312 } 313 Big ans = 0; 314 for (int i = 0; i < mat.n; ++i) ans = ans + dp[now][i]; 315 ans.print(); 316 printf(" "); 317 } 318 return 0; 319 }