AT_abc305_g [ABC305G] Banned Substrings 题解

### 题目大意
给你一堆字符串 $S_i$，然后让你统计满足以下条件的字符串 $T$ 的数量：
- 只由 $\texttt a$ 和 $\texttt b$ 组成。
- 不包含任意一个 $S_i$。

### 解题思路
考虑 AC 自动机，dp，矩阵快速幂。

由于字符串长度在 $6$ 以内，所以自动机的节点数小于 $2^7$。

首先设 $dp_{i, c}$ 为 $T$ 的长度为 $i$ 且在自动机上遍历到 $c$ 节点，那么显然可以从 $dp_{i - 1, f_c}$ 转移过来，其中 $f_c$ 为 $c$ 的上一个结点。

然后我们就可以构建矩阵，只要他不是字符串的结尾，都给他赋值为 $1$。

CODE：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353, N = 132;
queue<int> q;
int n, m, c[N][2], fail[N], u, cnt;
bool vis[N];
struct mat {
	int n, m, a[N][N] = {};
	inline mat operator * (const mat b) {
		mat res;
		res.n = n, res.m = b.m;
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= b.m; j++) {
				for (int k = 0; k <= m; k++)
					res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
			}
		}
		return res;
	}
} x, ans;
inline void insert(string str) {
	u = 0;
	for (char x : str) {
		if (!c[u][x - 'a']) {
			c[u][x - 'a'] = ++cnt;
		}
		u = c[u][x - 'a'];
	}
	vis[u] = 1;
}
inline void get_fail() {
	for (int i = 0; i < 2; i++) {
		if (c[0][i]) {
			q.push(c[0][i]);
		}
	}
	while (!q.empty()) {
		u = q.front(), q.pop(), vis[u] |= vis[fail[u]];
		for (int i = 0; i < 2; i++)
			if (c[u][i]) {
				fail[c[u][i]] = c[fail[u]][i];
				q.push(c[u][i]);
			} else {
				c[u][i] = c[fail[u]][i];
			}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	while (m--) {
		string a;
		cin >> a;
		insert(a);
	}
	get_fail();
	x.n = x.m = ans.n = cnt, ans.m = 0, ans.a[0][0] = 1;
	for (int i = 0; i <= cnt; i++) {
		if (!vis[i]) {
			for (int j = 0; j < 2; j++) {
				x.a[c[i][j]][i] = 1;
			}
		}
	}
	while (n) {
		if (n & 1) {
			ans = x * ans;
		}
		x = x * x;
		n >>= 1;
	}
	int res = 0;
	for (int i = 0; i <= cnt; i++) {
		if (!vis[i]) {
			res = (res + ans.a[i][0]) % mod;
		}
	}
	cout << res;
	return 0;
}
```

正在渲染内容...