Season 2022
#6299. Binary String
如果 \(0\) 的个数小于 \(1\) 的个数那么就反转 \(01\) 以及反转序列，接下来假设 \(0\) 的个数大于等于 \(1\) 的个数。
称有 \(11\) 的序列为”未完全展开的“，那么序列的种类数有两个阶段：展开过程中和展开之后的。
在展开之后如果知道序列那么用 KMP 算最小周期即可计算不同的方案数，展开过程中显然均是不同的，所以只需要求出展开时间和展开后长什么样即可。
考虑三个连续的 \(01\) 长度为 \(x,y,z\)，其中 \(x,z\) 是 \(1\)，\(y\) 是 \(0\)，如果 \(x>y\)，那么在 \(x\) 完全展开之前，\(z\) 就会和 \(x\) 接触，那么总展开时间就是 \(x+z\)，这相当于将 \(z,y\) 交换。因此可以用栈暴力模拟这个过程，然后首尾相消。这样得到的是若干段 \(0\) 和 \(1\)，满足所有 \(1\) 在展开之前都不会碰到另外的 \(1\)，那么展开时间和最终序列都是容易求的。时间复杂度 \(O(n)\)。
#5503. Euclidean Algorithm
考虑 \(2a-b\) 这样的操作能造出啥数列。
手摸一下可以摸出结论：只会产生对于所有自然数 \(k\)，\((k+1)a-kb\) 或者 \((k+1)b-ka\) 中的自然数。证明不难，归纳就行。
设 \(g=\gcd(a,b)\)，则显然 \(g\leq a\)，所以只有 \((k+1)a-kb\) 能产生 \(g\)，解得 \(k=\frac{a-g}{b-a}\)，也即要求 \(b-a\mid a-g\)。
不妨先转化一下变成 \(b-a\mid b-\gcd(a,b-a)\)，用 \(a\) 代换 \(b-a\) 可以得到 \(a\mid b-\gcd(b,a)\)。枚举 \(g=\gcd(b,a)\)，设 \(a'=\frac{a}{g},b'=\frac{b}{g}\)，则要求 \(a'\mid b'-1\) 且 \(\gcd(a',b')=1\)。容易发现后面一个条件是废话，那么也就是要求 \(a'\mid b'-1\)，对于所有 \(b\) 的约数 \(g\)，总是有 \(d(\frac{b}{g}-1)\) 个 \(a\) 满足条件，那么枚举 \(\frac{b}{g}\)，计算式就变成 \(\sum\limits_{i=1}^{n}{\lfloor\frac{n}{i+1}\rfloor d(i)}\)。对 \(i\) 除法分块，\(\sqrt n\) 计算 \(d(n)\) 前缀和即可做到 \(O(n^{0.75})\)。
#6308. Magic
假设我们选定了一些位置，钦定其和下一个位置不同，那么要怎么判定存在一种方案？
也就是说我们需要让两个点不同，那么所有将两个区间覆盖成相同的都不能作为这两个点的最后覆盖。只有以 \(i\) 为右端点和以 \(i+1\) 为左端点的区间可以，也就是说我们要求这两个中至少一个成立。
那么现在需要找到限制之间的矛盾关系。对于两个同是左端点的限制，让左端点靠右的区间后做，一定最优，因为这样可以让两个左端点都 win，两个右端点也是同理。那么矛盾只在左右端点之间。如果两个区间的限制都包含了对面的限制，那么肯定有一个不行，这会导致矛盾。其余情况可以归纳说明没有矛盾。
如果我们再将 \(i\) 是右端点，\(i+1\) 是左端点的连边，限制其不能同时选，那么最多能满足的限制个数就是最大独立集的个数，可以 bitset 优化匈牙利算法做到 \(O(\frac{n^3}{\omega})\)，常数很小，可以通过。
#6410. Classical DP Problem
这个题和这场的 E 是一个题?
首先最小值是容易求的，只需要找到点 \((x,y)\) 满足 \(\min(x,y)\) 最大即可。
同时考虑这些点可以怎么放，设答案为 \(x\)，若 \(A_x>x\)，那么在 \([1,x]\) 行中都要放一个，同时还要覆盖 \(B_x>x\) 的列。也就是说，每个数有一个放的范围，同时有一个范围内的数必须选至少一个，求方案数，可以 \(O(n^2)\) dp 解决，对于 \(B_x>x\) 同理，若相等则需要想两个方向分别计算一次，然后减去重叠的。
E 就是考虑怎么优化这个 dp。考虑容斥，枚举至少选一个中有多少个没选，乘以选择方案和容斥系数，那么结果是一个关于多少个没选的多项式，可以先分治 NTT 求出这个多项式，然后多点求值。
另外，这个多项式可以分解成若干个一次式的乘积，并且查询的 \(x\) 连续，可以先求离散对数化乘为加，然后用任意模数 FFT 卷积计算，最后搞回来就行，复杂度可以做到 \(O(n\log n)\)，不比上面那东西 practical 多少。
#6415. Classical Minimization Problem
首先考虑如果 \(y\) 互不相同怎么做，这样只有 \(x\) 要求不同的限制，这是经典问题。具体的，每次选出 \(x\) 个数最多的和剩下不同行的一个，这样能尽量消掉最大的。
然后现在有两个维度，每次只需要找到行最大和列最大，并且不在同一行的匹配即可。如果行列的最大值都大于等于 \(2\)，那么只需要 \(O(1)\) 次查找就一定能找到一对匹配的。否则转化成一维问题，可以按照上面那个方法做。
Season 2023
Stage 1: Qindao
E. Infinite Parenthesis Sequence
Stage 3: Binjiang
C. Clique Challenge
Stage 5: Northern
J. Sets May Be Good
首先这个为偶数就非常怪异，不妨将其变成求偶数减奇数，最后加上 \(2^n\) 再除二就是答案。
考虑将第一个点拿出来看。如果第一个点没有边连出去，那么第一个点可以任意，否则如果第一个点连出去的边选了奇数个，那么第一个数选与不选会改变选的边数的奇偶性，则正负会相消。因此只需要考虑第一个点连出去的边是偶数个的情况，这种情况下 \(1\) 不论如何选都不会改变奇偶性，则当前的答案就是去掉 \(1\) 之后的图，带着一个限制的答案再 \(\times 2\)
问题在于带着一个限制的答案怎么求？你可以注意到，这个限制和原来的限制，即要求边数总和是奇/偶长得差不多，所以如果你把这个限制当成一个方程直接代入到原来那个方程里面去，就可以消掉一个元，并可能改变原限制的奇偶性，都是可以维护的。因此直接递归时间复杂度 \(O(n^3)\)。
H. Shared Memory Switch
感觉上这个问题不能在线处理，因此可以考虑离线之类的东西。
我们考虑在每一秒钟结束的时候决策这一秒弹掉了哪些点，并用一棵线段树维护每秒的缓冲区还有多少容量。因为对于每个队列来说，从这个点进来到结束的区间要么包含要么不交，所以新的一个区间不可能去反悔前面的区间。所以新的区间可以直接按照右端点从大到小选即可。时间复杂度 \(O(n\log n)\)。
E. Elimination Race
什么 b 题 \(O(\frac{n^4}{\omega})\) 出 \(n=500\) 还开 \(0.7s\) 恶心人是吧。
分开考虑每个数 \(x\) 后面的数，将比赛作为左部点，除了 \(x\) 的数作为右部点，一场比赛能向这场比赛 \(x\) 后面的点连边。我们断言，能让这个人剩下的充要条件是有完美匹配。
必要性显然，充分性可以构造证明：如果有某个序列最后是匹配了的，直接选了，然后弹掉每个序列，在最后的已经删掉的点。如果没有可以直接匹配的，则考虑每个还没用过的比赛，将其的匹配点与最后一个点连一条边，这样一定会形成一个基环内向树，则直接选择环上的点的比赛即可。
同理这个构造可以直接用，于是做完了。好像后面的构造 \(O(n^2)\) 是瓶颈，不是很好绷。
所以题解写的 \(\frac{1}{3}\) TL 怎么做到啊？