0102
P8164 [JOI 2022 Final] 沙堡 2 / Sandcastle 2
https://www.luogu.com.cn/article/ztfmbbo6
考虑怎么刻画一个矩形是合法的：每个点连向比它小的最大值，最后形成一条链。因为每个点互不相同，所以有一个充要就是，给每个点一个 \(a_i-x\)（其中 \(x\) 是比它小的最大值，没有就是 \(0\)）的权值，如果当前点比周围四个点都要大则说明它是链头，就是 \(1e7-x\)。这样一个矩形如果是合法的，权值和就是 \(1e7\)。
这样就好做了，我们直接枚举上下边，然后从左到右扫描线右端点，求出有多少个合法的左端点即可。
0104
https://codeforces.com/contest/2180
D Insolvable Disks
好吧，这种套路我确实没见过。
考虑一个点 \(i\) 开始的连续相切段最远能够相切到 \(f_i\)，显然 \(f_i\) 是不减的。那么我们直接贪心取 \(x\to f_x,x+1\to f_{x+1},\cdots\) 就好了。
这是因为有这样：
--- ---如果有一个下面的能够更优，必定是因为很长：
--- ---
-------但是这样的话，它就长过上面的第二段了，显然不合法。
所以直接贪心就是对的。
E No Effect XOR
阅读的是 https://www.luogu.com.cn/article/osdymemx。这里用到了异或一一对应的性质。我们希望 \([l,2^k)\) 异或上一个 \(x\) 后依旧是自己这个区间的值，那么相当于 \([0,l)\) 异或上 \(x\) 后依旧是自己区间内的值。
利用这个性质就很好做了。
F1 Control Car
没有用题解的做法，就是考虑我们将计数转概率，那么设计状态 \(f_{i,j,0/1,0/1}\) 表示从 \((1,1)\) 走到 \((i,j)\)，其中 \((i,j)\) 右上角是否向下，\((i,j)\) 左下角是否向右。直接 dp 就好了。只保存这两个是因为这两个可能关系到两次移动，而其他只关系一次移动。
F2 就是用矩阵乘法优化就好了。
G Balance
https://www.luogu.com.cn/article/8d19d6fz
我们需要注意到的是，原数列是一个回文串，所以可以正着算一遍，反着算一遍加起来得到答案的两倍，以此删除掉式子中的某些项。
这样我们就可以直接推式子做了。每次取出中位数其实也很有门道，看题解吧。主要就是发现一种数是模 \(4\) 周期的取出，我们直接从后往前扫就好了。
0105
P6168 [IOI 2016] railroad
这种题需要考虑使用欧拉回路建图。我们先建出每个速度的节点，然后考虑将 \(\le s\) 特化为 \(=s\)，然后加速不收钱，减速收钱。此时我们需要使得整张图所有边都被经过，所以就要补边。我们考虑：跨过某条边的加速边和减速边数量一样，根据这个补全图，然后图可能不连通，再用 mst 求出把图弄联通的最小代价即可。
https://www.luogu.com.cn/article/wu9wc3lb
P5294 [HNOI2019] 序列
首先需要学习保序回归。这里有一个很好看的保序回归的解释：
这是经典的「全序集上的保序回归问题（\(L_{2}\)）」，时间复杂度可以做到 \(O(n)\)。
Lemma 1. 如果 \(a_i>a_{i+1}\)，则最终取 \(b_i=b_{i+1}\) 一定不劣。
Proof. 考虑使用调整法，分为以下几种情况：
- \(b_{i} \ge a_{i+1}\)，做调整 \(b_{i+1}\gets b_{i}\) 一定不劣。
- \(b_{i+1} \le a_i\)，做调整 \(b_{i}\gets b_{i+1}\) 一定不劣。
- \(b_{i}<a_{i+1}<a_i<b_{i+1}\)，做调整 \(b_{i} \to a_{i},b_{i+1}\to a_{i}\) 一定不劣。
考虑一对 \(i,i+1\) 满足 \(a_{i}>a_{i+1}\)，不妨钦定 \(b_{i}=b_{i+1}\)，那么它们可以被合并为一个变量 \(x\)（保持序列其余位置不变），且代价函数为 \(f(x)=(a_{i}-x)^2+(a_{i+1}-x)^2\)。
https://www.luogu.com.cn/article/b8247llu
所以可以用单调栈维护上面的过程。
这道题我们就因为每次只会修改一个，所以先正着做一遍，反着做一遍，正反两个单调栈再加上中间这个。中间这个怎么合并呢？我们需要二分一下。注意到左右端点具有单调性，详见：https://www.luogu.com.cn/article/3cerr8vu
P6167 [IOI 2016] shortcut
二分答案，直接硬写出来式子，然后相当于不满足第一个就要满足第二个。判定是否存在一个建快捷方式的方案使得满足。把绝对值拆了之后是个二位偏序，但是会发现其中一维其实没有作用，如果不满足一定不优。所以可以直接做一维偏序，做到 \(O(n\log nv)\)。
https://www.luogu.com.cn/article/dc3hazci
0107
vp The 3rd Universal Cup. Stage 37: Wuhan 记录。
L. Subsequence
签到题。将序列排序后，枚举最小值和中位数，然后就可以算出最大值，check 一下对不对就好了。
非常可惜的是写急了，罚了两发。第二次甚至样例都没过/wul。
J. Dictionary
考虑直接在反串上建出 SAM，找到某个串对应的节点后，就是非常经典的将 fail 树上的子树内全部打上 tag，统计 tag 的点的数量。这个直接暴力 dfs，跑到一个已经被打了 tag 的点就跳出来就好了。
M. Flight Tracker
发现题目给我们的坐标非常奇怪，研究后发现是：将球心射到某个点上，形成的射线交球面的交点。我们发现我们可以根据两个这种坐标算出它们对应的两个点的距离，同时答案是凸的，于是直接三分就好了。
注意注意，acos 里面传入 1+1e-18 也会返回
nan，务必特判！
H. WildFire, This Is for You!
可以使用 Python。
考虑 checker 怎么写。枚举 \(|i|+|j|<k\)，然后令所有的 \(\gcd(x+i,y+j)\neq 1\)；并判断是否存在一个 \(|i|+|j|=k\) 使得 \(\gcd(x+i,y+j)=1\)。
我先忽略了后面那个条件。然后只要使得 \(x+i\) 和 \(y+j\) 存在一个共同的因子即可。我令这个因子是一个质数。那么就是 \(x\equiv-i \pmod {prime},y\equiv-j\pmod {prime}\)，暴力跑 crt 合并。发现竟然第二个条件莫名其妙成立了（大概因为 crt 合并出来的是最小解导致的），但交上去 wa 了。
发现是位数太长了。考虑优化，每次我们不会弄一个新的质数，而是把质数从头到尾枚举一遍，如果某个质数丢进去做 excrt 没有报错，就用这个，直接卡到了 1300 位，然后就可以通过了。
K. Las Vegas
题解为什么要上下界网络流/yiw？
最开始考虑的是 meet in middle，但是不太会做。考虑这个数据范围也有可能是网络流，所以建图。
二分图，左部点是游戏场，右部点是玩家。我们发现每个游戏场会有三种结果：我放最多的钱成为第一名，我放第一名的钱数让第二名赢，我摆烂不放让第一名赢。
这三种边有三种代价，所以每个游戏场向对应玩家连流量为 1，代价为对应代价的边。源点向每个游戏场连流量为 1，代价为 0 的边。
然后玩家要向汇点连边，我们枚举我能赢 k 场，其他人赢的场数都要小于等于 \(k\)，那么就每个人（除了我）向汇点连流量为 k，代价为 \(0\) 的边，而我则向汇点连流量为 k 代价为负无穷的边，这样我们就会尽可能把我的 k 个流量流完。
太神奇了，竟然就过了。确实这种负无穷边可以让某个边流完。
D. Odd and Even
再给我两个小时都做不出来。
感觉在大规模复述官方题解，建议先看了官方题解，然后再看这个，这里还写了具体怎么实现。
发现只和奇偶性有关，所以我们变成 01 串，再做一个前缀和（异或），就变成了新的 01 串（不过段数稍微有点多，但是这不重要，先不考虑）。
我们现在需要选择 \(r+1\) 个数，令相邻不同数对（或相同数对）尽可能多。其中第一个和最后一个必选。
考虑 p 最大怎么做，发现肯定是尽可能选不同的，设前缀和段数为 \(t\)，那么答案就是 \(t-1\)，但是可能 \(p\) 达不到，所以要和 \(p\) 取一个 min，并且这个答案和 \(t-1\) 的奇偶性要相同（因为最开始答案是 \((t-1)\bmod 2\)，每次加入一个新段，答案奇偶性一定不会变）。
考虑 q 最大怎么做，相当于令 \(p\) 最小。我们换个方向考虑：对于每个 \(p\)，算出其 \(r\) 最大能是多少。因为答案具有单调性，就可以二分然后得到对应的 \(p\)。
也就是我们需要求出每个 \(p\) 最大的 \(r\)。
考虑这么一件事情，如果同时有两个相邻的块不选，一定不优，可以选择其中一个使得 \(p\) 不变，\(r\) 变大。
就此，我们发现选择情况一定是若干个 「选-不选-选-...-选-不选-选」 合并起来的。每次我们可以选择这么一个极长连续段，将其选或不选的情况反转，使得 \(p\) 减少 \(2\)，\(r\) 减少一定值。
这很类似于反悔贪心，我们用小根堆每次弹出 \(r\) 最小的减小值即可，然后将新的
「选-不选-选-...-选-不选-选」
段加入堆中。注意第一段和最后一段是不能反转的（\(0\) 和 \(t-1\) 必选）。三个极长段
101 101 101，反转中间那个，会变成
101 010 101，相当于将相邻两个极长段合并起来。
直接用 set 合并是可以的，但是是 \(O(t)\) 的复杂度。发现主要是因为原本的 1
做了前缀和之后就会变成 1010101...，形成很多段。
但是注意到这些段长度一定为 1，也就是操作这些段只会让
\(r\)
减小一。我们可以假设这些段已经被处理了，只模拟最后 \(O(n)\) 次操作，那么如果输入的 \(r\) 比初始的 \(r'\) 还要大，答案就是初始的 \(r'\) 对应的 \(p'\) 算出的 \(2(r-r')+p'\)。
考虑怎么实现比较好看，我们将段分为三种：全 0 段，全 1 段，101...101 段，其中第三种段前后只能接全 0 段。全 0 段前后不能是全 0 段，否则可以合并，全 1 段同理。
全 0 段，全 1 段已经就是一段了，一整个加进去即可。而 101...101 段，经过前面全 \(p\gets p-1\) 的处理，会变成 「选-不选-选-...-选-不选-选」，也是一个段了，也可以直接加进去了。
然后就做完了，怎么感觉我讲的这么抽象呢？放个代码吧：https://qoj.ac/submission/1897592。
0108
P11994 [JOIST 2025] 外郎糕 / Uiro
我们注意到：
- 对于每种数，一定是前面全部选
+，后面全部选-； - 贪心的思路是：从小到大考虑每种数，初始全部为
+，从后往前看能改就改； - 注意到这样每种数会形成一个分界线，这个分界线一定是递增的，所以我们可以离线询问，然后每次枚举一种数，二分其分界线，因为分界线递增，所以实际上我们只需要记录上一个分界线前面是哪些数，分界线后面的一定全部选择了
-，所以实际上我们知道每种数的实际取值。可以直接二分了。
P14392 [JOISC 2017] 都市 / City【通信题暂无法评测】
我们可以记录下“dfn” 和 “sz” 来判定。dfn 是一定要记录的，但是这样 sz
就记录不下来了。我们考虑加入一些虚拟节点来使得 sz
的种类不会太多，实际上只需要 512 种虚拟节点，增长率为 0.023
即可。
考虑一点朴素的想法：把 \(\text{dfn}\) 跟 \(\text{size}\) 都传进去，但大概需要 36 位。感性上考虑 \(\text{dfn}\) 更重要，我们尝试把 \(\text{size}\) 压到 9 位。
考虑做一个这样的事情：构造序列 \(f_0 \sim f_{511}\) 去拟合 \(\text{size}_x\)，每次找到最小的 \(i\) 使得 \(f_i \geq \text{size}_x\) 并加入 \(f_i - \text{size}_x\) 个虚拟节点，再在此基础上构造 \(\text{dfn}\) 序列。
考虑构造 \(f_i = \lfloor (1 + w)^i \rfloor\)，其中 \(w\) 是一个足够小的正实数。限制有 \((1 + w)^{511} \geq 2^{19}\) 以及 \(\sum (f_i - \text{size}_x) \leq 2^{19} - n\)。分析一下后一个限制：由于 \(f_i \leq (1 + w)\text{size}_x\) 故左侧相当于 \(w \sum \text{size}_x \leq 19wn\)，故至多有 \((1 + 19w)n\) 个点。
然后可以注意到 \(f_i\) 不需要严格地取 \(\lfloor (1 + w)^i \rfloor\)，可以这样： \[f_i = \max(1, w \times f_{i-1}) + f_{i-1}\] 这样就能避免前期增长过慢的问题。然后二分找到一个满足条件的 \(w\) 即可。一个满足条件的值是 \(w = 0.022\)。
0109
P8376 [APIO2022] 排列
发现我们可以实现乘法（一个放在左下，另一个放在右上，得到 \(xy\) 的贡献），或者加法（一个放在左上，另一个右下，得到 \(x+y-1\) 的贡献）。直接朴素二进制分解是可以拿到 \(91\) 分的。
考虑我们不一定每次只弄 \(2\)。我们可以是任意质数啊。我们用任意质数的方法 dp 跑出 \(\le 200000\) 的所有答案的最优解，然后每次对于一个 \(k\)，从 \(200000\) 枚举到 \(2\)，判断是否能整除，若能直接用乘法，否则就普通的减一除二暴力即可。
P8491 [IOI 2022] 囚徒挑战
我们可以记录当前看到的位数以及最高位是什么，这里我在比赛时陷入了思维固区，以为必须是在 \(A\) 看完，\(B\) 检查，再让 \(A\) 看。实际上可以 \(A\) 看完，\(B\) 检查完再把 \(B\) 也写上去，然后 \(A\) 检查完再写新的 \(A\) 上去……可以优化很多。
然后我们每次可以在下面全是 \(0\) 或 \(N-1\) 的时候直接返回，那么状态转移就是 \(f_0=2\)（注意有 \(0\) 节点哦），然后 \(f_i=\max f_{i-j}j+2\)。发现 \(f_20>5000\)，刚好够了，可以用了。
详见：https://www.luogu.com.cn/article/05q47uir
P5473 [NOI2019] I 君的探险【交互、随机化】
考虑图是一颗树，且每个点的父亲编号小于它的编号（测试点 10、11）怎么做。
容易想到二分，每次我们对于一个点 \(x\)，二分它的父亲的范围 \([l,r]\)，然后将 \([l,r]\) 都操作一遍，如果 \(x\) 变色了，就说明它的父亲就在 \([l,r]\) 内。
非常可惜的是，这题不允许区间操作。但是我们可以使用整体二分，每次做一个 \(f(l, r, p)\) 表示编号大于 \(r\) 而父亲范围在 \([l,r]\) 的点的集合是 \(p\)，每次转移则将 \([l,mid]\) 的点全部反转，然后将 \((mid,r]\) 中被反转的点加入集合 \(pl\)。将 \(p\) 中被反转的点加入 \(pl\)，没被反转的点加入 \(pr\)，递归执行 \(f(l,mid,pl)\) 和 \(f(mid+1,r,pr)\) 即可。
void solve(int l, int r, vector<int> p) {
if (l == r) {
for (int i : p) {
report(l, i);
num++;
}
return ;
}
int mid = (l + r) >> 1;
vector<int> pl, pr;
for (int i = l; i <= mid; i++) {
modify(i);
}
for (int i = mid + 1; i <= r; i++) {
if (query(i)) pl.push_back(i);
}
for (int i : p) {
if (query(i)) pl.push_back(i);
else pr.push_back(i);
}
for (int i = l; i <= mid; i++) {
modify(i);
}
solve(l, mid, pl);
solve(mid + 1, r, pr);
}考虑怎么进阶到正解。一种思路是直接套用到无限制的图上，但是我们会遇到一个小问题：如果一个点前面有偶数条边连向它，那么这个点不会产生任何的连边。
不妨考虑随机化，我们每次打乱我们考虑的排列，这样原本有偶数条边连向它的点可能就会变成只有奇数条边连向它。每次分治完后，将已经确定的边删除（这可以通过之后每次
modify 操作时先将已经确定的临点反转实现），再通过
check
操作将已经记录完的点踢出排列，循环上面的操作，就可以通过了。
注意需要特判第一个子任务，这个子任务可以写暴力。
#include "explore.h"
#include <bits/stdc++.h>
using namespace std;
namespace Sub1 {
bool s[510];
vector<int> g[510];
void explore(int N, int M) {
for (int u = 0; u < N - 1; u++) {
modify(u);
s[u] ^= 1;
for (int v : g[u]) {
s[v] ^= 1;
}
for (int v = u + 1; v < N; v++) {
if (query(v) ^ s[v]) {
s[v] ^= 1;
report(u, v);
g[u].push_back(v);
g[v].push_back(u);
}
}
}
}
}
namespace Sub2 {
vector<int> g[200010];
int s[200010], num;
void solve(int l, int r, vector<int> p, const vector<int> &V) {
if (l == r) {
for (int i : p) {
g[V[l]].push_back(i);
g[i].push_back(V[l]);
report(V[l], i);
num++;
}
return ;
}
int mid = (l + r) >> 1;
vector<int> pl, pr;
for (int i = l; i <= mid; i++) {
modify(V[i]);
s[V[i]] ^= 1;
for (int j : g[V[i]]) s[j] ^= 1;
}
for (int i = mid + 1; i <= r; i++) {
if (query(V[i]) ^ s[V[i]]) pl.push_back(V[i]);
}
for (int i : p) {
if (query(i) ^ s[i]) pl.push_back(i);
else pr.push_back(i);
}
for (int i = l; i <= mid; i++) {
modify(V[i]);
s[V[i]] ^= 1;
for (int j : g[V[i]]) s[j] ^= 1;
}
solve(l, mid, pl, V);
solve(mid + 1, r, pr, V);
}
void explore(int N, int M) {
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
vector<int> V;
for (int i = 0; i < N; i++) V.push_back(i);
while (1) {
solve(0, (int)V.size() - 1, {}, V);
if (num == M) break;
vector<int> nw;
for (int i : V) if (!check(i)) nw.push_back(i);
V = nw;
shuffle(V.begin(), V.end(), rnd);
}
}
}
void explore(int N, int M) {
if (N <= 500) Sub1::explore(N, M);
else Sub2::explore(N, M);
}这个算法为什么是正确的呢？我们发现对于一个度数为 \(k\) 的点，有 \(\frac{\lfloor k/2\rfloor}{k}\) 的概率前面有奇数条边连向它，当 \(k=3\) 时，上式取到最小值 \(\frac{1}{3}\)，也就是每次考虑的集合大小为 \(m\) 的时候，最坏情况下期望会使得集合大小减少 \(m/3\)（这里的最坏情况指的是给定的图的最坏情况，所以和期望并不矛盾），容易得到一个不严谨的式子：\(T(m)=T(m-m/3)+O(m\log m)\)，分析之后发现是 \(O(m\log m)\)。
0110
CF1540D Inverse Inversions【分块、max+卷积】
容易推出一个 \(O(\sum (n-x))\) 的做法，就是每次你发现我们考虑在 \(x\) 位置插入一个数之后，后面每个数，如果 \(a_i\le x\)，那么 \(x\gets x + 1\)，最后面答案就是 \(O(n-x)\)。
这个过程可以用分块优化，我们考虑一个块怎么快速求出以 \(x\) 进入后会变成什么。我们发现我们只需要维护以 \(x\) 进入后会加上 \(i\) 就行了。发现加上的值域只有 \(B\)，而输入的值域却有 \(n\)，果断换维。我们只维护 \(f_i\) 表示要加上 \(i\)，至少要 \(x\ge f_i\)。此时只有 \(B\) 个数要维护了。
考虑怎么计算一个段的 \(f\) 以及单点修改。考虑线段树。我们开个线段树算这个，那么怎么合并呢？我们可以发现，假设最终加了 \(k\)，其中 \(i\) 是在左边加的，\(j\) 是右边加的，\(i+j=k\)。那么 \(x\ge fl_i\)，然后变成 \(x+i\)，故 \(x+i\ge fr_j\)，也就是 \(x=\max(fl_i,fr_j-i)\)。所以 \(f_k=\min_{i+j=k} \max(fl_i,fr_j-i)\)。发现当 \(k\) 由 \((i,j)\) 转移过来时，\(k+1\) 一定由 \((i+1,j)\) 转移过来或者 \((i,j+1)\) 转移过来。所以可以 \(O(B)\) 合并。
建树就是 \(O(nB)\) 的，然后每次单点修改是 \(O(B)\) 的（真的学到了，可以用这种线段树来维护函数做到单点修改复杂度很小），查询直接二分根节点的值就好了。
平衡之后就是 \(O(n\sqrt{n\log n})\) 的。
P5284 [十二省联考 2019] 字符串问题【SAM、Easy】
https://www.cnblogs.com/bztMinamoto/p/10684233.html
最开始的思路就是将串反过来建 SAM，然后按照 parent 树连边跑拓扑求最长路即可。
但是但是，一个点可能是由多个串的，如果 \(a_i\) 和 \(b_j\) 在同一个节点上，且 \(|b_j| > |a_i|\)，此时它们就会连一个自环！但实际上 \(b_j\) 不是 \(a_i\) 的前缀！
所以我们对于每个节点，把所有串排个序，然后每个 \(B\) 串连向下一个长度的 \(B\) 串，以及这两个长度之间的所有 \(A\) 串，跑最长路即可。
P5285 [十二省联考 2019] 骗分过样例【数论】
要和我签订契约，成为出题人的 npy 吗？
有用的部分无非就是善用 factor 命令以及 miller rabin
了，注意求很大的数的莫比乌斯函数时，可以这么做：
- 先用 \(\le 10^6\) 的数把区间内的数能除就除掉。
- 此时区间内的数，要么是 \(1\)，要么是一个大质数（定义为 \(>10^6\) 的质数），要么是一个大质数的平方，要么是两个不同的大质数。
- 单独一个大质数可以用 miller rabin 判，一个大质数的平方可以 sqrt check 一下，否则就是两个不同的大质数了。
0111
D - Two Rooms【Ad-Hoc、爬山算法】
确实没想到啊。
假设当前所有人已经被分配到了房间 \(X\) 或房间 \(Y\)。总分定义为： \[ f = \sum_{i,j \in X} A_{i,j} + \sum_{i,j \in Y} A_{i,j} \] 假设人 \(i\) 现在处于 Bad State，即：
\[ \sum_{j \in \text{同房间}} A_{i,j} < \sum_{j \in \text{异房间}} A_{i,j} \]
如果我们将 \(i\) 从房间 \(X\) 移动到房间 \(Y\)，总分 \(f\) 会发生以下改变：
\[ \Delta f = 2 \times \left( \sum_{j \in Y} A_{i,j} - \sum_{j \in X, j \neq i} A_{i,j} \right) \]
显然这个值非负（因为发生调整时，人 \(i\) 总是处于 Bad State）。
同时，我们也知道，当某个人处于 Bad State 时，总有一种方法将总分增加。
所以，当总分最大时，所有人都处于 Good State。
这种东西太好了，所以其实直接退火也能过，这是因为调整代价一定是好的。
0112
P5781 [IOI 2019] 矩形区域【rect-trick】
前置阅读：Genius_Star 的题解。
定义连续段表示连续的 \([x,y]\)。
定义合法连续段表示一个连续段，并且「连续段最左端的右侧第一个比他大的数是连续段最右端」或「连续段最右端的左侧第一个比他大的数是连续段最左端」。
在我们枚举了右边界 \(r\) 和左边界 \(l\) 之后，我们需要求出有多少个 \(S_{l,r}\) 中的连续段 \([x,y]\) 使得 \(f_{x,y}\le l\)。上述题解中主要采用的方法是发现这样的连续段 \([x,y]\) 一定也是第 \(l\) 列的合法连续段（因为 \(f_{x,y}\le l\)），所以可以直接对第 \(l\) 列再跑一次单调栈求出所有合法连续段然后判断它是否真的 \(f_{x,y}\le l\)。
实际上，你可以直接先求出第 \(r\) 列的合法连续段，然后求出 \(S_{l,r}\) 的连续段，直接暴力找到所有被 \(S_{l,r}\) 的连续段包含的第 \(r\) 列的合法连续段，然后直接判定 \(f_{x,y}\le l\) 即可。这样复杂度之所以正确，是因为一个长度为 \(len\) 的连续段里，最多包含 \(O(len)\) 个合法连续段（合法连续段要么不交，要么包含），复杂度就是 \(O(\sum len)=O(nm)\) 的。
P3838 [IOI 2017] Toy Train【Ad-Hoc】
https://www.cnblogs.com/alfalfa-w/p/17309757.html
需要改变一下题目意思，然后你发现你可以排除一部分一定失败的点，如果没有一定失败的点，那么剩下的点全部都是一定成功的，否则可以递归下去继续做。
0113
P3700 [CQOI2017] 小 Q 的表格【数论、莫反、前缀和推式子 trick】
注意到题目给的东西可以直接进行变换：
\[ \frac{f(a,a+b)}{a+b}=\frac{f(a,b)}{b} \]
就是：
\[ \frac{f(a+b,a)}{a(a+b)}=\frac{f(a,b)}{ab} \]
这不是辗转相除法求 gcd 吗？我们继续看下去：
\[ \frac{f(a,b)}{ab}=\frac{f(\gcd(a,b),\gcd(a,b))}{\gcd(a,b)^2} \]
所以我们修改一个位置 \((a,b)\) 为 \(v\) 后所有 \(\gcd(x,y)=\gcd(a,b)\) 的位置都会被修改成 \(\frac{v}{ab}\cdot xy\)。
所以我们用树状数组维护一下 \(g(d)=f(d,d)\)。然后推式子，得到答案为：
\[ \sum_{d=1}^n \sum_{d|x}\sum_{d|y}\frac{g(d)xy}{d^2}[\gcd(x,y)=d] \]
简单推导：
\[ \sum_{d=1}^ng(d)\sum_{x=1}^{n/d}\sum_{y=1}^{n/d}xy[\gcd(x,y)=1] \]
莫反：
\[ \sum_{d=1}^ng(d)\sum_{x=1}^{n/d}\sum_{y=1}^{n/d}xy\sum_{p|x,p|y}\mu(p) \]
简单推导：
\[ \sum_{d=1}^ng(d)\sum_{p=1}^{n/d}\mu(p)p^2\sum_{x=1}^{n/d/p}\sum_{y=1}^{n/d/p}xy \]
设 \(S(m)\) 是 \(1+2+...+m\) 的前缀和函数，容易有：
\[ \sum_{d=1}^ng(d)\sum_{p=1}^{n/d}\mu(p)p^2S(n/d/p)^2 \]
关注后半部分，设 \(G(n)=\sum_{i=1}^{n}\mu(i)i^2S(n/i)^2\)。
使用一个不怎么众所周知的前缀和推式子的方法，就是考虑 \(G(n)-G(n-1)\) 的值，因为有 \((n/i)-(n/(i-1))=[i|n]\)，所以我们相减之后只用考虑这些项：
\[ G(n)-G(n-1)=\sum_{i|n}\mu(i)i^2(S(n/i)^2-S(n/i-1)^2) \]
考察 \(S(m)^2-S(m-1)^2\) 的值，实际上可以这么推：\((S(m)+S(m-1))(S(m)-S(m-1))=m^2\cdot m=m^3\)（\(m^2\) 可以用前缀和公式得到），所以有：
\[ G(n)-G(n-1)=\sum_{i|n}\mu(i)i^2(\frac{n}{i})^3 \]
即：
\[ G(n)-G(n-1)=n^2\sum_{i|n}\mu(i)\frac{n}{i} \]
后者可以使用狄利克雷卷积证明等于 \(\varphi(n)\)，也可以通过只看素数幂的情况来证明（证明了素数幂的情况下合法，因为卷积之后依旧是积性函数，所以得证），就是：
\[ \sum_{i|p^k}\mu(i)\frac{p^k}{i} \]
注意到只有 \(i=1\) 或 \(i=p\) 时 \(\mu\) 有值，所以就是：
\[ p^k-p^{k-1}=\varphi(p^k) \]
得证，所以 \(G(n)-G(n-1)=n^2\varphi(n)\)。
所以 \(G(n)=\sum_{i=1}^n i^2\varphi(i)\)，得到这个之后，直接跑数论分块即可。
P9730 [CEOI 2023] Grading Server【状态压缩、放缩法】
非常喜欢这种题目。
考虑转换一下题目，首先攻击系统的这个值没有必要和 \(0\) 取 \(\max\)，因为如果是负数肯定选择不攻击。先把自己的算力变成 \(c_H-f_G\cdot S\)，相当于每次可以将 \(c_G\) 减去 \(c_H\)，或者如果 \(f_G\) 还有的话，可以让 \(f_G\) 减 \(1\)，让 \(c_H\) 加上 \(S\)。对手同理。
整理一下上面的思路，就是有一个 \(A_0=c_H-f_G\cdot S,A_1=c_G-f_H\cdot S,f_0=f_G,f_1=f_H\)，这样每次的操作只和 \(f_0,A_0\) 或 \(f_1,A_1\) 有关了。每次可以选择下面两种操作：
- \(A_{k\oplus 1}\gets A_{k\oplus 1}-A_k\)；
- \(\text{if } f_k>0,f_k\gets f_k-1,A_k\gets A_k+S\)。
直接暴力就是设状态 \((A_0,f_0,A_1,f_1)\)，转移直接调换先后手位置，输就是 \(A_k+f_k\cdot S\le 0\)，然后直接去记忆化搜索即可。
手玩一些比较简单的结论：
- 当 \(A_0\le 0\) 时，尽可能选择操作二（买血），原因是这时候攻击并不优。（买不了我就输了）
- 当 \(A_0\ge S,A_1\le S\) 时，选择操作一（攻击），原因是这时候可以直接将对手打到 \(\le 0\)，而对手这时候就算选择买血，你也可以继续把它打到 \(\le 0\)。这时候，后手就会死亡。
- 如果 \(A_1\ge S\)，选择攻击，因为选择买血的话，对手一攻击，我们的 \(f_0\) 不仅少了一次买血机会，而且 \(A_0\) 血量也变得更小了（我们只能让 \(A_0\) 加 \(S\)，但对手一攻击就前功尽弃了）。
- 如果 \(A_0\ge 0,A_1\le 0\)，那么这时候我们需要尽可能选择买血，因为这样我们就会让自己变得 \(\ge S\)，对手就算买血也没有我们大（情况 3 直接把它打回原形），而且还攻击不了一点。如果能买血，那么后手就会死亡。
好像已经把很多情况覆盖完了？事实上加上这些剪枝，我们的 \(A_0\in[0,S],A_1\in[0,S]\)。
上面这些剪枝可以直接模拟（加一些小技巧），我们手模几个情况就好了：
先只考虑 \(A_0,A_1\) 是正数的情况，那么 \(A_0\ge S,A_1\le S\) 容易由情况二得到直接结束，当 \(A_0\le S,A_1\ge S\) 时，如果攻击完后 \(A_1'\ge S\)，那么直接结束（情况二），否则进入两个都是 \([0,S]\)。两个都 \(\ge S\) 时，最多只能坚持 \(\log V\) 轮。\(A_0\le 0,0\le A_1\le S\)，选择买血，如果还没能够回来，对方如果能买血就直接秒杀，否则我就会把血尽可能买到 \(\ge 0\)（每次相当于加上 \(S-A_1\)，因为对方一定会攻击）。如果是对方 \(\le 0\)，也是同理的，能买就买，买不了就攻击，交换之后变成上面的状态。两边都 \(\le 0\) 就是两边比谁先 \(\ge 0\)。
同时，我们注意到当 \(A_k+f_k\cdot S\le \max c(记作 V)\)，同时 \(A_k\ge 0\)，这时候可以得到 \(f_k\le V/S\)，所以我们发现状态数实际上是 \(O(S^2(\frac{V}{S})^2)=O(V^2)\)。
注意到我们的记忆化搜索存的是 \(0/1\)——先手赢或者输，非常不划算。考虑这么一件事情：当 \(f_0,A_1,f_1\) 相等时，\(A_0\) 越大先手越可能获胜（具有单调性），所以我们可以记录最小能使得先手胜的 \(A_0\)，然后就可以少掉一个状态。那么怎么转移呢？我们注意到我们可以二分这个值，然后直接判定一下 \(A_0\) 能不能赢，能赢就往下二分之类的云云。
现在这些能拿到 45 分。考虑做一些展开。
接下来我们需要利用性质，发现我们的值域都是 \([0,S]\)，这意味着，一旦我们回一次血，那么对手必须进攻（因为我们回血之后是 \(A\ge S\)，对手必须进攻）。
所以相当于我们每次是提升了 \(S-A_1\)，决策方不变。
设 \(\Delta_0=S-A_1,\Delta_1=S-A_0\)。
那么就是 \((A_0,f_0,A_1,f_1)\to (A_0+\Delta_0,f_0-1,A_1,f_1)\)。
注意到如果我们一直回血直到用完，之后攻击力如果比 \(S\) 还大，那么就可以获胜。
也就是 \(A_0+\Delta_0f_0\le S\)，否则先手获胜。
如果先手选择进攻，那么后手 \(A_1-A_0+\Delta_1f_1\le S\)，否则后手赢了。
这样又可以剪掉一些情况。
不要一直回血了，我们考虑夹杂一次进攻。
假设我们的战略目标为：先回血 \(x\) 次，然后攻击一次将决策权交给对手，然后对手回血完攻击之后我们把回血机会全部用完，最后直接放一次攻击消灭对手——假设我们目标就是这样。
对手如果知道了我们这个目标，肯定会尽可能在它的回合将回血机会用完（如果他就算把回血机会用完了，到了我的回合也能够把它打趴，那么我一定赢！）
推一推式子吧： \[ A_0'=A_0+x\Delta_0 \] 这里带撇表示新的。
那么显然有： \[ A_1'=A_1-A_0'+f_1(S-A_0') \] 同时，\(A_1-A_0+\Delta_1f_1\le S\)，否则我们只能回血。
因此： \[ \begin{aligned} A_1'&=A_1-A_0-x\Delta_0+f_1(S-A_0-x\Delta_0)\\ &=A_1-A_0-(f_1+1)x\Delta_0+f_1\Delta_1\\ &\le S-(f_1+1)x\Delta_0 \end{aligned} \] 此时 \(\Delta_0'\ge (f_1+1)\Delta_0x\)。
我们将 \(\Delta_0\) 增加了一个量级，但是被后手攻击了一次（不妨认为这个攻击攻击了 \(S\) 格血，即放成 \(S\)）
我们再防守 \(f_0-x\) 次，这时候 \(A_0''\) 就变成了 \(A_0''=A_0+x\Delta_0-S+(f_0-x)(f_1+1)\Delta_0x\)，缩成 \(-S+(f_0-x)(f_1+1)\Delta_0x\)，即 \((f_0-x)(f_1+1)\Delta_0x\ge 2S\) 时先手直接获胜。
二次函数最大值，不妨令 \(x=\frac{f_0}{2}\)，那么： \[ \frac{1}{4}(f_1+1)\Delta_0f_0^2\le 2S\\ (f_1+1)\Delta_0f_0^2\le 8S \] 也就是： \[ (f_1+1)(S-A_1)f_0^2\le 8S \] 因此，\((f_0,f_1,A_1)\) 的个数为 \(\sum\dfrac S{i^2}\ln S\) 的，利用 \(\sum\frac{1}{i^2}=\frac{\pi^2}{6}\) 可以证明这个式子是 \(\mathcal O(S\log S)\) 的。
注意需要特判 \(f_0=0\) 的情况，这种情况下方案数会爆（因为乘积是 \(0\)），处理方法很简单，直接进攻（甚至不需要计算，直接进入到 \((A_1-A_0,f_1,A_0,f_0)\) 即可）
0114
vp https://contest.ucup.ac/contest/1472。
L. 铁路环游【非常规思维、并查集】
一直想的是从代价函数的凸性上入手，结果正解和这个一点关系没有，果然还是被限制了思维。
考虑普通的 dp：设 \(f_{i,j}\) 表示考虑前 \(i\) 个轨道，连通了其中的 \(j\) 个，然后 \(i-1\) 连了 \(i\)。\(g_{i,j}\) 表示前面一样，但是 \(i-1\) 没有连到 \(i\)。
注意，这里将两个数组分开设，有利于优化 dp 的转移，不然可能会增加难度。
有转移：
\[ f_{i,j}=\max(f_{i',j'}+w(i',i))(i'-j'=i-j)\\ g_{i,j}=\max(g_{i-1,j},f_{i-1,j}) \]
注意这里 \(g\to f\) 的转移中 \(i-j\) 的值都是一样的，也就是说它们的转移是独立的。
所以我们维护 \(n\) 个数据结构，分别表示 \(d=i-j=0,1,\cdots,n-1\) 的最大的 \(d\) 值，每次我们扫描 \(i\)，然后将 \(r=i\) 的奖励的前缀 \(l\) 在数据结构中都加上 \(v\)，然后取出最大值，更新新的 \(g\)，把 \(g\) 插入数据结构末尾即可。
可以先扫描 \(d\) 再扫描 \(i\)，这样只需要同时维护一个数据结构，减小空间。
数据结构显然可以用线段树，但这很慢，因为每次都是前缀加正数，那么如果后一个数被前一个数偏序了，那么不需要记录后一个数，用并查集把他们合并起来，记录每个并查集到下一个并查集的差即可维护。
P5281 [ZJOI2019] Minimax搜索
参考：https://www.luogu.com.cn/article/kv8bsyq8。
我们先求出每个节点的权值，揪出贡献给根节点的那条转移链。要使得根节点的权值改变，我们需要修改某些值。
例如，转移链上的某个点 \(u\)，它的权值为 \(x\)，深度为奇数（取 \(\max\)），则它的儿子只需要有一个 \(>x\) 即可，方案就是它的每个儿子的方案的最小值。
而转移下去之后，例如儿子 \(v\)，它要大于 \(x\)，但是它这一层深度为偶数，即取 \(\min\)，则它的每个儿子都要 \(>x\)，方案就是它的每个儿子的方案的最大值。
直接跑线段树合并就可以维护了。
P3785 [SDOI2017] 文本校正【字符串、KMP、exKMP、马拉车、回文trick、AdHoc】
题目大意：给定两个长度为 \(n\) 的字符串 \(S,T\)，你需要判定 \(T\) 能否通过以下方式构造出来：
- 将 \(S\) 划分为三个非空连续段；
- 将这个三个非空连续段随意排列组合。
判断是否可以，如果能，给出方案。
\(n\le 10^6\)。
前置知识：在 KMP 算法中，模式串的每个前缀对应一个状态，其失配指针
\(\pi\)（也称 nxt 或
fail）定义了状态之间的后缀链接。由这些后缀链接构成的树结构称为
KMP 自动机的后缀链接树（fail 树），其中状态 \(i\) 的父节点为 \(\pi(i)\)。
设段编号为 \(1,2,3\)，将这三段的 \(3!=6\) 种关系分类讨论一下。
\((1,2,3)\)
与原串一样，直接判断是否相同即可。
\((2,3,1)\)、\((3,1,2)\)
是原串的循环同构，可以倍长后跑 KMP。注意题目要求三段都是非空的。
\((1,3,2)\)、\((2,1,3)\)
以 \(2,1,3\) 为例，\(S\) 和 \(T\) 具有相同的后缀，枚举这个后缀 \((p,n]\)，那么 \(T[1,p]\) 由 \(2\) 和 \(1\) 两个部分组成，求出所有是 \(T[1,p]\) 的后缀又是 \(S[1,p]\) 的前缀的字符串（将 \(T[1,p]\) 在 \(S\) 建出的自动机上跑了之后，得到的状态在后缀链接树上的所有祖先），它们就是可能成为 \(1\) 部分的字符串。设其中一个字符串是 \(S[1,k]\)，再判断 \(S[k+1,p]\) 与 \(T\) 的 lcp 是否超过 \(p-k\) 即可（使用 exkmp 计算出 \(z_{k+1}\) 即可判定）。取出 \(\max\{k+z_{k+1}\}\) 的祖先状态，这个可以在后缀链接树上预处理得到。
\((3,2,1)\)
将 \(T\) 前后翻转为 \(T'\)，就是判定 \(S\) 是否可以分成三段，使得每段和 \(T'\) 对应的段刚好前后顺序相反。考虑构造这么一个字符串：\(S_1,T'_1,S_2,T'_2,\cdots,S_n,T'_n\)，那么我们只需要判定是否能够将这个新的字符串划分为三段，使得每段都是回文串即可。存在一个引理：如果 \(s\) 是一个双回文串（对于一个字符串 \(s=ab\)，若 \(a,b\) 都是回文串，则称 \(s\) 为双回文串），则存在一种拆分方法 \(s=ab\)，使得 \(a\) 是 \(s\) 的最长前缀回文串，或者 \(b\) 是 \(s\) 的最长回文后缀。利用这个引理，算出以每个点为开头（结尾）的最长回文串长度即可判定。
引理的证明①如下。考虑引入一个新的引理：若 \(s=x_1x_2=y_1y_2=z_1z_2\)，且 \(|x_1|<|y_1|<|z_1|\)，\(x_2,y_1,y_2,z_1\) 是回文串，则 \(x_1\) 与 \(z_2\) 都是回文串。
设 \(z_1=y_1v\)。
\(v\) 是 \(y_2\) 的前缀，因为 \(y_2\) 是回文串，那么也是 \(y_2\) 的后缀。可以得到也是 \(x_2\) 的后缀，因为 \(x_2\) 是回文串，则 \(v\) 是 \(x_2\) 的前缀。
即 \(x_1v\) 是 \(z_1\) 的前缀。
因为 \(z_1\) 是回文串，所以：
\[ z_1=z_1^R=v^Ry_1^R \]
又因为 \(y_1\) 也是回文串，可以得到：
\[ y_1v=v^Ry_1 \]
所以容易有 \(z_1[i]=z_1[i+|v|]\)，即 \(z_1\) 存在一个长度为 \(|v|\) 的周期，换句话说，\(z_1\) 是 \((v^R)^{\infty}\) 的前缀，即 \(x_1\) 是 \((v^R)^\infty\) 的前缀。
同时我们也可以得到 \(x_1v\) 也存在一个长度为 \(|v|\) 的周期，所以 \(x_1\) 是 \(v^\infty\) 的后缀。
所以 \(x_1\) 是回文串。
如果字符串 \(s\) 存在至少三种划分方式，那么只需要最长前缀回文串即可判定，否则两种（一种）划分方式都会被我们考虑，得证。
0118
P6305 [eJOI 2018] 循环排序【欧拉回路】
考虑排列怎么做，先普通建出置换环，发现你可以用 \(x\) 的代价把某些置换环合并，现在问题变成了怎么把非排列变成排列。
我们需要定一个顺序，普通定顺序是哈密顿回路，考虑转成值域建图变成欧拉回路。
那么发现一个连通块就是一个欧拉回路，所以欧拉回路建图一定最优。
P9316 [EGOI 2021] Double Move / 二选一游戏【二选一trick】
类似Angle Beats 2.0的套路，我们发现建图之后的方案数由每个连通块的方案数相乘，一个连通块如果是树，方案就是点数（随意定根），如果是基环树，就是 2（环方向定义），否则是 0。
我们发现：
- 树+树=树
- 树+基环树=基环树
- 树+边=基环树
所以直接发现去记录基环树个数以及每个树的大小，然后爆搜即可。
0206
P9722 [EC Final 2022] Rectangle【线段树】
先令 \(x_2\gets x_2+1,y_2\gets y_2+1\)，转化为左闭右开区间。
分讨三横与两横一竖的情况，三横显然直接 dp 即可，考虑两横一竖。枚举竖线，相当于丢掉了一些已经满足条件的矩形，剩下的矩形就可以压成一个区间，我们需要计算有多少种 \((L,R)\) 满足 \(L<\min r_i,R\ge \max l_i\) 且不存在 \(L<l_i<r_i<R\)。考虑若固定了一个 \(L\)，则 \(R\) 的取值范围就是 \([\max l_i,\min_{L<l_i}r_i)\)，关键在于如何维护 \(\min_{L<l_i}r_i\)。考虑线段树分治加入这些修改，由于是前缀取 \(\min\) 所以可以转化成区间覆盖，直接做是 \(O(n\log^2 n)\)。
考虑怎么做单 \(\log\)。考虑换维扫描线，数据结构维护时间维的信息，由于是前缀改我们倒着扫，此时只需要支持前后缀取 \(\min\) 与查区间和，类似地可以直接转化成区间覆盖。当 \(\min_{L<l_i}r_i\le \max l_i\) 时还需要把该位置删掉，这个可以直接均摊维护。朴素线段树就可以完成上述事情，复杂度 \(O(n\log n)\)。
这里区间取 min 是因为，每次都是前后缀取 min，所以最后就是一个单峰函数，显然单峰函数取 min 的话，暴力做（维护区间 min max，如果 max 都比它小则退出，如果 min 比它大则区间覆盖，否则递归下去）只有 \(O(1)\) 个有用区间，所以依旧是对的
#6042. 「雅礼集训 2017 Day7」跳蚤王国的宰相【树的重心】
可以确定以下两条基本性质：
- 性质一：所有被断开的边，其中一个端点必然是原树的重心 \(p\)。即我们只断开与 \(p\) 直接相连的边。
- 性质二：所有断开后的连通分量，重新连接在目标节点 \(u\) 上是最优的。
性质二的成立是显而易见的。我们的目标是减小 \(u\) 在原树中“上方连通块”（即不包含 \(u\) 及其子树的部分）的大小，因为根据重心的性质其他子树的大小显然都是 \(\le \lfloor n/2\rfloor\)。将断开的子树重新连接到 \(u\) 节点上，可以直接从上方连通块中移除对应的节点数。由于原重心 \(p\) 的任何儿子子树大小 \(S\) 均满足 \(S \le \lfloor n/2 \rfloor\)，将这些子树挂载到 \(u\) 下作为其新的子树，不会导致 \(u\) 的任何下方子树大小超过 \(n/2\)。因此，这种重连方式在减小上方负担的同时，不会引入新的非法子树。
基于上述性质，我们只会断 \(p\) 周围的边。有两种删法：
- 只删 \(p\) 除了 \(u\) 子树外的边；
- 把 \(p\) 的一部分边删掉之后，再删 \(p\) 到 \(u\) 方向的那条距离 \(p\) 最近的边。
此时我们选择根据子树大小从大到小贪心断，直接二分即可。
为了证明只断开 \(p\) 的直接出边是最优的，我们需要对 \(p\) 的不同子树进行分类证明：
情况一：子树不包含 \(u\)
设 \(v\) 为 \(p\) 的一个儿子，且 \(u\) 不在 \(v\) 的子树中。若要从该方向消减 \(u\) 的上方重量，断开边 \((p, v)\) 优于断开 \(v\) 子树内部的任何边。因为断开 \((p, v)\) 能够一次性获得该子树最大的减重收益 \(size_v\)。任何更深层次的切割所获得的节点数必然小于 \(size_v\)，在断边代价相同的情况下，选择 \(p\) 的出边效率最高。而 \(size_v\le n/2\)，所以断开后直接接到 \(u\) 上是一定合法的。
情况二：子树包含 \(u\)
设 \(v\) 为 \(p\) 的一个儿子，且 \(u\) 位于 \(v\) 的子树中。此时，断开边 \((p, v)\) 同样是减重效率最高的方案。
证明：断开边 \((p, v)\) 后，包含 \(p\) 及其所有其他子树的结构被整体移走并重连至 \(u\)。此时 \(u\) 剩下的上方连通块变为了 \(v\) 子树内部除去 \(u\) 及其子树后的剩余部分，其大小为 \(size_v - size_u\)。
由于 \(p\) 是原重心，已知 \(size_v \le \lfloor n/2 \rfloor\)，因此 \(size_v - size_u\) 必然满足 \(\le \lfloor n/2 \rfloor\)。这意味着断开路径上最靠近 \(p\) 的这条出边，仅需一次操作即可使该方向的负担直接合法。而在 \(p \to u\) 路径中间进行的任何其他切割，移走的重量都更大，直接接到 \(u\) 上不一定能够合法。
综上，所有最优的切割方案均发生在原重心 \(p\) 的邻边上。通过对 \(p\) 的儿子子树大小进行排序和前缀和预处理，经过二分可以在 \(O(n \log n)\) 的时间复杂度内解决该问题。
#6043. 「雅礼集训 2017 Day7」蛐蛐国的修墙方案【搜索】
思维不能硬化啊，搜索也要面子的诶
建出置换环，发现大小为 \(2\) 的偶环可以直接判断，而大小 \(\ge 4\) 的偶环不会超过 \(25\) 个，且只有两种选择，可以 \(2^{25}\) 爆搜。
Dice Stats【概率、期望】
\(E[ans]\) 是容易用 dp 求的，然后方差怎么算呢？
有 \(P(A\land B)=P(A)*P(B|A)\)，这个 \(|\) 意思是条件，就是在 \(A\) 成立下 \(B\) 成立的概率是多少。
考虑怎么求 \(Var[ans]\) ，首先 \(Var[ans] = E[(ans - E[ans])^2]\) ，为了方便表达设 \(e = E[x]\) 。
先根据期望的线性化简一下式子：
\[ \begin{array}{l} V a r [ a n s ] = E \left[ (a n s - e) ^ {2} \right] (3) \\ = E \left[ a n s ^ {2} - 2 e a n s + e ^ {2} \right] (4) \\ = E [ a n s ^ {2} ] - 2 e E [ a n s ] + e ^ {2} (5) \\ = E [ a n s ^ {2} ] - e ^ {2} (6) \\ \end{array} \]
\(e^2\) 很好求，对于 \(E[ans^2]\) ，可以先把 \(ans = X_1 + X_2 \dots X_n\) 代入
\[ \begin{array}{l} E [ a n s ^ {2} ] = E \left[ \left(\sum_ {k = 1} ^ {n} X _ {k}\right) ^ {2} \right] (7) \\ = E \left[ \sum_ {k = 1} ^ {n} \sum_ {l = 1} ^ {n} X _ {k} X _ {l} \right] (8) \\ = \sum_ {k = 1} ^ {n} \sum_ {l = 1} ^ {n} E \left[ X _ {k} X _ {l} \right] (9) \\ \end{array} \]
但是由于 \(X_{k}\) 和 \(X_{l}\) 并不独立。所以不能拆开。所以只能硬算
\[ E \left[ X _ {k} X _ {l} \right] = \sum_ {i = 1} ^ {6} \sum_ {j = 1} ^ {6} P \left[ X _ {k} = i \wedge X _ {l} = j \right] * i * j \tag {10} \]
现在考虑 \(P[X_{k} = i\wedge X_{l} = j]\) 怎么算，先转化一下形式：
\[ P \left[ X _ {k} = i \wedge X _ {l} = j \right] = P \left[ X _ {k} = i \right] * P \left[ X _ {l} = j \mid X _ {k} = i \right] \tag {11} \]
但是 \(k\) 和 \(l\) 的取值太多，肯定不可以直接算。考虑继续化简 \(E[ans^2]\)
\[ E [ a n s ^ {2} ] = \sum_ {k = 1} ^ {n} E \left[ X _ {k} ^ {2} \right] + 2 \sum_ {k = l} ^ {n} \sum_ {l = k + 1} ^ {n} E \left[ X _ {k} X _ {l} \right] \tag {13} \]
\(E[X_k^2]\) 很好求，继续对后面的式子进行化简：
\[ \begin{array}{l} \sum_ {k = l} ^ {n} \sum_ {l = k + 1} ^ {n} E \left[ X _ {k} X _ {l} \right] = \sum_ {k = 1} ^ {n} \sum_ {l = k + 1} ^ {n} \left(\sum_ {i = 1} ^ {6} \sum_ {j = 1} ^ {6} P \left[ X _ {k} = i \wedge X _ {l} = j \right] * i * j\right) (14) \\ = \sum_ {k = 1} ^ {n} \sum_ {l = k + 1} ^ {n} \sum_ {i = 1} ^ {6} \sum_ {j = 1} ^ {6} P \left[ X _ {k} = i \right] * P \left[ X _ {l} = j \mid X _ {k} = i \right] * i * j (15) \\ = \sum_ {i = 1} ^ {6} i \sum_ {j = 1} ^ {6} j \sum_ {k = 1} ^ {n} P \left[ X _ {k} = i \right] \sum_ {l = k + 1} ^ {n} P \left[ X _ {l} = j \mid X _ {k} = i \right] (16) \\ \end{array} \]
对于显然 \(P[X_{l} = j|X_{k} = i]\) 可以这样转化形式：
\[ P \left[ X _ {l} = j \mid X _ {k} = i \right] = P \left[ X _ {l - 1} = j \mid X _ {k - 1} = i \right] \tag {17} \]
重复这个过程：
\[ P \left[ X _ {l} = j \mid X _ {k} = i \right] = P \left[ X _ {l - k + 1} = j \mid X _ {1} = i \right] \tag {18} \]
因此我们可以继续化简原来的式子：
\[ \sum_ {k = l} ^ {n} \sum_ {l = k + 1} ^ {n} E \left[ X _ {k} X _ {l} \right] = \sum_ {i = 1} ^ {6} i \sum_ {j = 1} ^ {6} j \sum_ {k = 1} ^ {n} P \left[ X _ {k} = i \right] \sum_ {l = k + 1} ^ {n} P \left[ X _ {l} = j \mid X _ {k} = i \right] (19) \\ = \sum_ {i = 1} ^ {6} i \sum_ {j = 1} ^ {6} j \sum_ {k = 1} ^ {n} P \left[ X _ {k} = i \right] \sum_ {l = 1} ^ {n - k} P \left[ X _ {l + 1} = j \mid X _ {1} = i \right] (20) \\ \]
定义 \(F(i,j,k) = \sum_{l = 1}^{k - 1}P[X_{l + 1} = j|X_1 = i]\) ，由于 \(F\) 状态数只有 \(O(36n)\) 个，所以可以直接用下面的式子预处理：
\[ F (i, j, k) = F (i, j, k - 1) + P \left[ X _ {k} = j \mid X _ {1} = i \right] \tag {21} \]
最后就可以在 \(O(n)\) 的时间内通过下面的式子得出 \(\sum_{k = l}^{n}\sum_{l = k + 1}^{n}E[X_kX_l]\)
\[ \sum_ {k = l} ^ {n} \sum_ {l = k + 1} ^ {n} E \left[ X _ {k} X _ {l} \right] = \sum_ {i = 1} ^ {6} i \sum_ {j = 1} ^ {6} j \sum_ {k = 1} ^ {n} P \left[ X _ {k} = i \right] F (i, j, n - k + 1) \tag {22} \]
但是这样做由于转化成了 \(Var[ans] = E[ans^2] + e^2\) 分别计算，可能精度会有问题
考虑原式：
\[ \begin{align} Var &= E[(ans - e)^2] \tag{1} \\ &= E[ans^2] - e^2 \tag{2} \end{align} \]
由于\(E[ans^2] - e^2\)精度误差较大，所以考虑直接求\(E[(ans - e)^2]\)。由于\(e\)是已知的，所以可以对每个面的贡献都减去\(\frac{e}{n}\)，最后求和后就是\(ans - e\)，就是我们要求的式子。所以直接套用\(E[x^2]\)的做法即可。
0209
C - Divide into 4 Teams【生成函数】
首先列出生成函数，记录 \(A-B\) 和 \(C-D\)。那么一个元素就是 \(x^{P_i}+x^{-P_i}+y^{P_i}+y^{-P_i}\)。就是要求 \([x^0y^0]\prod(x^{P_i}+x^{-P_i}+y^{P_i}+y^{-P_i})\)。
此时我们进行因式分解：
\[ x^{P_i}+x^{-P_i}+y^{P_i}+y^{-P_i}=(x^{P_i}+y^{P_i})(1+x^{-P_i}y^{-P_i}) \]
设 \(S=\sum P_i\)。
前者是一个背包，当你选出了一个大小为 \(u\) 的元素分配给 \(x\)，就会产生 \(x^uy^{S-u}\) 的贡献。
后者也是一个背包，当你选出了一个大小为 \(t\) 的元素，就会产生 \(x^{-t}y^{-t}\) 的贡献。
显然有：
\[ u=t S-u=t \]
那么：
\[ u=t=S/2 \]
所以直接背包然后平方即可，注意需要减去空的情况。
F - Unpredictable Moves【网络流】
考虑怎么 check。
当出现以下情况，你是过不去的：
##（直接相连）
#.
.#（45度相连）
#
.
#（跳一格相连）
根据经典结论：如果从右上角存在一个走这种 #
的方案可以走到左下角，那么就不能到达。
反过来我们就最小割，把每个墙拆点建一个 1 的边，然后直接连边即可。
G - Kyoen【数论】
实话实说，根本不会考哈哈哈。
先学习高斯整数。注意这里之所以 \(2\) 没有贡献是因为 \(2=(1+i)(1-i)\)，这两个质数实际上可以通过最后旋转 \(90\) 度得到，会算重。
然后这道题相当于你的 \((x\bmod C,y\bmod C)=(-A\bmod C,-B\bmod C)\)。同时因为 \(p_i\le 100\)，所以直接暴力找高斯整数分解是容易的（都是质数，可以枚举 \(x,y\)，使得 \(x^2+y^2=p\)）。但是注意到 \(e_i\) 很大，不过因为 \(C^2\) 很小，所以 \(x,y\) 存在周期，可以算出周期直接做。
F2. Again Trees... (hard version)【线性基、FWT】
先用线性基把 \(b\) 弄了，然后你发现设计 dp \(f_{u,i}\) 表示子树 \(u\) 内被砍掉的部分的异或在线性基内表示为 \(i\)。
转移是容易的，就是一个异或卷积，设 \(S\) 表示子树内异或和，然后你需要把 \(\sum_{b\in B}f_{u,S\oplus b}\) 加到 \(f_{u,S}\) 上。
每次 FWT、IFWT 复杂度多个 \(k\)，所以考虑全程不 IFWT。
这个其实也挺容易，分为两个部分，单点加、查询所有 \(S\oplus b\) 的和。
单点加是可以做到 \(O(2^k)\) 单次的，很容易。
后者你发现，假设 \(S=0\) 怎么做。
就是 \(P_i=[i\in B]\)，你要求：
\[ F_i\cdot P_i \]
就是一个点积。
不过我们有一个结论，设 \(\widehat{A}\) 表示 \(A\) 的 FWT 后的结果：
\[ \sum_{j=0}^{2^k-1} \widehat{A}_j \widehat{B}_j = 2^k \sum_{i=0}^{2^k-1} A_i B_i \]
所以我们可以先把 \(P_i\) FWT 后，然后两个做点积，再除以 \(2^k\) 即可。
这个证明也容易：
第一步：把定义代入左边根据定义，\(\widehat{A}_j = \sum_{i} A_i (-1)^{i \& j}\)（这里为了简洁，\(i \& j\) 代表 \(\text{popcount}(i \text{ AND } j)\) 的奇偶性）。
我们把左边的乘积展开：
\[ \sum_{j} \left( \sum_{i_1} A_{i_1} (-1)^{i_1 \& j} \right) \times \left( \sum_{i_2} B_{i_2} (-1)^{i_2 \& j} \right) \]
利用乘法分配律（就像 \((a+b)(c+d) = ac+ad+bc+bd\) 一样），把括号全部拆开：
\[ = \sum_{j} \sum_{i_1} \sum_{i_2} A_{i_1} B_{i_2} (-1)^{i_1 \& j} (-1)^{i_2 \& j} \]
第二步：利用指数性质合并 \((-1)\)
注意到 \((-1)^x \cdot (-1)^y = (-1)^{x+y}\)。在位运算里，\(x\&j + y\&j\) 的奇偶性其实等于 \((x \oplus y) \& j\) 的奇偶性。所以公式变成：
\[ = \sum_{j} \sum_{i_1} \sum_{i_2} A_{i_1} B_{i_2} (-1)^{(i_1 \oplus i_2) \& j} \]
现在我们调整求和的顺序（把对 \(j\) 的求和提到最里面）：
\[ = \sum_{i_1} \sum_{i_2} A_{i_1} B_{i_2} \left[ \sum_{j=0}^{2^k-1} (-1)^{(i_1 \oplus i_2) \& j} \right] \]
第三步：分析那个“神奇的括号”这是整个推导最关键的地方。我们要看 \(\sum_{j=0}^{2^k-1} (-1)^{x \& j}\) 这个式子：
如果 \(x = 0\)（也就是说 \(i_1 = i_2\)）：那么 \((i_1 \oplus i_2) = 0\)。不管 \(j\) 是多少，\(0 \& j\) 永远是 \(0\)。\((-1)^0 = 1\)，所以这就是 \(2^k\) 个 \(1\) 相加。结果 = \(2^k\)。
如果 \(x \neq 0\)（也就是说 \(i_1 \neq i_2\)）：这是一个非常有意思的对称结构。如果你把所有的 \(j\) 遍历一遍，你会发现 \(x \& j\) 为偶数的情况和为奇数的情况正好各占一半。也就是有一半的 \(1\) 和一半的 \(-1\)。结果 = \(0\)。
第四步：见证奇迹的时刻
回到我们的公式：
\[ \sum_{i_1} \sum_{i_2} A_{i_1} B_{i_2} \times (\text{如果是 } i_1=i_2 \text{ 就贡献 } 2^k, \text{ 否则贡献 } 0) \]
因为只有当 \(i_1 = i_2\) 时这一项才不是 \(0\)，所以我们可以把 \(i_2\) 全部换成 \(i_1\)：
\[ = \sum_{i_1} A_{i_1} B_{i_1} \times 2^k \]
把系数 \(2^k\) 提出来，就得到了：
\[ = 2^k \sum_{i} A_i B_i \]
然后原本相当于你还要异或一个 \(S\)。相当于还要做一个卷积。这也容易。求出只有 \(S\) 的 FWT（\(O(2^k)\) 非常快），然后直接对位点积就求出来了。
0211
P6335 [COCI 2007/2008 #1] STAZA【仙人掌、圆方树 dp】
没什么好说的。
P4747 [CERC2017] Intrinsic Interval【数据结构、线段树】
不要只会 \(\max-\min=r-l\) 啊，换个思路，\((\sum_{i}[i\in S\land i+1\in S]) - (r-l)\) 也可以。前者能做但是大粪，后者小清新。
发现两个区间 \([l1,r1]\)，\([l2,r2]\) 如果相交且分别合法，那么它们的交也合法。所以我们每次扫描线右端点，用线段树区间 max 维护这个右端点对应的最大的左端点合法区间，然后扫到一个询问就加到堆里，每次取出一个左端点最大的询问，看看能不能被解决，如果能，其他解必定比它更劣，所以直接设答案，然后从堆里踢掉就行了。
本文作者：ZnPdCo
本文链接： https://znpdco.github.io/blog/2026/01/03/2026-Public-Problem-%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95/
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用