比赛链接：https://qoj.ac/contest/1302

队友开局秒 J ，后面 AC 了 L ，然后我去做 A ，搞了个结论，和队长说了一下，队长觉得很对，上去写，过了。

D 我开局就声称是 Runs 板子题，但是我不信真有板子题，在队长核善的邀请下还是上去写了 Runs ，然后一小时的时候 WA 了，后面发现是板子有点问题，半小时后过了。

队友写 G ，在两个小时的时候喜提 WA ，一直卡精度到三小时都没过，期间我搞了个 Border Series 上去把 B 过了，后面他们弃了。

后面和队长讨论 I ，搞了个看着很对的暴力，上去写过了。

后面和队友讨论 G ， 队长上去写了个高精度，在四个小时的时候过了，最后不会做 E ，遗憾离场。

G 我们精度差了，他们用 long double 存高精度，最后在除阶乘，我一开始声称说逐步乘精度可能会变好，队长说不会，原因精度差在回溯的减法，而在浮点数记录有效位数，除个数字不会影响有效位数，所以这是没有道理的，但是最后看题解发现题解就是这么做的，至于为什么这么做精度变好了，未知，神秘。

没啥错误，就是菜了。

正赛我肯定直接上 Runs ，但是训练赛怎样都无所谓，毕竟 Runs 确实有点大炮打蚊子的感觉，平时太过依赖科技不好，但写 Runs 也可以顺便查下板子（板子也确实错了），反正我个人认为怎样决策都对，不管他了。

部分题解：

A

首先假设每个点都选了 $Y$ ，所以现在变成要不要把 $Y$ 换成 $X$ 。

思考一下线性基，本质上是个线性方程组。

假设现在问你 $x$ 经过线性基后的最小值是多少，显然是从大到小，最高位相同就异或。

所以先把后手的线性基跑出来。

问题变成先手最大化线性基跑出来的最小值，注意到这是一个可以拆分的问题，即这是线性的。

所以可以先把每个可选的数字包括 $X$ 扔进去跑出最小值，然后在问这堆数字异或起来的最大值，求最大值再建个线性基就行了，时间复杂度：$O((n+m)\log{V})$

与题解和别人做法一致。

D

上 Runs 了。

注意到每个答案都一定在恰好一个 Runs 里，首先显然在一个 Runs 里。

其次考虑在两个 Runs 里，如果一个最小周期为 $p$ ，另外一个为 $q$ ，那么显然 $p+q\le len$ ，所以可以得到两个 Runs 周期相同，所以可以直接合并成一个 Runs ，矛盾，证毕。

那么求出 Runs 计数就行了。

但是这个能过洛谷的板子错了，你们有什么头猪吗？

不过还好错误不大，能在不会 Runs 具体过程的情况下猜出来，不然就真爆了。

看了题解：不是哥们，怎么优秀的拆分高中不会，上了大学还是不会啊。唐人就只会用科技解决问题，但是正解就不一样了。

首先，设长度为 $x$ 的极长周期串（重复至少两次）的子串为 $T_{1},…,T_{k}$ ，显然相邻两个串的交集 $<x$ ，所以考虑将原串以长度 $x$ 分段。

那么显然，每个极长周期串至少覆盖其中一个整段，而且显然，完整覆盖其中一个整段的极长周期串至多一个，所以这个时候就已经可以对每个段用 SA 直接暴力求解所有可能的极长周期串，或者二分 + Hash。

但是别急，还有性质，相邻两个段如果完全一样，则一定存在同时覆盖这两个段的极长周期串，$k$ 个段同理。

所以综上，设极长相等的段编号为 $l,r$ ，根据上面的结论，不需要求 $(r-l+1)$ 次极长周期串，求一次就行了，因为如果存在（$l<r$ 时一定存在），则覆盖 $[l,r]$ 的是同一个。而且显然，这个极长周期串覆盖 $[l,r]$ ，不覆盖 $l-1,r+1$ 。

但是这能带来什么进步吗？其实不能，只不过二分 + Hash 中二分的范围变小了罢了。

时间复杂度：$O(n\log{n})/O(n\log^2{n})$ 。

甚至求出所有串后，可以直接排序去重，得到的就是 Runs ，可以看成 Runs 一个很低门槛的等价替代品。

B

上 Border Series 了。

插入在前面可以把串翻过来，注意到翻过来后，整个串的 $Bd$ 是不会变化的，所以尝试维护 Bd 集合。

注意到 Bd 可以拆分成 $\log$ 段等差数列，那么你在维护的时候，直接合并相邻两段可以合并的等差数列到不能合并为止，最多只会有 $2\log$ 段，所以可以这样维护。

然后每添加一个字符的 Bd 集合怎样变化，手模一下就知道了。

时间复杂度：$O(n\log{n})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct node{
	int l, r, p;
};
typedef vector<node> VN;
bool check(node x, node y){//x.l > y.r
	if(x.l == x.r && y.l == y.r) return 1;
	if(x.l != x.r && y.l != y.r && x.p != y.p) return 0;
	if(x.l == x.r) x.p = 0;
	if(y.l == y.r) y.p = 0;
	int p = max(x.p, y.p);
	return x.l - y.r == p;
}
VN merge(VN x){
	VN tmp;
	while(!x.empty()){
		node y = x.back();
		x.pop_back();
		while(!x.empty()){
			node z = x.back();
			if(!check(z, y)) break;
			x.pop_back();
			y.p = z.l - y.r;
			y.r = z.r;
		}
		tmp.push_back(y);
	}
	reverse(tmp.begin(), tmp.end());
	return tmp;
}
VN fail;
int a[N * 2];
int llen, rlen;
int n;
bool check(int len, int t, int c){ //t = 0 : left
	if(!t) return a[rlen - len] == c;
	else return a[llen + len] == c;
}
int main(){
	cin >> n;
	llen = n + 1;
	rlen = n;
	for(int i = 1; i <= n; i++){
		string s, t;
		cin >> s >> t;
		int x;
		if(t[0] == 'd') x = 0;
		else if(t[0] == 'r') x = 1;
		else if(t[0] == 'm') x = 2;
		else if(t[0] == 'f') x = 3;
		else if(t[0] == 's' && t[1] == 'o') x = 4;
		else if(t[0] == 'l') x = 5;
		else if(t[0] == 's' && t[1] == 'i') x = 6;
		else assert(false);
		int type = s[0] == 'a';
		VN tmp;
		for(auto [l, r, p] : fail){
			if(check(r, type, x)) tmp.push_back({r + 1, r + 1, 0});
			if(l < r && check(l, type, x)) tmp.push_back({l + 1, r - p + 1, p});
		}
		if(i != 1 && check(0, type, x)) tmp.push_back({1, 1, 0});
		if(type == 0) a[--llen] = x;
		else a[++rlen] = x;
		fail = merge(tmp);
		int ans = 1;
		for(auto [l, r, p] : fail){
			ans++;
			if(l < r) ans += (r - l) / p;
		}
		cout << ans << "\n";
	}
	return 0;
}

题解做法：

注意到周期 $x$ 存在的时间是一段区间：$[x,?]$ ，二分 + Hash 确定这个区间就行了。

时间复杂度：$O(n\log{n})$ 。

但是我的做法用了科技，代码却意外的更短，绷不住了。

G

直接做 DP ，然后回溯 DP ，枚举最后一个数字是啥，然后求求答案就行了。

和题解一致。

I

注意到，空集和全集一定在里头。

全集用所有集合取并就行了，空集用所有元素去交就行了。

然后注意到每个元素所在的集合和其所在的大小最小的集合一一对应。

显然一个元素所在的大小最小的集合是唯一决定的，而这个元素所在的集合就是所有这个集合的超集。

所以至多 $5$ 种本质不同的观众，考虑把全集踢掉，只有 $2^4$ 种可能性，所以 $2^{20}$ 次方枚举一下就行了。

check 随便怎么 check 都行，只要不是太扯就行了。

至于计数，注意到集合有标号，我们选定了每种观众所在的集合，所以直接计数就是不会重的。

至于计数吗，容斥一下就行了。

时间复杂度：$O(\mathrm{能过})$

看了题解，发现分析的有点 SB ，$\binom{2^{4}}{5}$ 确实可以看成 $2^{20}$ ，但是显然 $2^{2^{4}}$ 也就是 $2^{16}$ 是一个显然的更小的界。

但是那个线性递推的做法，说句实话，我没懂。

Plan

补题

把两个字符串的题目写写代码。