2022.10 做题笔记
djwj233
·
·
个人记录
牛的题目会用 * 标示，惊艳到我的题目会用 @ 标示。
* ARC 145 D
由于写题的时候没有写记录，所以写一下大致做法得了。
构造一个大小为 \dfrac{n}{2} 的集合 S 满足上述性质，然后用 -S-V 和 S+V+\dfrac{m}{n} 和一定的微调解决，其中 V 是一个足够大的常数。
这个 S 的构造可以用前 n 个 3 进制下每一位都是 0/1 的数，值域是 \mathcal O(n^{\log_23}) 的，可以过。
* ARC 145 E
考虑对 A 作差分去匹配 B 相当于对 B 作前缀和，所以我们可以只用对 B 做前缀和这种操作。
因此 B_i 能匹配上 A_i 当且仅当 A_i\oplus B_i 可以被 B_{1\cdots {i-1}} 的线性基表示出来，这样可以判无解。
注意到复杂度肯定是 \mathcal O(n\log w) 的，所以我们考虑从后往前，单次 \mathcal O(\log w) 匹配一个。
排除掉 A_i=B_i 的情况，最后肯定有一次操作是 K=i，所以我们要使 \bigoplus_{t=1}^iB_t=A_i。
而如果 j 是 1\cdots i-1 的线性基中的一个，那么操作 K=j+1 会导致 \bigoplus_{t=1}^iB_t 在 B_j 这维上的改变。
所以我们贪心地从 i-1 扫到 1，每次看是否需要改 B_j 位置上的值，这可以通过判定 1\cdots j-1 的线性基能否生成来判定。
朴素的实现时间复杂度是 \mathcal O(n^2\log^2 w) 的，但是注意到这个操作不会改变线性基中元素的位置，可以做到 \mathcal O(n^2\log w)。
总操作次数不大于 n\log w+n。
理一下思路，有这么几步：
- 差分转前缀和；
- 从后向前，单次 \mathcal O(\log w)；
- 将条件转化为 \bigoplus_{t=1}^iB_t=A_i；
- 依然倒序考虑对每个线性基中的元素考虑，并发掘操作后什么变了，什么不变；
- 发现我们可以通过对每个基中元素的后一个位置操作使总和异或上 B_j；
- 发现判定是否需要当前元素方法：判断 1\cdots j-1 的线性基能否生成需要的数。
用到的一个结构是线性基，一个性质是线性基表示的唯一性，也即上面的判定。
@ P8566 You are the Miserable
感觉很多 MO-style 的题还是很有意思的。
但是现在还没书读啊，有空了再专门研究一下这类题吧。
首先有一个结论就是说 k=2n-6，怎么来的？
首先你注意到这个 m\le k，而输入是 \mathcal O(m) 的，所以 k 和 n 很可能是线性关系（
再还有就是，把 n 的定义域放宽到 3 上，根据定义 k=0，由这三个点可以看出 k=2n-6？
而注意到 k=(n-3)\times 2，不难想到一次 Yes 对应一次 No 的策略。
也即，A 对每个询问当且仅当有之前询问穿过它时才回答 Yes，这样可以卡到至少 2(n-3) 次。
这个想法主要来源于多少次询问现在还没有被浪费，就是类似于势能的观点：
如果 A 回答了 Yes，那么相当于分治成了两个子问题，同时穿过这个 Yes 的所有 No 都失效了。
同时也可以引出 A 操作最优的一个必要条件：每个前缀中 0 的个数不少于 1 的个数，经过数值运算可以发现这是充分的。
B 该怎么办？观察大样例，发现 B 早期的最优操作是不停地问跨度为 2 的弦（同样适用于分治过的问题），下称其为二度弦。
手模 n=5 的情况，发现钦定 A 不首次回答 Yes 后，最优策略总是要选择问两条相邻的弦，这样可以保证问完后两次内做完。
根据上面那个观点，反证可以得到每个 Yes 最多浪费一个 No，所以 k=2n-6。
然后有一个很强大的结论：
对任意 n-3 元的弦集 S，都存在一个三角剖分 P 与 S 不交。
进一步地：
P 唯一当且仅当 S 是一些连续的二度弦。
前者的证明可以通过取不在 S 中的二度弦来构造，后者存在性可以构造一个放射状的三角剖分，而证明唯一性需要利用的一个性质：
对于凸 n(\ge 5) 边形的三角剖分，其至少含两条二度弦，且显然它们不相邻。
证明可以归纳，不再赘述。
上面的结论意味着，无论 B 问什么，A 都可以先回答 n-3 次 No。
现在我们考虑，如果 B 问的前 n-3 次中有不相邻的两段二度弦，那么 A 可以取两段中各一个定为 Yes，这样 B 至少要多浪费一次。
因此 B 最优当且仅当任意时刻，每个子问题中的 No 都是一段连续的二度弦，除非答案已经确定，即已经形成 n-3 元相邻二度弦集。
依此归纳可知，任意时刻 B 面临的问题都是一个大的子问题和一些大小为 3 的平凡子问题，对后者我们不予考虑。
这样代码就能写了，但是细节有点多。
* P8558 黑暗（Darkness）
首先，走到 (A-x,B-y,C-z) 的概率是：
\dfrac{1}{3^{x+y+z}}\binom{x+y+z}{x,y,z}
我们枚举撞墙的那一维，得到答案是：
f(A,B,C)+f(B,A,C)+f(C,A,B)
其中：
f(x,y,z)=\sum_{i=0}^y\sum_{j=0}^z\dfrac{(y+z-i-j)^k}{3^{x+1+i+j}}\binom{x+i+j}{x,i,j}
问题转换为如何单次线性地求出 g(x,y,z) 的一个点值。
考虑换元 t=i+j，得到：
g(x,y,z)=\dfrac{1}{3^{x+1}}\sum_{t=0}^{y+z}\dfrac{(y+z-t)^k}{3^t}\sum_{i=t-z}^{y}\binom{x+t}{x,i,t-i}
注意到：
\sum_{i=t-z}^{y}\binom{x+t}{x,i,t-i}=\binom{x+t}{x}\sum_{i=t-y}^z\binom{t}{i}
后面那个东西可以递推！记 g_{y,z}(t)=\sum_{i=t-y}^{z}\binom{t}{i}，得到：
g_{y,z}(t+1)=\sum_{i=t+1-y}^{z}\binom{t+1}{i}=\sum_{i=t-y+1}^{z}\binom{t}{i}+\binom{t}{i-1}=2g_{y,z}(t)-\binom{t}{z}-\binom{t}{t-y}
而 i^k(i\in \N) 可以线性筛筛出，这样就做到了线性！
启示：有固定上下界的组合和式可以考虑递推。更科学地，超几何式可以整式递推。
pjudge NOIP Rd 2 D
现在问题转化为：有 $n$ 个物品，每个体积在 $[1,4]$ 范围内，要求做 01 背包。
我场上尝试打反悔贪心，后来发现我 naive 了，如果要反悔贪心复杂得一批......
正解其实不难，考虑记 $dp_{i,j}$ 为体积 $[1,i]$ 的物品凑出 $j$ 的最小代价，这个转移（在模 $i$ 意义下）一定有决策单调性。
于是就可以 $\mathcal O(n\log n)$ 了，[代码](http://pjudge.ac/submission/53710)难写。
### \* 校内 NOIP 模拟 10.6 D
转化后的大致题意：
> 给定 $t_{0\cdots m}$，记一个数列 $a_{1\cdots m}$ 为好的，当且仅当 $\forall i\in[1,m],a_i\sube t_i$，且 $a_i$ 的不交并为 $t_0$ 的一个子集。
>
> （其中集合运算都是二进制意义下的）
>
> 记 $a_{1\cdots m}$ 的价值为 $\sum_{i=1}^m i\times a_i$，价值为 $x$ 的好数列有 $f(x)$ 个，求 $\sum_{x\ge 0}(f(x)\bmod 2)$。
>
> $1\le m\le 10,1\le t_i<2^{50}$。
有几个重要的点：
- **我们要对每个 $x$ 考虑，即 DP 状态应立足于 $x$；**
- $m$ 只有 $10$，可以考虑 NOIP2021 T2 类似的 trick：从小到大 DP，同时记录进位。
第一个点引出了一个常见的处理思路：**在最低的不同位区分开两个 $x$**。
具体地，我们发现 DP 到前 $i$ 位时，对于一个 $x$（$x<2^i-1$，就是已经确定的部分），有用的信息只有**每种进位情况对应的方案是否是奇数**。
所以我们考虑把这些信息（信息量为 $\Theta(2^m)$）压进状态里，转移几下，具体细节略去，单次复杂度 $\mathcal O(2^mm^2\log t)$。
总结一下，由于第二个点我场上已经想到，主要就是第一个点：我没有**何时区分两个不同的组合对象**的意识。
这个题的思路过程大致是这样：
- 由于题目本质上要问**有多少 $x$ 满足 $f(x)\bmod 2=1$**，所以 $x$ 才是重要的组合对象！
- 上面的分析已经告诉我们，我们要将每一位分给 $a_{1\cdots m}$ 中的一个元素，所以从二进制入手 DP。
- 由于 $x$ 大小会达到 $nt$，所以不能直接从 DP 状态中区分，考虑**在最低的不同位** *(难点 1)* 区分两个 $x$。
- 由上面的分析，状态**一定只能设为**：有多少个**总价值 $x$ 的低 $i$ 位**满足 (......) 性质。
- 注意到当前凑出来的 $x$ 的低 $i$ 位相同不一定代表全部相同，更高的位还是有用的。
- 由于 $m$ 不大，**联想到** *(难点 2)* NOIP2021 T2 的进位 trick。
- 但是由上面的分析，我们不能直接设出进位状态，因为这样会把同一个组合对象拆成好几份。
自然想到解决方案：对每个组合对象记录有哪些进位状态，然后用状压设出状态。
- 转移、实现。
发现这个思维过程中有两个较为不自然、可能需要经验的地方（上面的难点 1,2），以后碰到时需要多加注意。
---
总结一下计数 DP 的常见思路吧：
**简化：分析组合对象、确定计数方式、舍弃冗余信息、建立模型 / 设计状态、考虑转移。**
其中，“舍弃冗余信息”这一步重在**求同存异**，可以借助 DP of DP 类似思想更直观地掌控。
### \* [pjudge NOIP Rd 2 C](https://pjudge.ac/contest/1015/problem/21688)
场上一点思路也没有，可能是因为我在摆烂
首先先有一步转化：操作就是交换两个 (color, value) 的二元组，然后各自反色。
这样对于一个点，全部操作结束后颜色改变当且仅当其经过奇数条边。
部分分分成两部分，我们也两部分做：
- **连通块是二分图**
这样每个点是否被反色只与所在块有关了。
有一个显然的必要条件：每种点值对应的**左部黑点 $+$ 右部红点**相等 。
取一棵生成树简单构造可知它也是充分的。
- **连通块不是二分图**
那它肯定有个奇环，考虑任意挖一个奇环出来。
我们发现可以构造在奇环上绕一圈，来反转环上相邻两个点的颜色。
而任意时候我们都可以沿着一条路径把一个点拉过来再扯回去，不改变中间点的颜色。
用上面的方法我们可以通过把它们拉到相邻位置的方法同时反转任意两个点的颜色，所以题目可以被我们弱化为：
> 给一张完全图，每次交换两个点**而不改变它们的颜色**，然后可以同时改变两个点的颜色。
不难发现只要点值匹配，且颜色不匹配的点数是偶数即可，后面的条件其实就是两种颜色前后的奇偶性相同。
### [CF1658D2 388535 (Hard Version)](https://www.luogu.com.cn/problem/CF1658D2)
写个简单题放松一下。
但是蚌埠住了，这就是 2300 的实力吗？
考虑从高到低看 $x$ 的每一位有没有必要取，如果取这位为 $0$ 后，无论 $x$ 后面怎么取，其最大值或最小值都不符合要求，那么这位肯定要取 $1$。
否则我们证明一定存在一组取 $0$ 的解。
因为保证有解，所以如果不存在一组取 $0$ 的解，就一定有一组取 $1$ 的解，有值域区间可以推断出 $a_i$ 关于这一位是对称的，所以存在一组取 $0$ 的解。
题解里一个更牛的做法是倒着做然后分治，感觉我是傻逼。
---
这几天补一下 PKUSC，[题意](https://blog.csdn.net/Defener/article/details/117202243)，而且[这里](https://haltoj.top/p)好像可以交题。
### PKUSC 2021 Day1 A
若 $t=0$ 直接输出 $a$，否则后面的结果只与第 $t-1$ 次后每行每列的和有关。
以行为例，注意到一次变换后：
$$
R^\prime_i=\sum_{j=1}^n a_{i,j}=\sum_{j=1}^n R_i+C_j=nR_i+\sum C_j
$$
记 $S=\sum C_j=\sum R_j$ 为整个矩阵的和，变换后：
$$
S^\prime = \sum R^{\prime}_i=2nS
$$
所以其实 $R_i$ 最后的值只与最开始的 $R_i$ 和 $S$ 有关，且系数是恒定的。
矩阵快速幂计算即可。（我场上好像直接把通项推出来了......）
场上过了就不写了。
### @ PKUSC 2021 Day1 B
其实这个题还有个部分分，就是：所有的修改都是全局修改。
注意到在这个部分分的限制下，我们只需要记录当前有 $v$ 次操作。
我们用单调栈维护每个数的后一个大于它的数，这样可以建出一棵树，在这棵数上倍增就可以得到某个位置的当前值。
而如果一个点对应全部的数被它的父亲“吞并”，那么这个点就废了。
由于每个点的子树都是一段区间，所以这个时间就是 **子树大小 $+$ 与父亲的距离 $-1$**。
所以操作等价于单点加、求一条祖先链的和，这可以树状数组在 DFS 序上维护。
感觉这个做法很自然，不知道为什么我当时不会做
做了这个部分分再想想原来那个题怎么做，不难发现我们只需要维护哪些点要被删除即可。
究竟怎么维护呢？发现不会，看个题解。
发现有个重要性质：记一个结点的**非自然死亡**为**它还可以向左扩展，但是已经被完全吞并了**。
由定义可以推出，**非自然死亡只会在左端点处出现，我们只需要检查 $a_l$ 对应的值是否非自然死亡**。
其余的死亡都是走完了整个生命周期（吞并了整棵子树又被父亲吞并），也就是说现在是叶子。
叶子有什么性质呢？根本不会被访问到！**也就是说，我们上面做法中的树状数组是不必要的，删去叶子结点无需修改**。
那么怎么维护每个位置现在记录着什么数呢？
维护方法也非常别具一格：维护 $p_i$ 表示当前 $a_i=\max_{j=i}^{p_i} A_j$，其中 $A_j$ 是原始数组。
这样一次操作就是把 $p_{l+1\cdots r}$ 左平移一格，再让 $p_r\gets p_{r-1}$。
这样结合 ST 表就可以实现单点求值，而这个 $p$ 可以用 Splay 维护。
也有一种不用平衡树的方法：
>对每个位置记录 $r_i$ 表示 $i$ 向左延伸到了哪个位置。
>
>修改时线段树上二分、区间减一，询问时线段树上二分加一个 ST 表。
复杂度 $\mathcal O(n\log n)$，[代码](https://haltoj.top/record/63413a1957f3aa8d48a28737)。
---
理一下思路：
- 看到求区间单调栈和，考虑单调栈的树状结构。
- 把询问转化为**树上祖先链和**。
- 发掘修改的性质，提出**一个结点死亡的概念：不存在这个数**。
- 注意到访问都是存活结点，得出**叶子结点的死亡不需要被关心**。
- 观察非叶子结点的死亡，发现**每次修改至多在左端点带来一次非自然死亡**。（重点）
- 只需要维护每个点当前的值了，可以用 Splay。
感觉重点的那一步比较不显然，但是其实也能理解。
Day 1 C 是德州扑克，所以咕了。
### [CF1025E Colored Cubes](https://www.luogu.com.cn/problem/CF1025E)
有点难写的构造题，为了放松一下就写了。
一个做法是把所有方块整到第一行，然后按照它们终点的行列双关键字冒泡排序，平移到对应行再匹配。
但是我比较傻逼，写了个很阿拉丁的做法。
### PKUSC 2021 Day2 A
$k=0$ 是傻，不说了。
$k=1$ 枚举断了哪条边，显然分成两个连通块。
我们预处理 $h_x$ 表示 $x$ 子树内的点到 $x$ 的距离之和，$g_x$ 表示子树外的。
记 $f(T,x)$ 表示 $T$ 中的点到 $x$ 的距离之和，$S(u)=\text{subtree}(u)$，$V(T)$ 是第一问答案，设割了 $(u,v=fa_u)$，那么答案就是：
$$
\begin{aligned}
&\sum_{x\in S(u)}\sum_{y\notin S(u)} V(S(u))+V(T/S(u))+|T/S(u)|\times f(S(u), x)+|S(u)|\times f(T / S(u), y)+|S(u)|\times |T/S(u)| \\
=&(V(S(u))+V(T/S(u))+|S(u)|\times |T/S(u)|)\times |S(u)|\times |T/S(u)|+\\
&|T/S(u)|^2\sum_{x\in S(u)}f(S(u), x)+|S(u)|^2\sum_{y\notin S(u)} f(T / S(u), y)
\end{aligned}
$$
考虑计算 $V(S(u))+V(T/S(u))$，不难发现有：
$$
V(S(u))+V(T/S(u))=V(T)-|S(u)|\times|T/S(u)|-|S(u)|(g_x-|T/S(u)|)-|T/S(u)|h_x
$$
考虑计算 $\sum_{x\in S(u)}f(S(u), x)$，发现：
$$
f(S(u),x)=f(T,x)-\sum_{y\notin S(u)} dis(y,x)=f(T,x)-\sum_{y\notin S(u)} (dis(y,u)+dis(u,x))=h_x+g_x-g_u-|T/S(u)|dis(u,x)
$$
所以
$$
\sum_{x\in S(u)}h_x+g_x-g_u-|T/S(u)|dis(u,x)=\left(\sum_{x\in S(u)}h_x+g_x\right)-|S(u)|g_u-|T/S(u)|h_u
$$
同理：
$$
\sum_{y\notin S(u)} f(T / S(u), y)=\left(\sum_{y\notin S(u)} h_y+g_y\right)-|S(u)|g_u-|T/S(u)|h_u
$$
代码可以看[这里](https://www.luogu.com.cn/paste/x0k8v5w4)。
### \* PKUSC 2021 Day2 B
先想想不依赖值域的多项式做法怎么做。
考虑如果我们确定了一共会得到多少张代金券，我们肯定会在最前面得到它们。
这样就会存在一个点，在这个点之前我们只会用代金券省掉 $a_i \bmod C$ 的余数的部分，之后我们全部都用代金券。
这样就可以 $\mathcal O(nq)$ 模拟了，代码长这样：
```cpp
ll suf[N], ans, cur;
ll Query() {
suf[n + 1] = ans = cur = 0;
fr(i,n,1) suf[i] = suf[i + 1] + a[i];
fo(i,1,n) {
ll v = min(cur, c[i]);
cur -= v, ans += v;
if(cur + b[i] >= suf[i + 1]) {
ll x = (__int128_t)(cur + b[i] - suf[i + 1]) * C / (C + 1);
ans += min(x, min(cur, b[i] * C)) + suf[i + 1]; break;
}
cur += b[i];
}
return suf[1] - ans;
}
```
我们发现只有这个 `if` 分支非常复杂，但好在只会有一次进入 `if` 分治，可以暴力模拟。
剩下部分只有一个，就是每次 $v\gets \max(0, v-c_i)+b_i$，考虑和 IOI 2021 D1T1 的做法类似找到最后一个 $0$。
之后就是二分找到这个点然后模拟了，可以写成 $\mathcal O(n+q\log n)$ 的，但是因为懒写了 $\log^2$。
[代码](https://haltoj.top/record/6342a98348ed6e9865bf8e77)。
### [CF913F Strongly Connected Tournament](https://www.luogu.com.cn/problem/CF913F)
显然是一个相对 traditional 的 $\mathcal O(n^2)$ 类容斥题。
我们记 $g(y,x)$ 表示 $y$ 个点中选出 $x$ 个点，满足这 $x$ 个点和 $y-x$ 个点中的边都是 $x\to (y-x)$，共 $\binom{y}{x}$ 种选法的概率和。
计算 $h(x)$ 表示任意 $x$ 个点随机连边是一个 SCC 的概率，它们都可以 $\mathcal O(n^2)$ 计算。
记 $f(x)$ 表示 $x$ 个点对应的答案，这里我们需要枚举第一个 SCC 大小为 $y$，但是我们发现后面的东西不好算。
但是还是可以算的，不难发现后面的东西实际上就是 $x-y$ 被提前钦定了一张图，这就是 $f(x-y)-\binom{x-y}{2}$。
由于懒，写了复杂度 $\mathcal O(n^2\log P)$ 的。
### @ PKUSC 2021 Day2 C
先看看 $n=3$ 怎么做，不难发现条件等价于让三个点极差超过 $k$。
考虑容斥，转成存在一个长为 $k$ 的区间包含三个数。
事实上我们可以钦定 $x_1< x_2< x_3$（取等的概率为 $0$，可以忽略），再把概率乘 $3!$，这样条件就是 $x_3\le x_1+k$。
发现一个更方便的条件是 $x_1<x_2,x_3$，再乘 $3$，这样可以列出：
$$
ans = \int_{0}^m \dfrac{\min(k,m-x)^2}{m^3}\text{d}x=\dfrac{(m-k)k^2}{m^3}+\int_{0}^k\dfrac{x^2\text{d}x}{m^3}=\dfrac{k^2(m-k)}{m^3}+\dfrac{k^3}{3 m^3}
$$
答案就是 $1-3\times ans$，但是显然这种方法做不来 $n$ 更大的情况。
不会了，看题解。
对于这种实数问题有一个常见的处理：**把每个数分成整数部分和小数部分**！
这样，每个数的小数部分排序后就是一个 $v_1<v_2<v_3<\cdots <v_n$ 的形式，我们**就可以将任意两个数的距离与 $k$ 比较**。
这样我们有了一个有限复杂度的做法：枚举 $v_1\cdots v_n$ 中每个数的整数部分暴力判断，复杂度 $\mathcal O(m^n\text{poly}(n))$。
有一个更优的做法是状压 DP，复杂度 $\mathcal O(2^n\text{poly}(nm))$。
既然都到这一步了，而且**点与点之间除了顺序没有区别**，那为什么不用插入式 DP 呢？
我们先钦定整数部分 $\in [m]$，不难发现这个转化是正确的，这样答案就是合法序列数除以 $m^n$。
记 $dp_{x,y,c,vc,d,vd}$ 为当前有 $x$ 个点，当前要处理的整数部分是 $y$，前一个整数部分为 $c$，小数部分排行为 $vc$，倒数第二个整数部分为 $d$，小数部分排行为 $vd$，就可以转移了。
但是状态复杂度有 $\mathcal O(n^3m^3)$，无法接受。
考虑把 $y$ 这维去了，复杂度就变成 $\mathcal O(n^3m^2)$ 了，而且转移复杂度好像就是这个。
看了题解，正解有一个小优化，就是把 $d$ 那维改成 $c-d$，这样复杂度变成 $\mathcal O(n^3mk)$。
看起来没什么优化，但是注意到 $\dfrac{n-1}{2}\times k\ge m$ 时答案为 $0$，可以直接判掉。
这样 $nk=\mathcal O(m)$，总复杂度变成 $\mathcal O(n^2m^2)$。
---
这题主要的一个主要思路是：
- **实数概率问题可以考虑分开整数部分和小数部分考虑**。
一个技巧是：
- 优化 DP 时注意是否有形式：**对于有用的问题都有 $AB=\mathcal O(C)$**。
若是，可以考虑把一个 $C$ 换成 $B$ 来优化，尽管可能 $B=\Theta(C)$ 导致看上去没有优化。
### \* [CF1557E Assiut Chess](https://www.luogu.com.cn/problem/CF1557E)
是一个不错的题，我的做法是先下在角上，然后根据确定出的王现在位置的范围来确定下一步操作。
实现起来会有点困难。
### ARC 147 C
首先有个结论，记 $S=\{L_i\}\bigcup\{R_i\}$，那么最后的 $\{x_i\}\sube S$。
证明可以反证然后调整法，不再赘述。
那么我们可以想到把所有的端点排序，算每一段的贡献。
每一段的贡献至少是左边点和右边点的乘积，不难发现这是一个有限制的二次函数，可以构造得到这也是可以达到的。
题解好像是更牛的一个东西。
### \* ARC 147 D
挺好的一个题。
考虑 $n=1$ 时答案为 $1$，$n=2$ 时答案为 $m\times 2^m$，不难猜想答案为 $m^{n-1}n^m$，交一发发现过了。
证明可以考虑 $m^{n-1}$ 是什么。注意到这个序列是一个类似于格雷码的形式，所以考虑**枚举相邻两个集合之间不同的是哪个数**。
这样这个“相邻不同数序列”的个数恰好是 $m^{n-1}$，接下来我们证明对于一个确定的“相邻不同数序列”，其对应的所有序列的权值之和均为 $n^m$。
证明可以归纳，$m=0$ 时显然成立，接下来默认命题对 $m-1$ 成立。
考虑 $m$ 在哪些集合中出现过，不难发现只有两种互补的情况，分别对应 $S_1$ 中是否包含 $m$。
而其余元素的状态与 $m$ 是否出现无关，所以得到 $n^{m-1}\times(x + (n-x))=n^m$。
快速幂一波带走，复杂度 $\mathcal O(\log (n+m))$。
### \* ARC 146 C
之前做过这个但是忘光了，复习一下。
首先整几个 $n=\{1,2,3\}$ 的小样例观察可以猜想 $|S|\le n+1$。
证明可以反证，利用线性基大小为 $n$，故后两个数可以被前 $n$ 个数表示，分讨推翻条件。
这也意味着一个合法的 $S$ 必须满足**线性基大小至少是 $|S|-1$，且剩下的那个数在线性基中的表示 $\text{popcount}$ 是偶数**，不难发现这也是充分的。
大小为 $k$ 的 $n$ 位线性基数量为：
$$
f(k)=\dfrac{1}{i!}\prod_{i=0}^{k-1}(2^n-2^i)
$$
我们可以枚举线性基的大小统计答案。
但是这会面临一个问题：同一个 $S$ 可能会由多种线性基生成。
万幸的是，确定多出来的那个数由几个数异或得到后，数列被线性基生成的次数是相同的，可以直接除去。
这样系数就是 $\sum_{2\mid v}\binom{k}{v}\frac{1}{v+1}=\frac{1}{k+1}\sum_{2\mid v}\binom{k+1}{v+1}$。
另一种更牛的做法是直接去考虑现在还能加哪些数，可能式子会好列一点。
### ARC 147 E
感觉这种 CF-style 的贪心题在 AtCoder 中都会被出题人认为是很难的题，然后放到很后面。
可能这就是文化差异吧。
注意到引起我们交换数的动机都是有 $A_i<B_i$ 的元组存在，那么我们把他们挑出来，这些数肯定要改动的。
而剩下的元组中，$A_i=B_i$ 的肯定是不会被我们动到的，有用的只有 $A_i>B_i$ 的。
考虑如果 $A_x<B_x\le A_y$，那么我们交换 $A_x,A_y$ 实际上就是删去了 $A_x<B_x$ 这个矛盾，引入了 $A_x,B_y$ 这个二元组并判断它们是否有矛盾。
也即：**一次操作的条件是 $B_x\le A_y$，效果是把 $B_x$ 改成 $B_y$**。
所以只要 $A_y\ge B_x$，$A_y$ 的具体大小是无关紧要的，我们只关心 $B_y$ 是否尽可能小，以及这个 $y$ 是否被我们用到过。
不难想到枚举每个矛盾的对，每次确定我们要用哪个 $(A_y,B_y)$ 来解决当前的矛盾。
那么我们还要把 $(A_y,B_x)$ 放入当前的可用操作吗？
注意到一次操作是有效的至少要满足**新的 $B_y$ 比原来的 $B_x$ 小**，那么我们把矛盾对按 $B_x$ 降序排序，$B_x$ 肯定比后面的 $B_i$ 大，不会再被我们用到。
这样我们可以扔掉 $(A_y,B_x)$，因此一次操作至少删去一个二元组，复杂度是 $\mathcal O(n\log n)$。
实现时是要注意 $(A_x,B_y)$ 也可能没有矛盾，变为操作被后面的矛盾用到。
还有就是不要写成 `set`，要用 `multiset`。
---
这个题的大致思路就是：
- 分析操作的动机，将元组分为**矛盾**和**操作**两类；
- 概括出矛盾所在和操作的各项属性：代价、条件、作用效果；
- 贪心法，得到一个 $\mathcal O(n^2\log n)$ 的做法；
- 分析这个复杂度哪里寄了，发现主要问题在**一个操作会生成另一个操作重复被作用**；
- 建立出操作之间的依赖关系，可以得到至少有一种操作序列长度是 $\mathcal O(n)$ 的；(*)
- 依据上面的依赖关系可以得到将 $B_x$ 降序排序再贪心的做法，操作复杂度 $\mathcal O(n)$。
重点在于建立出依赖关系，这可能需要一定的直觉和灵感，其余部分是自然的。
### [CF1452F Divide Powers](https://www.luogu.com.cn/problem/CF1452F)
首先有一个很自然的想法：尽可能的动 $[0,x]$ 以内的数，因为这样一次操作就可以生成一个新的数。
很不幸，这是假的，问题在于**动 $(x+1,n)$ 中的数可能效率更高**。
比如，分裂一个 $2^{x+1}$ 可以新增两个，代价为一；分裂一个 $2^{x+2}$ 可以新增四个，代价为三……
不难发现也只有这种情况可能会效率更高，而且位越低效率越高。
所以我们从低到高枚举 $(x+1,n)$ 中的每一位 $i$，算需要分裂几个完整的 $2^i$。
这样最后我们会面临一个问题，就是说剩下需要的点在 $2^i$ 以内。
此时效率肯定不高于全部用动 $[0,x]$ 以内的数，所以如果合法我们会采用动 $[0,x]$ 以内的数解决。
否则必须有一个分裂 $2^i$ 为 $2^{i-1}$ 的过程，然后问题被分治了，继续做下去即可。
复杂度 $\mathcal O(qn)$。
### [CF1344D Résumé Review](https://www.luogu.com.cn/problem/CF1344D)
我们给 $f(x)=x(a-x^2)$ 求个导，得到 $a-3x^2$，也即导函数单调减。
后来发现我们要用的其实是差分，$f(x)-f(x-1)=a-3x^2+3x-1$ 肯定也是单调减。
所以我们二分一个界表示所有被用到的差分的下界，每次二分即可。
复杂度 $\mathcal O(n\log^2 a_i)$。
### ARC 143 A
不妨有 $A\le B\le C$。
若 $A+B<C$ 显然不合法，否则可以操作 $A+B-C$ 次 $(A,B,C)$，$C-A$ 次 $(B,C)$，$C-B$ 次 $(A,C)$ 来解决。
### ARC 143 B
翻译一下条件就是**每行中的最小值不能是当前列的最大值**。
考虑 $\min$ 值最大的行，不难发现别的行一定满足条件，只需要保证此行满足即可。
考虑容斥，发现容斥后条件即为 那个数所在列的所有数都比它小。
不难发现这也同时满足了别的行的 $\min$ 值不大于它，所以是好算的。
### ARC 143 C
首先我们证明，把每个数 $\bmod (X+Y)$ 对答案没有影响。
原因是这一部分可以通过对称另一方的操作来消除。
现在每个数都小于 $X+Y$，也就是说只有一方能操作。
如果一个数能被先手操作，那么它肯定会被先手操作掉，这显然是不劣的。
之后判断一下两方的情况即可。
### CF1733E
发现每个球经过一定的时间，无论路径具体是怎样，都不会变。
考虑倒着做回去，发现不好做，于是考虑正着 DP。
注意到对当前操作产生影响的有且仅有前几次，就可以 DP 了。
复杂度 $\mathcal O(qn^2)$。
### ARC 143 D
首先先想想桥的数量至少是多少。
我们把 $(A_i,B_i)$ 看作一条边，自环不算。
[一个错解](https://www.luogu.com.cn/paste/k0shodvq)。
发现有一个问题：度数大于等于 $2$ 的连通块不一定没有割边。
事实上，如果 $(A_i,B_i)$ 图中有割边，那么新图中一定也有割边。
所以一个描述可行性的更好的方法是**给每条边定向**，如果这个 e-DCC 能成为一个 SCC 那么就可以。
### ARC 143 E
感觉这场的题没啥惊喜，全是惊吓。
个人评价：A < C < E << B < D。
就是你考虑对于一棵子树，都有两种可能：
- 其父亲在子树的根之前被选；
- 其父亲在子树的根之后被选。
我们猜想只有一种是可行的，这可以归纳证明。
于是就可以 DP 判断无解了，之后问题转化为若干 “A 必须在 B 之前被选择” 形式的条件，用堆拓扑即可。
### \* [P7916 [CSP-S 2021] 交通规划](https://www.luogu.com.cn/problem/P7916)
> 因为之前或多或少得到了不少提示，所以这里的思路曲线可能比较怪。
想想 $k=2$ 怎么做，不难发现这就是要求一个两点间的最小割。
扩展一下 $k=2$，发现 $k$ 更大的情况就是多源点多汇点的最小割，建一个虚拟源点还是可以跑。
但是 Dinic 复杂度是 $\mathcal O(n^2m)$ 的，$n=2.5\times 10^5$，$T$ 还有 $50$，有点寄。
想想不用网络流能不能做 $k=2$，这需要用一个结论：平面图最小割转化为对偶图最短路。
具体地我们对 $k=2$ 的两个点分开的两个“半圆”建一个虚点，再建出对偶图跑最短路。
这样单次的复杂度 $\mathcal O(S\log S)$，其中 $S$ 是区域中的点数，$S=\Theta(nm)\sim 2.5\times 10^5$，好像刚好能过 
$k>2$ 怎么做？先看看 $k=4$，不难发现只有两种情况：$1,3$ 旁边划分或 $2,4$ 旁边划分。
为什么不会有相交的状况呢？画个图分讨一下就可以知道这显然不优。
同理 $k$ 更大的情况也不会有相交，这样我们就可以区间 DP 了。
询问总复杂度是 $\mathcal O(T(k^3+(n+m)^2))$，而预处理要求我们跑出 $n+m$ 个点彼此之间的最短路，这部分复杂度 $\mathcal O(n^3\log n)$，有点寄。
回想一下 $k=2$ 我们是每次直接建图做的，考虑现在也这么做，问题是我漏了一个条件 $\sum k_i\le 50$。
这样总复杂度 $\mathcal O((\sum k_i)\times nm\log(n+m)+\sum k_i^3)$。
---
理一下思路：
- 阅读题面，**发现这就是最小割的定义**；
- 自然想到朴素方法网络流（同时适用性更强）；
- 观察 $k=2$ 的性质，联想到转对偶图最短路，可以解决 $k=2$；
- 对 $k>2$ 进行研究，注意到一个性质：最小割不相交；
- 区间上不相交的东西可以考虑区间 DP，配合最短路可以完成此题。
其实个人感觉一个更合理的部分分是：
- $\Theta(T\times 2^{nm}\text{poly}(nm))$ 10 分；
- $\Theta(T\times 2^n\text{poly}(nm))$ 30 分；
- 朴素 Dinic 40 分；
- $n=500,k=2$ 60 分；
- 正解 100 分。
UOJ 上还卡常，马死了。
### ARC 142 A
不难发现对于一个确定的 $x$，$f(x)$ 只有两种可能的值：去掉所有的后置 $0$ 后是否反转。
那么若 $K < \text{Rev}(K)$ 那么答案肯定为 $0$，否则肯定是在后面加 $0$ 的形式。
### ARC 142 B
首先不难发现边缘的格子一定满足要求，因为相邻格子总和为奇数。
考虑一种构造，每一行奇数位的格子从左往右填小的一半，剩下的填大的一半。
不难证明其正确性。
### ARC 142 C
显然 $\forall x, d_{1,x}+d_{x,2}\ge d_{1,2}$，所以可以考虑枚举 $x\notin \{1,2\}$，对 $d_{1,x}+d_{x,2}$ 的答案取 $\min$。
若 $d_{1,2}\ne 1$ 则答案一定正确，也即我们要判断是否 $d_{1,2}=1$。
若 $d_{1,2}=1$ 则显然有一个点 $x$ 满足 $d_{1,x}+d_{x,2}=3$，且没有等于 $2$ 的。
若这种点不是恰有两个，那么答案就是 $d_{1,2}=1$，否则再取一个 $y$，判断 $d_{x,y}$ 是否为 $1$ 即可。
询问至多 $2n-3$ 次。