20230215 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

博弈论 + 计数，AC 自动机 + dp，格路计数

# A. 取石子

看了几个小时才想到怎么博弈。

我们把 $x_i\ \bmod\ (a+b)$ 的余数分类讨论，设余数为 $r$ 。

假设 $a < b$ .

$0 \leq r \leq a - 1$
$a \leq r \leq b - 1$
$b \leq r \leq 2a - 1$
$2a \leq r \leq a + b - 1$

下面来分析一下：

情况 1 对胜负没用，忽略掉，不过最后计数的时候要乘上 $2^{c_1}$ 。
出现情况 2，那么 $\text{Alice}$ 必胜，因为这步可以留到最后走。
出现情况 3，那么相当于交换先后手。
出现情况 4：
- 出现次数大于 1：那么 $\text{Alice}$ 必胜，可以手模一下。
- 只出现 1 次， $\text{Alice}$ 先手则先手胜， $\text{Bob}$ 先手则交换先手顺序。

如果 $2a < b$ 的话把 3，4 合并起来就行了（好像）

然后把四种情况记到桶里。

$O(1)$ 计算或者 $O(n)$ $\text{dp}$ 都行。

	#include <bits/stdc++.h>
	#define pb push_back
	// #define int long long

	using namespace std;

	const int N = 1e5 + 10;
	const int mod = 1e9 + 7;
	int n, a, b;
	int s[N], c[N], tot, tmp;

	inline int add(int x) {return x >= mod ? x - mod : x;}
	inline int sub(int x) {return x < 0 ? x + mod : x;}
	inline int mul(int x, int y) {return 1ll * x * y % mod;}

	inline int qpow(int a, int b, int v){
	if(b < 0) return v;
	int res = 1;
	for(; b; b >>= 1, a = mul(a, a))
	if(b & 1) res = mul(res, a);
	return res;
	}

	int t[4], win[4];
	// 0: alice 胜 1: Bob 胜 2: 先手 3: 后手
	int d[N], k, flag;

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cin >> n >> a >> b;
	if(a > b) swap(a, b), flag = 1;
	for(int i = 1; i <= n; ++i) cin >> s[i];
	for(int i = 1; i <= n; ++i){
	int r = s[i] % (a + b);
	if(r < a) t[0]++;
	if(a <= r && r < b) t[1]++;
	if(b < 2 * a){
	if(b <= r && r < 2 * a) t[2]++;
	if(2 * a <= r && r <= a + b - 1) t[3]++;
	}else{
	if(b <= r && r <= a + b - 1) t[3]++;
	}
	}
	win[2] = add(qpow(2, t[2] - 1, 0) + mul(t[3], qpow(2, t[2] - 1, 1)));
	win[2] = mul(win[2], qpow(2, t[0], 1));
	win[3] = mul(qpow(2, t[2] - 1, 1), qpow(2, t[0], 1));
	win[0] = sub(qpow(2, n, 0) - add(win[2] + win[3]));
	if(flag) swap(win[0], win[1]);
	for(int i = 0; i < 4; ++i) cout << win[i] << " ";
	cout << '\n';
	return 0;

	}

# B. 字符串

妙题。

我们对 $s_1 \sim s_n$ 的正反串分别建两个 AC 自动机，设为 $A,B$ 。

记一个 $\text{dp}$ ，设 $f_{i, S, p, q}$ 表示填了 $i$ 个字符，包含了状态为 $S$ 的串，当前在 $A$ 的 $p$ 点， $B$ 的 $q$ 点时的方案数。

转移时枚举下一个填 $0/1$ ，对称的位置是固定的，让 $p, q$ 跳到相应的 $x, y$ 点，状态或上 $x,y$ 包含的子串。

转移方程：

$f_{i + 1, s | endA_x | endB_y, x, y} += f_{i, s, p, q}$

这时还有一个小问题，就是有一些串越过中间的位置。

我们预处理出一个数组 $g_{i, j}$ 表示现在在 $A$ 中的 $i$ 点， $B$ 中 $j$ 点时，两边拼接能够包含的 $n$ 个模式串的 01 状态。

统计答案时枚举状态，再枚举所有符合这个状态的 $p, q$ ，把 $S$ 跟 $g_{p, q}$ 或起来看一下是否合法即可。

	#include <bits/stdc++.h>
	#define pb push_back
	#define fi first
	#define se second
	#define int long long

	using namespace std;

	const int N = 610;
	const int mod = 998244353;
	int n, m;
	char s[10][N];
	int b[N], len[10];

	inline void add(int &x, int y) {x = x + y >= mod ? x + y - mod : x + y;}

	struct ACAN{
	int ch[N][2], tot, num[N], fail[N];
	vector <int> G[N];

	inline void insert(char *s, int id){
	int len = strlen(s + 1), u = 0;
	for(int i = 1; i <= len; ++i){
	int c = s[i] - '0';
	if(!ch[u][c]) ch[u][c] = ++tot;
	u = ch[u][c];
	}
	num[u] \|= (1 << id);
	}

	inline void build(){
	queue <int> q;
	for(int i = 0; i < 2; ++i)
	if(ch[0][i]) q.push(ch[0][i]);
	while(!q.empty()){
	int x = q.front(); q.pop();
	for(int i = 0; i < 2; ++i){
	if(ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
	else ch[x][i] = ch[fail[x]][i];
	}
	}
	for(int i = 1; i <= tot; ++i) G[fail[i]].pb(i), num[i] \|= num[fail[i]];
	}
	}A, B;

	int g[N][N];

	inline int jump1(int p, int l, int r){
	int x = 0;
	for(int i = l; i <= r; ++i) x = A.ch[x][s[p][i] - '0'];
	return x;
	}

	inline int jump2(int p, int l, int r){
	int x = 0;
	for(int i = r; i >= l; --i) x = B.ch[x][s[p][i] - '0'];
	return x;
	}

	inline void dfs2(int x, int y){
	g[x][y] \|= g[x][B.fail[y]] \| g[A.fail[x]][y];
	for(auto v : B.G[y]) dfs2(x, v);
	}

	inline void dfs1(int x, int y){
	dfs2(x, y);
	for(auto v : A.G[x]) dfs1(v, y);
	}

	typedef pair<int, int> P;
	int f[2][64][N][N];
	vector <P> vec[2][64];

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cin >> m >> n;
	for(int i = 0; i < m; ++i){
	cin >> (s[i] + 1), len[i] = strlen(s[i] + 1);
	A.insert(s[i], i), reverse(s[i] + 1, s[i] + 1 + len[i]);
	B.insert(s[i], i), reverse(s[i] + 1, s[i] + 1 + len[i]);
	}
	A.build(), B.build();
	for(int i = 0; i < m; ++i)
	for(int j = 1; j < len[i]; ++j)
	g[jump1(i, 1, j)][jump2(i, j + 1, len[i])] \|= (1 << i);
	dfs1(0, 0);

	f[0][0][0][0] = 1;
	vec[0][0].pb(P(0, 0));
	for(int i = 0, l = 0; i < n; ++i, l ^= 1)
	for(int s = 0; s < (1 << m); ++s){
	for(auto p : vec[l][s]){
	for(int c = 0; c < 2; ++c){
	P q = P(A.ch[p.fi][c], B.ch[p.se][c ^ 1]);
	int t = s \| A.num[q.fi] \| B.num[q.se];
	if(!f[l ^ 1][t][q.fi][q.se]) vec[l ^ 1][t].pb(q);
	add(f[l ^ 1][t][q.fi][q.se], f[l][s][p.fi][p.se]);
	}
	f[l][s][p.fi][p.se] = 0;
	}
	vec[l][s].clear();
	}
	int ans = 0;
	for(int s = 0; s < (1 << m); ++s)
	for(auto p : vec[n & 1][s])
	if((s \| g[p.fi][p.se]) == (1 << m) - 1) add(ans, f[n & 1][s][p.fi][p.se]);
	cout << ans << '\n';
	return 0;
	}

# C. 树

挺复杂的格路计数。

经过大量模拟不难发现不包含 $k$ 连树相当于根到每个叶子上左儿子个数小于 $k$ 。

考虑按先序遍历建出这棵树，每次有两种操作：

当前点加一个左孩子；
退到上一个只有左孩子的点，加一个右孩子。

转化成括号匹配，相当于一个长度为 $2n - 2$ 的序列，保证左括号 - 右括号数量小于 $m$ 。

当然还要保证括号序列合法，即前缀和大于等于 0。

如果只有前缀和大于等于 0 的条件，就是经典的卡特兰数的容斥：

总路径 - 不合法路径。大概就是把第一次碰到 -1 后面的路径全部翻折，最后到达 $(2n-2, -2)$ （不会的自行百度）

不合法方案数就是从 $(0, 0)$ 走到 $(2n-2,-2)$ 的路径数。

然后现在有两个限制条件，我们的方案数就是：

$总 - [-1] - [m - 1]$

（ $[-1], [m-1]$ 表示经过 $-1, m-1$ 的方案数）

但是明显有重复的，所以就再套个容斥：

$总 - [-1] - [m - 1] + [-1, m - 1] + [m - 1, -1] - [-1, m - 1, -1] -\cdots$

然后就没了。

	#include <bits/stdc++.h>
	#define pb push_back

	using namespace std;

	const int N = 2e7 + 10;
	const int mod = 998244353;
	int n, m;
	int fac[N], ifac[N];

	inline int add(int x) {return x >= mod ? x - mod : x;}
	inline int sub(int x) {return x < 0 ? x + mod : x;}
	inline int mul(int x, int y) {return 1ll * x * y % mod;}

	inline int qpow(int a, int b){
	int res = 1;
	for(; b; b >>= 1, a = mul(a, a))
	if(b & 1) res = mul(res, a);
	return res;
	}

	inline void init(int n){
	fac[0] = 1;
	for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
	ifac[n] = qpow(fac[n], mod - 2);
	for(int i = n - 1; i >= 0; --i) ifac[i] = mul(ifac[i + 1], i + 1);
	}

	inline int C(int n, int m){
	return mul(fac[n], mul(ifac[m], ifac[n - m]));
	}

	inline int f(int x){
	if(x > n \|\| x < -n) return 0;
	return C(n, (n + x) / 2);
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cin >> n >> m, init(2e7);
	n = 2 * n - 2;
	int ans = f(0);
	for(int k = 2; (k - 2) * m <= n; k += 2){
	ans = sub(ans - add(f(k * m - 2) + f(-(k - 2) * m - 2)));
	ans = add(ans + add(f(k * m) + f(-k * m)));
	}
	cout << ans << '\n';
	return 0;
	}

# A. 取石子

# B. 字符串

# C. 树

20230214

20230217