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

计数，~~div lj ak~~AC 自动机 + 树上差分，结论 + 树状数组，区间 dp

# A. 矩阵游戏

一眼想到我永远喜欢月，然而并没有什么卵用。

不难发现行列是独立的，所以分开考虑。

我们称操作一行或一列被操作奇数次为有效操作。

那么当有 $i$ 行有效， $j$ 列有效的方案数为：

$\dbinom ni\dbinom mj$

此时 $i, j$ 应满足 $0 \leq i, j \leq k, i, j \equiv 2 \bmod k$ .

但是会算重，什么情况下有重复呢？

结论：只有在 $n, m$ 均为偶数时，不同的操作方案才会导致出现相同的矩阵。

证明… 就算了。

算重的部分同样是：

$\dbinom ni \dbinom mj$

当 $i, j$ 满足: $(i,j <= k, i, j \equiv 2 \bmod k, n-i, m - j \leq k)$ .

最后面这个条件什么意思呢？其实就是把所有的操作反过来依旧合法的限制。

用上面的总方案数减掉这个就行了。

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

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 2e5 + 10;
	const int mod = 1e9 + 7;
	int T, n, m, k;
	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;
	while(b){
	if(b & 1) res = mul(res, a);
	a = mul(a, a), b >>= 1;
	}
	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 void solve(){
	cin >> n >> m >> k;
	int res = 0, s1 = 0, s2 = 0;
	for(int i = k & 1; i <= min(n, k); i += 2) s1 = add(s1 + C(n, i));
	for(int i = k & 1; i <= min(m, k); i += 2) s2 = add(s2 + C(m, i));
	res = mul(s1, s2);
	if((n & 1) \|\| (m & 1)) cout << res << '\n';
	else{
	s1 = 0, s2 = 0;
	for(int i = k & 1; i <= min(n, k); i += 2)
	if(n - i <= k) s1 = add(s1 + C(n, i));
	for(int i = k & 1; i <= min(m, k); i += 2)
	if(m - i <= k) s2 = add(s2 + C(m, i));
	cout << sub(res - mul(qpow(2, mod - 2), mul(s1, s2))) << '\n';
	}
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	cin >> T;
	init(2e5);
	while(T--) solve();
	return 0;
	}

# B. Divljak

简单 AC 自动机套树上差分。

简单说一下吧，先建 AC 自动机。

对于每个询问串，把它在 $fail$ 树上的点全都存下来，这些点单点加 1，再把两两 $lca$ 单点减 1。

查询的时候查子树和就行了。

树状数组维护，复杂度一个 $\log$ 。

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

	using namespace std;

	const int N = 2e6 + 10;
	int n, m;
	char s[N];

	int ch[N][26], tot = 1, id[N];

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

	int fail[N];
	vector <int> G[N];

	inline void build(){
	queue <int> q;
	for(int i = 0; i < 26; ++i) ch[0][i] = 1;
	q.push(1), fail[1] = 0;
	while(!q.empty()){
	int x = q.front(); q.pop();
	for(int i = 0; i < 26; ++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 = 2; i <= tot; ++i) G[fail[i]].pb(i);
	}

	int siz[N], son[N], dep[N];

	inline void dfs1(int x){
	dep[x] = dep[fail[x]] + 1, siz[x] = 1;
	for(auto y : G[x]){
	dfs1(y), siz[x] += siz[y];
	if(siz[y] > siz[son[x]]) son[x] = y;
	}
	}

	int top[N], dfn[N], tim;

	inline void dfs2(int x, int topfa){
	top[x] = topfa, dfn[x] = ++tim;
	if(son[x]) dfs2(son[x], topfa);
	for(auto y : G[x])
	if(y != son[x]) dfs2(y, y);
	}

	inline int lca(int x, int y){
	while(top[x] != top[y]){
	if(dep[top[x]] < dep[top[y]]) swap(x, y);
	x = fail[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
	}

	int c[N];

	inline void add(int x, int y){
	for(; x <= tot; x += x & (-x)) c[x] += y;
	}

	inline int ask(int x){
	int res = 0;
	for(; x; x -= x & (-x)) res += c[x];
	return res;
	}

	inline int ask(int l, int r) {return ask(r) - ask(l - 1);}

	inline bool cmp(int a, int b) {return dfn[a] < dfn[b];}

	inline void upd(char *s){
	int len = strlen(s), u = 1;
	vector <int> vec;
	for(int i = 0; i < len; ++i) u = ch[u][s[i] - 'a'], vec.pb(u);
	sort(vec.begin(), vec.end(), cmp);
	for(auto x : vec){
	add(dfn[x], 1);
	// cout << x << " " << dfn[x] << " " << id[1] << " " << ask(dfn[id[1]] - 1) << endl;
	}
	for(int i = 0; i < (int)vec.size() - 1; ++i)
	add(dfn[lca(vec[i], vec[i + 1])], -1);
	// cout << "tmp " << ask(dfn[id[1]] - 1) << endl;
	}

	inline int qry(int x){
	return ask(dfn[x], dfn[x] + siz[x] - 1);
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> s, insert(s, i);
	build(), dfs1(1), dfs2(1, 1);
	// for(int i = 1; i <= tot; ++i) cout << fail[i] << " ";
	// cout << endl;
	// for(int i = 1; i <= tot; ++i) cout << dfn[i] << " ";
	// cout << endl;
	cin >> m;
	while(m--){
	int op, x; cin >> op;
	if(op == 1) cin >> s, upd(s);
	if(op == 2) cin >> x, cout << qry(id[x]) << '\n';
	}
	return 0;
	}

# C. 交换

就是那道 JOISC 的题。

结论就是累加上每个点向左向右交换次数较少的那个。

简单说一下证明：就是考虑把最小的移到最左侧或最右侧，肯定选代价较小的，移动之后不影响其他数的顺序，就变成了一个子问题。

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

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 3e5 + 10;
	int n;
	int a[N], b[N];

	int c[N];

	inline void add(int x, int y){
	for(; x <= n; x += x & (-x)) c[x] += y;
	}

	inline int qry(int x){
	int res = 0;
	for(; x; x -= x & (-x)) res += c[x];
	return res;
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	for(int i = 1; i <= n; ++i)
	b[i] = i - 1 - qry(a[i]), add(a[i], 1);
	memset(c, 0, sizeof(c));
	for(int i = n; i >= 1; --i)
	b[i] = min(b[i], n - i - qry(a[i])), add(a[i], 1);
	int ans = 0;
	for(int i = 1; i <= n; ++i) ans += b[i];
	write(ans), puts("");
	return 0;
	}

# D. 零二（Zero Two）

比较离谱的题。

假设是个排列，设 $A_p = B_q = n$ 。

那么有 $\{A_1 \sim A_q\} = \{B_1 \sim B_q\}$ ，后半部分也相等。

设 $f_{l, r, x}$ 表示当前考虑 $l \sim r$ 的区间，最大值为 $x$ 时的序列个数。

令 $a_{pos} = x$ ，转移时枚举最后一个入堆的点（也就是入完之后一直弹堆，弹到 $x$ 被弹出来），左右可以分成两部分递归下去：

$f_{l, r, x} = \sum_{i = pos}^rf_{l, i, x - 1}f_{i + 1, r, x - 1}$

可能有点怪，也可以理解为枚举 $x$ 在 $B$ 中出现的位置，然后左右分开考虑，但是这样有瑕疵，最好还是能理解上面的东西。

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

	using namespace std;

	const int N = 110;
	const int mod = 998244353;
	typedef pair<int, int> P;
	int n;
	int a[N], f[N][N][N];
	P b[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 solve(int l, int r, int x){
	if(x == 0 \|\| l >= r) return 1;
	if(~f[l][r][x]) return f[l][r][x];
	int pos = -1;
	for(int i = l; i <= r; ++i)
	if(a[i] == x) {pos = i; break;}
	if(pos == -1) return f[l][r][x] = solve(l, r, x - 1);
	int res = 0;
	for(int i = pos; i <= r; ++i)
	if(a[i] <= x) res = add(res + mul(solve(l, i, x - 1), solve(i + 1, r, x - 1)));
	return f[l][r][x] = res;
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; ++i)
	cin >> a[i], b[i] = {a[i], i};
	sort(b + 1, b + 1 + n);
	for(int i = 1; i <= n; ++i)
	a[i] = lower_bound(b + 1, b + 1 + n, P(a[i], i)) - b;
	memset(f, -1, sizeof(f));
	cout << solve(1, n, n) << '\n';
	return 0;
	}

# A. 矩阵游戏

# B. Divljak

# C. 交换

# D. 零二（Zero Two）

20230215

2023 春季联赛游记