二月的做题记录
AGC034E Complete Compress
TAGS：思维
我们考虑枚举最终所有棋子所在的点，分别计算答案。
令这个汇聚点为树的根，则我们需要做的是将所有点移动到根。观察每次操作 $(x,y)$，只有两种情况：$x$ 深度减一 $y$ 深度加一，或者两个点都深度减一。由此猜测所有点深度之和为偶数即有解（根深度为 $0$）。
感知一下，$x$ 如果在某次操作里深度加 $1$ 了，说明这个点是另一个操作点的祖先。而以后需要多一次操作将 $(x,z)$ 将 $x$ 上提，那么显然这两步操作是可以直接合并成 $(y,z)$ 的，因此这种情况一定不优。那么就只需要考虑两个点同时上提的情况。
考虑树形 DP。假设现在在合并根的子树，且假设子树内操作已经做完，则我们的操作都会以根为 LCA，因此只关心每个子树内的目前深度和。比较显然的是，每个子树内其可以达到的深度和是一段连续的奇数/偶数，因此只需要记录一个最小值和一个最大值，剩下的问题是具体如何合并。
将合并的问题抽象一下：给定 $n$ 个数，每次操作可以选择两个不为 $0$ 的数，使他们都减掉 $1$，最小化最后剩下的数之和。一个显然的贪心策略是每次选择最大数和次大数进行操作。这个策略的花费是 $\max(0,2\times maxvalue-sum=maxvalue-others)$ 的。
设每个子树的取值区间是 $[l_i,r_i]$（注意奇偶性）。最大值显然只要不操作就行了，求和即可。需要求的就是最小的 $maxvalue-others$。先将每个子树都取到最大值，然后调整，将最大值调整到最大的临界（再降一步就不是最大值了或者越过下界），此时要使得 $maxvalue-others$ 减小显然已经不可能了。做完了！
HNOI2022模拟测试二十九 game
TAGS：人类智慧，博弈，DP
这不是公平博弈！！！！这不是公平博弈！！！！这不是公平博弈！！！！这不是公平博弈！！！！这不是公平博弈！！！！
因为不是公平博弈，每个人自己颜色的点上的棋子完全归自己管，因此双方的策略都是使自己走的步数减对方走的步数尽量大。
考虑一个棋子能够贡献的步数差，如果下一步走到了一个异色点且这个异色点会给对手带来收益，完全可以选择一直不走这个点，因此步数差会与 $0$ 取 max。那么就可以直接 DP 算出每个点上如果有棋子能够贡献的步数差了。
然后直接做一个背包，计算先手步数大于后手步数的方案数即可。
HNOI2022模拟测试二十九 perm
TAGS：限制转换，DP
再仔细看看排列的基础限制：$\forall 1\leq a<b<c\leq n$ 都有 $(a,c)$ 在 $(a,b)$ 和 $(b,c)$ 中间。
如果将一个 $(a,b)$ 看成一条 $a$ 连向 $b$ 的边的话，这个限制就相当于任意一个区间的边组成的图都是根据可达关系完全补全的，下面简称有传递性。
再冷静一下，二元组组成的是排列每个元素不会出现两次，这说明如果一个区间 $[l,r]$ 不合法则 $[1,r]$ 和 $[l,n]$ 里至少有一个不合法的，因此只需要保证所有前缀和后缀区间里边组成的图有传递性即可。
再仔细思考一下，$[1,i]$ 和 $[i+1,n]$ 互为补图，而两个互为补图的图只有 $n!$ 个。限于水平博主只知道对于一个排列能通过建立偏序图来对应到图，并不知道图怎么单射到排列。
然后考虑直接状压排列来 DP。每次加入一条边后，对排列的操作相当于是交换两个相邻的 $a,b(a<b)$。
HNOI2022模拟测试二十八 checkin
TAGS：容斥，数位 DP
以下提到的 $c,n$ 均为原题面中的值减 $1$。
首先写出 $2^m$ 的容斥式：
$$
\sum\limits_{S\subset[n]} (-1)^{|S|} \binom{n+c*|s|-\sum\limits_{i \in S} b^i+m}{m}
$$
令组合数里的上指标为 $x$，我们知道 $\binom{x+m}{m}$ 是一个关于 $x$ 的 $m$ 次多项式，因此我们只需要在预处理出多项式后对于每个 $k$ 计算所有可能的 $x^k$ 之和。
可以感知到这个东西一定跟 $b$ 进制相关，因为我们需要一个在 $b$ 进制里比较好看的问题，再枚举一个集合大小 $|S|$，那么就可以直接数位 DP 了。具体来讲，用二项式定理展开 $(x+t)^k$ 后就可以用较低次的总和来递推高次的总和，这样子复杂度是 $\mathcal O(m^5)$ 的。
考虑优化。首先枚举集合大小肯定是必须的。需要优化的是数位 DP 部分。考虑 DP 的过程中，如果目前是收到上限限制的话，根本不需要记录目前选择的数的个数，而不受上限限制的部分又跟输入无关，因此考虑在一开始预处理不受上限影响的数位 DP 数组，然后只需要枚举 LCP，将两半部分拼起来，就可以做到 $\mathcal O(m^4)$ 了。
HNOI2022模拟测试二十八 yyl
TAGS：重心的性质
重心的性质 1：一定在根的重链上，利用这个 $\log ^3$ 很好做，不多讲了。
重心的性质 2：必然会有子树大小大于一半的总权值和。
一个点满足性质 2 是成为答案的必要条件，而不可能同时出现两个无交的过半子树，因此这些点构成了一条深度单调的链。将整个问题拍平到 DFN 序列上看，一个子树代表一个区间，而一个包含了过半点的区间一定会包含重点。因此这个序列的带权重点一定是这些点的子孙，那么找到这个点后再倍增跳祖先就好了。
AGC040F Two Pieces
TAGS：计数
我们假设 $A>B$，且第一个棋子的位置永远大于等于第二个。
令 $x,y$ 分别表示第一个，第二个棋子的位置。然后将 $(x,y)$ 看成二维平面上一个点，那么我们的问题相当于：每次可以往右或者上走一步，有一种特殊操作会使得 $y:=x$，问从 $(0,0)$ 在除了开始时刻和特殊操作完时都有 $y<x$ 的限制下走到 $(A,B)$ 的方案数。
首先特殊操作这种 $y:=x$ 很不好处理，考虑原本的限制是不能经过 $y=x$ 这条直线，现在将特殊操作改成将直线下移，即在 $(x_0,y_0)$ 处进行特殊操作会得到新的限制直线 $y=x-(x_0-y_0)$。
审视原问题，每一次特殊操作都会让问题重新回到一个起跑线上，这提示我们考虑最后一次特殊操作。假设是在 $(x_0,y_0)$ 处进行的最后一次特殊操作，最后的终点就会是 $(A,B-(x_0-y_0))$。
假设现在有一条合法的路径，我们考虑一下怎么分配每个特殊操作使用的位置。可以注意到，这条限制直线不会上移，因此一条 $y=x-(x0-y0)$ 的限制直线对应的操作一定是在这条直线与合法路径最靠右的交点上进行的。又因为每次 $y-x$ 的值变化量的绝对值是 $1$，$y=x-k,k\in [0,x_0-y_0]$ 的直线都会与合法路径有交点，因此并不关心具体路径长啥样，只需要知道 $x_0-y_0$ 就行了。
因此，我们只需要枚举 $x_0-y_0$，用类似卡特兰数的方法计算路径数，再用插板法计算将 $n-A-(B-(x_0-y_0))$ 个特殊操作放在 $x_0-y_0+1$ 个交点的方案数即可求出答案。
九省联考2019 秘密袭击
TAGS：DP，线段树合并，线性变换取代复杂标记系统
首先考虑差分，在外侧枚举权值 $i$，计算有多少个连通块至少有 $k$ 个点点权大于等于 $i$，求和后就是最终的答案。
因为并不关心每个连通块具体的大小，可以直接用简单背包来转移。然后用多项式描述这个转移，自然而然就要想到插值。
但是这样子还是不好优化，我们考虑在外层枚举插值用到的横坐标 $x$，然后做内层的整体 DP。对于每个权值 $i$，我们维护两个值 $f,g$ 分别表示连通块暂未结束和已经结束的答案，$g$ 其实就是一个子树类和。然后如果用线段树来维护这个转移的话就需要维护一堆区间标记，形如区间乘，区间加，区间点乘，区间点加。如果你直接维护这些标记的话会非常恶心，需要一种更聪明的维护方法。考虑对于每个维护维护一个线性变换 $(a,b,c,d)$ 表示会将 $(f,g)$ 变为 $(af+b,cf+g+d)$，然后就可以方便维护了。
SNOI2017 遗失的答案
TAGS：FWT
首先我们知道 $10^8$ 以内，一个数最多拥有 $768$ 个约数，也就是说本质上只有至多 $768$ 个有用的询问。
再者，$10^8$ 内一个数至多拥有 $8$ 个不同的质因子。考虑 $\mathrm{gcd},\mathrm{lcm}$ 本质上是对相同质因子的指数取 min\max，因此可以考虑将所有合法的数字（小于等于 $n$，整除 $L$ 且被 $G$ 整除）用一个 $16$ 位长的二进制数来描述，前 $8$ 位表示每个质因子是否取到上界，后 $8$ 位表示是否取到下界，然后在没有限制的情况下用高维前缀和，每一位 $v$ 都让其变为 $2^v$，再高维前缀差分就可以得到答案了。
现在加入了限制，我们考虑容斥，计算没有购买皮肤 $X$ 的方案数。
审视一下做没有限制情况的过程，写出对 $f$ 做高维前缀和与高维差分的式子：
$$
g_S=\sum\limits_{T\subseteqq S} f_t \
h_S=\sum\limits_{T\subseteqq S} (-1)^{|T|-|S|)} f_t
$$
因为我们最后只需要 $h_U$ 处的点值，因此可以考虑删去皮肤 $X$ 对这些数组的影响。那么在知道 $X$ 所对应的二进制数后，只需要枚举其超集就能算出对答案的影响了。预处理即可，复杂度是 $\mathcal O(3^m)$ 的。
HNOI2019 校园旅行
TAGS：优化暴力，二分图，性质
$\mathcal O(m^2)$ 的暴力就是对点对 BFS，考虑优化这个暴力。
题目中给出了关键性质：路径可以不是简单路径。将边分为端点同色和不同色两类，考虑一条路径，将其划分为若干个极长同色 / 不同色边的段。可以重复走某个点，这意味着我们可以给每一段的长度随意加 $2$，那么就只需要考虑奇偶性了。
分开讨论两类边。对于一个极大的同色边组成的连通块，如果其是二分图，则任意两点路径的奇偶性唯一确定；如果不是，则可以通过走一个奇环来切换奇偶性。因此我们只需要保留一棵生成树，如果不是二分图则给这棵树随便加个奇环（自环即可）。
对于不同色边组成的连通块，显然都是二分图，因此也只要保留生成树。
然后我们就只留下了至多 $2n-2$ 条边，再做暴力即可。
USACO22JAN Counting Haybales P
TAGS：DP，观察
可以将题目中的操作转化为更容易理解的形式：交换两个相邻的差值为 $1$ 的数。
显然的是，如果两个数 $x,y$ 满足差值大于 $1$，则他们的相对顺序一定会保持不变。
还可以注意到，两个奇偶性相同的数字一定相对顺序不变，然后就可以 DP 了。
HNOI2022模拟测试二十六 s2mple
TAGS：结论，二分图
首先给出一个结论：对于一张无向图将其边定向使得 $0$ 度点最少，这个问题的答案等于图中的树个数。
证明：考虑图中每个极大连通块，如果其是一棵树（没有重边）可以将其定向成一棵外向树，这样子整棵树中只有一个 $0$ 度点。对于不是树的连通块，取出其一个基环生成树然后环上循环定向，其他定向成外向即可让所有点度数非 $0$。
题目中，我们每次从一个点集中取出两个点，连一条无向边然后定向，可以看成是给某个点的度数加 $1$。那么问题就变成了每次可以从一个集合中选取 $1$ 个点将其度数加 $1$，求最少 $0$ 度点个数。对于这个问题，我们建立一张二分图，令左部点代表集合右部点代表原图中的点，每个集合向其包含的点连边，原图中总点数减去最大匹配即是我们要求的答案。
HNOI2022模拟测试二十六 simple
TAGS：DP，差分
首先考虑 $\mathcal O(n^2 \sum a_i)$ 的 DP：从小到大的加入数字，在状态里记录目前有多少个需要继续往里面放数字的集合，以及这些集合的最大值之和。
考虑如何优化。上面那个 DP 的缺点在于虽然总的差异值会不大，但是在还没确定并减去每个集合里最小值的时候可能会非常大。但实际上，可以认为最大值减去最小值是两者之间的距离，那么我们状态中改成记录目前的距离和就可以做到 $\mathcal O(n^2 k)$ 了。
HNOI2016 最小公倍数
TAGS：连通性，回滚莫队
对于一个询问 $(u,v,a,b)$，考虑在图中保留所有被 $(a,b)$ 偏序的边，然后能够找到一条最大公约数是 $2^a 3^b$ 的路径当且仅当 $u,v$ 在同一个连通块，且这个连通块里两种边权的最大值分别为 $a,b$。
有了这个，我们就可以上回滚莫队了。注意回滚莫队有一维是会来回跳的，这一维需要将值域拍平成序列。
2022IOI选拔决赛前训练4 简单数据结构题
TAGS：手写 Bitset，奇怪树上撒点
假设你能快速提取子树信息，那么至少也要做 $Qlen64$ 次查询，这个显然不太行。有这个 $64$ 的提示，我们可以考虑一下手写的支持快速提取中间 64 位的 bitset。
你显然不能对于每个点都维护一个子树 bitset，考虑在树上撒 $\mathcal O(B)$ 个关键点，然后暴力算出其子树内信息的 bitset，使得每个点子树内都能找到一个子树大小最大的关键点使得最多需要再暴力加入 $\mathcal O(\dfrac{n}{B})$ 个点信息的点。
ZJOI2015 地震后的幻想乡
TAGS：概论，DP
根据题目中的提示，我们考虑计算答案是所有边中第 $i$ 小 $(n-1\leq i \leq m)$ 边的概率。
首先根据 Kruskal 的过程，一组钦定了前 $i$ 小边的方案会让答案取到其中最大那条边的充要条件是 加入第 $i$ 条边前整张图不连通且加入第 $i$ 条边后整张图连通，那么我们可以考虑计算 $a_k=\mathrm{Pr}(x > k)$，其中 $x$ 表示答案是第 $x$ 小的边。
然后考虑 DP，设 $f_{s,i},g_{s,i}$ 分别表示随机选取点集 $s$ 中的 $i$ 条边（不关心相对顺序），且加入这 $i$ 条边后 $s$ 连通 / 不连通的方案数。
首先显然有
$$
f_{s,i}+g_{s,i}=\binom{E(s,s)}{i}
$$
然后就只需要考虑 $g$ 的转移，根据常见连通块计数相关套路，枚举某个特定点 $k$ 所在极大连通块 $t$ 和其中的边数 $j$，有
$$
g_{s,i}=\sum\limits_{k\in t \subsetneq s} \sum\limits_{j=0}^i f_{t,j} \times \binom{E(s-t,s-t)}{i-j}
$$
然后就可以 $\mathcal O(3^n \cdot n^2)$ 递推了。
HNOI2017 影魔
TAGS：扫描线，单调栈
观察一个点 $r$ 能够与哪些右端点组成能提供攻击力的点对 $(l,r)$，设 $r$ 左侧第一个比 $a_l$ 大的数的位置是 $p$，则对于所有 $i \in (p,r),(i,r) $ 都会有 $p_1$ 的攻击力，然后将 $(p,r)$ 区间的数字提取出来，其中所有的后缀最大值位置 $j$ 的点对 $(j,r)$ 会有 $p_2$ 的攻击力。可以发现这个讨论过程跟单调栈很像，那么只需要对于一维限制套个扫描线，另外一维拿个支持区间加法区间求和的数据结构即可。注意要正反做两次。
2022IOI选拔决赛前训练2 劫后余生
TAGS：性质，奇怪的线性基
加法是显然封闭的，我们只用考虑乘法。考虑 $\sqrt{a} \times \sqrt{b}=t\times \sqrt{c}$，给 $t$ 添加一个 $\frac{1}{p}$ 的因子时相应的会给 $c$ 添加一个 $p^2$ 的因子，而最小的 $c$ 是 $a\times b$ 每种质因子指数模 $2$ 的结果，因此本质上相当于出现奇数次质因子集合的异或。那么转化得到的问题相当于是要对 $n$ 个向量组成的向量组求秩。
考虑 $>\sqrt{n}$ 的因子至多一个，而小于等于 $10^3$ 的质数只有 $168$ 个，因此可以对这 $168$ 个质数的部分用 std::bitset 来做，而大于根号的质因子只有一个，也是好处理的。
HNOI2022模拟测试二十四 诚实谦卑
TAGS：随机性质，FFT，最优化转计数
首先因为序列打乱了， 可以认为一整个序列的最优点对的靠后者期望出现在三等分点处，因此答案期望意义下只会有 $\log n$ 个不同的点值。
我们考虑每次求出整体最优解，再递归下去做剩下的部分。为了求出整体最优解我们可以采取一些暴力的算法，对每个数求出离散对数然后做 FFT 求出所有可能的结果即可。
ZJOI2019 开关
TAGS：概率生成函数
先设 $f_i$ 表示不考虑终止，第 $i$ 个时刻在目标状态的概率。分别考虑每一位的选取可以写出 $f$ 的 EGF：
$$
\hat F(x)=\prod(\dfrac{e^{\frac{p_i}{P}x}+(-1)^{s_i}e^{-\frac{p_i}{P}x}}{2})
$$
要将 $\hat F$ 转成 OGF $F$，这个我们后面再说。
设 $H(x)$ 表示从某个状态走了 $i$ 步走回来了的概率的生成函数，可以用类似的方法求出。
然后设我们真正需要的概率生成函数 $G(x)$ 表示在时刻 $i$ 第一次到达目标状态的概率，则会有 $F=G \times H$，而根据 PGF 的那套理论我们最后要求的答案是 $G’(1)$，因此需要分别求出 $F(1),F’(1),H(1),H’(1)$ 的值。
然后我们以 $\hat F$ 为例，将其转换成 OGF $F$。考虑枚举 $n$ 个括号因子里分别选取了 $e^{\frac{p_i}{P}x}$ 还是 $(-1)^{s_i}e^{-\frac{p_i}{P}x}$，最后得到的形式会是 $F(x)=\sum \limits_{i=-P}^{P} \dfrac{a_i}{1-\frac{i}{P}x}$。有了这个好看的封闭形式，求出点值就变得很轻松了！
然而还存在一个问题，和式里存在一项 $\dfrac{a_P}{1-x}$ 而这个的收敛半径是 $(-1,1)$，因此我们需要在求导之前给分子分母同乘一个 $(1-x)$，然后就做完了。