A. Kendama Challenge
对于存在一段的限制，考虑容斥，变为 \(1\) 减去不存在任何一段的概率。
考虑没成功的选手，需要相邻的选手距离 \(\le K\) 才合法。
于是设 \(f_i\) 为 \(i\) 是没成功的选手，且 \([1, i]\) 满足条件的概率。
转移即为 \(f_i = (1 - p_i)\sum\limits_{j = i - k}^{i - 1} f_j\prod\limits_{h= j + 1}^{i - 1}p_h\)。
把 \(\prod\) 拆成前缀积形式，对于 \(\sum\) 类似滑动窗口维护即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
submisson。
B. Cat Cut
分析答案结构。
对于每次的截断，可以看作是保留了 \(s_i\) 的一个前缀直接拼在了当前串后，直到最后再保留下最后 \(m\) 个字符。
于是能分析出可能的结构（以下中的任一元素也可以是空串）：
- \(\operatorname{suf}(s_1) + \operatorname{pre}(s_2) + \cdots + \operatorname{pre}(s_n)\)。
- \(\operatorname{substring}(s_i) + \operatorname{pre}(s_{i + 1}) + \cdots + \operatorname{pre}(s_n)(i\ge 2)\)。
刻画一下可能的转移路线，此处记第 \(i\) 个字符串的第 \(j\) 个字符为 \((i, j)\)，转移如下：
- \((1, i)\to (1, i + 1)(i < m)\)。
- \((1, m)\to (i, 1)(i\ge 2)\)。
- \((i, j)\to (i, j + 1)(j < m)\)。
- \((i, j)\to (i', 1)(i' > i)\)。
转移路线就可以认为是 \((i, j)\) 的下一个字符和之后的所有开头（这个转移对 \((1, i)(i < m)\) 不成立）。
对于字典序最小，考虑直接从前向后贪心选能选的最小的字符，只需维护可选的下标集合，在每次选出一个字符后和准备选下一个字符前更新集合元素即可。
用 bitset 做这一个过程，对于最小字符直接二分判断有无交，可以做到 \(\mathcal{O}(\frac{nm^2\log |\Sigma|}{w})\)，这居然是能过的，，
submisson。
C. Partition AND/OR Aggregation
对于 \(S(l, r) = \frac{\operatorname{And}(l, r)}{\operatorname{Or}(l, r)}\)，如果固定 \(l\) 来看，那么 \(S(l, r)\) 可能的取值只有 \(\mathcal{O}(\log V)\) 种（对于 and 每次改变至少少 1 位，对于 or 每次改变至少多 1 位）。
这也说明答案的取值也只有 \(\mathcal{O}(n\log V)\) 种。
先来考虑求 \(\max\)。
首先有一个贪心的想法，就是选 \(k - 1\) 个长度为 \(1\) 的段，剩下直接分一段，于是 \(k < m\) 时答案肯定为 \(1\)。
接下来考虑 \(k = m\)，排序后最小的段为 \(v\)，这就说明所有段都需要 \(\ge v\)，于是考虑二分答案 \(v\)。
因为 \(S(l, r)\le S(l + 1, r), S(l, r - 1)\)，这说明若 \(S(l, r)\ge v\) 且 \(l < r\)，那么随意分裂 \([l, r]\) 这个区间，\(S\) 值一定也都 \(\ge v\)。
这说明 \(\ge v\) 的段数一定是受到一个区间的约束的，上界是 \(n\)，只需关注下界了。
下界是好办的，每次尽可能扩张的更远即可，因为这相当于是让接下来的一个段前面没有了附加值，一定不劣。
于是 \(\max\) 就在 \(\mathcal{O}(n\log (n\log V))\) 的复杂度内解决了。
接下来考虑 \(\min\)。
此时 \(k\) 与 \(m\) 的大小就没有什么特殊性了。
类似 \(\max\)，考虑二分答案 \(v\)，那么限制就是要有 \(m - k + 1\) 个段的值 \(\le v\)，并且总共至少需要有 \(m\) 个段。
如果没有总共 \(m\) 个段的限制，这是好做的。
考虑对于每个 \(l\) 根据 \(S(l, r)\) 不同分出的 \(\mathcal{O}(\log V)\) 个段，那么就可以找到 \(S(l, r)\le v\) 的最小的 \(r\)，记为 \(r_l\)。
直接考虑 dp，记 \(f_l\) 表示 \([l, n]\) 能够划分出的 \(S \le v\) 的段数的最大值，转移为 \(f_l = \max(f_{l + 1}, f_{r_l + 1} + 1)\)，直接判断 \(f_1\) 与 \(m - k + 1\) 的大小即可。
现在的问题就是总段数的限制，贪心的考虑，除了钦定为 \(\le v\) 的段，其他的元素肯定都是单独划段最优。
这其实也就是最小化选出的 \(m - k + 1\) 个段的总长，若总长 \(\le n - (k - 1)\)，就可以选出至少 \(k - 1\) 个单段，也就满足了限制。
于是问题转化为，求出选出 \(m - k + 1\) 个 \(S\le v\) 的段的最小总长。
考虑记 \(f(i)\) 为选出 \(i\) 个 \(S\le v\) 的段的最小总长，感性理解一下 \(f(i)\to f(i + 1)\) 的过程，每次 \(f(i + 1) - f(i)\) 一定是不降的，也就是 \(f(i)\) 应该是个凸函数。
于是使用 wqs 二分，内部转移与上文的 \(f_l\) 基本一致，得到 \(f(m - k + 1)\) 的值即可。
时间复杂度 \(\mathcal{O}(n(\log n + \log V)\log (n\log V))\)。
submission。
D. Campaign Speech
经过手玩可以知道行走路线一定是从一个点开始直接顺着边界走直到走完所有点。
所以长度就是选择路线上相邻的两个点，除这两个点间剩下的边都要走，那也就是找到两点间距离的最大值。
可以考虑以一个点为原点，求出所有点的相对距离。
在沿着边界走的时候判断这条边是横边还是竖边，对于每一行每一列分别用 set 维护之中的点即可。
时间复杂度 \(\mathcal{O}((n + m)\log n)\)。
submission。
E. Ball Dumping Golf
当 \(m = 1\) 时，整个图由许多环组成，最小操作数即为环数。
于是类比到 \(m > 1\) 的情况，此时的每个点都满足入度出度均为 \(m\)，所以每个连通块都能找到一条欧拉回路，最小操作数即为连通块数。
那么考虑求出 \(f_i\) 表示 \(i\) 个点恰好成一个连通块的方案数。
这不太好直接求，考虑对其 EGF 求 exp 后得到的 \(G(x) = \exp(F(x))\)。
\(g_i\) 表示的是 \(i\) 中有若干个连通块的方案数，也就是这 \(i\) 个点的 \(mi\) 条入边出边都是这 \(i\) 个点的方案数，于是可知 \(g_i = \frac{(mi)!}{(m!)^i}\)。
对 \(G(x)\) 求 \(\ln\) 后即可得到 \(F(x)\)，也就得到了 \(f_i\)。
对于统计答案，考虑对每个连通块单独统计贡献，枚举大小为 \(i\) 的连通块，方案数即为 \(f_ig_{n - i}\binom{n}{i}\)。
时间复杂度 \(\mathcal{O}(nm + n\log n)\)。
submission。
F. 1e16 Cities
因为式子中既有 \(\operatorname{lcm}(i, j)\) 也有 \(\gcd(i, j)\)，这启发去换元。
记 \(i = i'd, j = j'd(\gcd(i', j') = 1)\)，式子变为 \(di'j' = Ad + B\)。
那么经过一些等式变换，能得到以下两个式子：
- \(d = \frac{B}{i'j' - A}\)。
- \(i'j' = A + \frac{B}{d}\)。
第一个式子说明了 \(d\) 一定需要是 \(B\) 的因数，第二个式子说明了固定 \(d\) 后 \(i'j'\) 也就固定了。
因为值的大小是 \(10^8\) 级别的，因数个数不多，直接枚举 \(d\) 后枚举 \(i'\) 判断 \((i', j')\) 是否合法即可。
时间复杂度 \(\mathcal{O}(d(V)(\sqrt{V} + d(V)\log V) + (d^2(V) + q)\log (d^2(V) + q))\)，其中 \(V = 10^8\)。
submission。
G. The Symbolic Tree
记 \(f_{u, i}\) 表示 \(u\) 当前填的数是 \(i\) 的方案数，转移即为 \(f_{u, i} = \prod\limits_{v\in \operatorname{son}(u)} \sum\limits_{j = 1}^i f_{v, j}\)。
这样做只能做到 \(\mathcal{O}(nk)\)。
考虑另一个 dp，记 \(f_{u, i}\) 表示 \(u\) 子树满足条件且填了 \(i\) 种不同的数的方案数。
这样虽然只能做到 \(\mathcal{O}(n^3)\)，但是这其实说明了答案最后可以表示为 \(\sum\limits_{i = 1}^n f_{1, i}\binom{k - 1}{i - 1}\)，也就是答案一定是一个 \(n - 1\) 次的多项式。
直接插值即可。
时间复杂度 \(\mathcal{O}(n^2)\)。
submission。
I. Xor Magic Square
偶数的情况是简单的，\(n^2\) 个元素都为 \(1\) 即可。
对于奇数的情况，因为 \(n\) 为奇数，所以不能只是构造 \(1\oplus 1 = 0\) 这种“消除”，就需要引入奇数个数的“消除”，就是 \(1\oplus 2\oplus 3 = 0\)。
于是只对于行分析，每一行的和至少为 \(n + 3\)（\(n - 2\) 个 \(1\)，\(1\) 个 \(2, 3\)），答案就有下界 \(n(n + 3)\)。
写个搜索会发现 \(n = 5\) 直接搜出来了一个合法解：
1 1 1 2 3
1 1 2 3 1
2 1 3 1 1
3 2 1 1 1
1 3 1 1 2
对于 \(n\) 更大的情况，自然的考虑增量构造，具体的，对于 \(n\to n + 2\)，只需增添如下边框即可：
2 1 ... 1 3
1 1
. .
1 1
3 1 ... 1 2
对于 \(n = 1\)，显然无解。
对于 \(n = 3\)，考虑独立开每一位，只分析 \(01\) 的情况，会发现 \(a_{2, 2}\) 始终为 \(0\)，于是无论如何组合 \(a_{2, 2}\) 始终为 \(0\)，无解。
submission。
J. Sum of max of iai
考虑 \(x = \sum\limits_{i = 1}^{n^2} [x\ge i] = n^2 + 1 - \sum\limits_{i = 1}^{n^2} [x\le i]\)。（这里转成 \([x\le i]\) 的原因是 \(f(a)\) 的求法是取 \(\max\)。）
于是可以先让答案为 \(n!(n^2 + 1)\)，再枚举 \(x\)，减去 \(f(a)\le x\) 的 \(a\) 的数量。
\(f(a)\le x\) 说明 \(\max (i a_i)\le x\)，也就说明 \(\forall i, ia_i\le x\)，就能得到 \(a_i\le \lfloor\frac{x}{i}\rfloor\)。
因为 \(\lfloor\frac{x}{i}\rfloor\le \lfloor\frac{x}{i - 1}\rfloor\)，这说明 \(a_i\) 的限制是具有“包容性”的，也就是说，按照 \(i\) 从 \(n\) 到 \(1\) 去选择 \(a_i\) 的值即可，方案数即为 \(\prod\limits_{i = 1}^n (\min(n, \lfloor\frac{x}{i}\rfloor) - (n - i))\)。
考虑到 \(\forall i, \min(n, \lfloor\frac{x}{i}\rfloor)\) 的取值只会有 \(\mathcal{O}(n)\) 次变化，整个式子的值也就只有 \(\mathcal{O}(n^2)\) 次变化。
只需要预处理好 \(1\sim n\) 的逆元，\(x\) 从 \(n^2\) 到 \(1\) 过程中 \(\mathcal{O}(1)\) 修改每一个变化，即可做到 \(\mathcal{O}(n^2)\)。
对于找到需要的变化，可以直接把 \(\mathcal{O}(n^2)\) 个变化用桶排直接排好。
时间复杂度 \(\mathcal{O}(n^2)\)。
submission。
L. Make Many KUPC
根据 \(x_1 < x_2, y_1 < y_2, x_1y_1 + x_2y_2 > x_1y_2 + x_2y_1\)，过程中肯定是让尽量大的 KUPC 匹配在一起。
于是直接倒着维护当前的 KUPC，UPC，PC，C，每次加入一个字符就和最大的能够匹配的后缀合并，此时大小顺序也已经保证（先加入的比后加入的大），直接用队列维护即可。
submission。
M. Linked VERSE
对于 \(x \gets \max(x - c, 0)\)，直接当作 \(x\gets x - c\) 并且此时多了一个为 \(0\) 的值。
于是答案就可以表示为：从开头或是 \(a_i = -1\) 的 \(i + 1\) 以值为 \(0\) 出发，经过 \(a_i\ge 0\) 则 \(+a_i\)，经过 \(a_i = -1\) 则 \(-c\) 的最大值。
再进一步考虑，如果 \(a_{i} = -1, a_{i + 1} \ge 0\)，则如果从 \(i + 2\) 开始肯定不比从 \(i + 1\) 开始优。
于是可以把起点给扩展到任意位置，也就是说答案就是 \(a_{i} = -1\) 则替换为 \(a_i = -c\) 的最大子段和（包含空子段）。
那么为了找到所有子段的信息，考虑分治。
对于 \(l = r\) 的边界是简单的，此时对应的就是 \(-c\) 或者 \(a_i\)。
对于 \(l < r\)，此时就是找到中点 \(p\)，要得到左端点在 \([l, p]\)，右端点在 \((p, r]\) 的子段信息。
因为此时的答案形态就是 \(k(-c) + b\) 的形式，这启发去维护凸包以减少信息量。
于是对于左端点只需要维护所有 \([l, p]\) 的后缀信息的凸包，对于右端点同理维护所有 \((p, r]\) 的前缀信息的凸包，合并时就是凸包合并。
最后求答案时只需要把之前得到的所有可能在凸包上的元素再跑一次凸包即可，可以离线下来做也可以在线直接二分斜率。
时间复杂度 \(\mathcal{O}(n\log n + q\log q)\)。
submission。
N. Cellular Component Constellation
对 \(m\) 卡一个最基本的界：因为每个颜色的连通块大小种类有 \(m\) 种，那么需要的格子数至少就是 \(\frac{m(m + 1)}{2}\)，2 个颜色需要的格子数至少就是 \(m(m + 1)\)，所以 \(m \ge n\) 时无解。
于是来考虑界最紧的情况：\(m = n - 1\)。
因为此时只需要 \(n(n - 1)\) 个格子，于是考虑再卡紧一点，尝试找到只需要 \(n(n - 1)\) 个格子的解。
那此时如果每个连通块都是平铺的形状看着就不太好构造了，于是尝试把每个连通块做成一个拐角的样子：
.#.
##.
...
会发现此时就能构造出 . 的 \(1, 5\cdots\)，# 的 \(3\cdots\)。
那要构造出 . 的 \(3\cdots\)，# 的 \(1, 5\cdots\)，就只需要对称过去了：
.#.#.#
##.#..
...###
那对于偶数，很简单的想法就是奇数 \(\pm 1\)，于是再对称一下，就有了以下构造（分别对应 \(n = 6, 5\)）：
.#.#.# .#.#.#
##.#.. ##.#..
...### ...###
###... ###...
..#.## ..#.##
#.#.#.
#.#.#.
那么接下来就只需要把 \(m\times (m + 1)\) 扩充到 \(n\times n\) 了。
这个时候为了不影响已有的结构，考虑每次增量一行或者时一列，都与相邻的行 / 列的元素对应不同。
会发现此时增量的连通块大小至多为 \(2\)，且当 \(m = 1\) 时只会有大小为 \(1\) 的连通块，构造成立。
submission。
O. Xor Triangle
注意到 \(x \oplus y = x + y - 2(x\ \&\ y)\le x + y\)，\(y = x \oplus (x\oplus y)\le x + (x\oplus y)\)，所以考虑容斥 \(x + y = x\oplus y, x + (x\oplus y) = y, y + (x \oplus y) = x\) 三种不合法的情况。
考虑拆位，每一位有 \(4\) 种情况：000, 011, 101, 110。总方案数即为 \(4^n\)。
当 \(x + y = x\oplus y\) 时，每一位就只能是 000 或 011 或 101。剩下两种情况同理，不合法的方案数即为 \(3\times 3^n\)。
但是若 \(x, y, x \oplus y\) 中有 \(0\) 时，上述等式就会有 \(2\) 个成立。假设若 \(x = 0\)，则每一位只能是 000 或 011，剩下两种情况同理，于是还要加上 \(3\times 2^n\)。
还有当 \(x, y, z\) 都为 \(0\) 时，上述 \(3\) 个等式都成立，所以需要 \(-1\)。
最后答案即为 \(4^n - 3\times 3^n + 3\times 2^n - 1\)。
时间复杂度 \(\mathcal{O}(\log n)\)。
submission