This is my December.
This is my time of the year.
还好这次这个月不是 my time of the year
AGC001F Wide Swap
TAGS：思维，分治
我们考虑在 $P$ 的逆置换 $Q$ 上操作，则问题变成了可以交换相邻两个差大于等于 $k$ 的数，需要优先使小一点的数字靠前。
注意到在这个限制下，对于任意排列 $Q’$，只要不改变任意两个差大于 $k$ 的数的相对位置关系，就一定能够通过交换把 $Q$ 变成 $Q’$。
然后考虑分治排序，问题在于如何将两个序列合并。设合并的左半部分是 $L$ 右半部分是 $R$，显然将 $L, R$ 合并起来后原本 $L,R$ 中的数字的相对顺序都不会改变，那么只需要考虑 $R$ 中每个元素会被交换到哪里，二分即可（或者顺便做个归并然后 pointer）。感觉像是把冒泡排序和归并排序拼在了一起？
实际上还有另外一种做法，也是基于上面给出的关键性质。我们知道这种优先小数字靠前的类字典序问题等价于 reverse 后字典序最大，那么考虑在反图上拓扑排序。具体维护需要用一个堆来存放入度为 $0$ 的点，每次在拓扑序列中加入一个点时计算出新的 $0$ 度点，用线段树实现。
CF555E Case of Computer Network
TAGS：点双连通分量
考虑对于原图的每个点双连通分量，我们一定可以将其边定向成若干个环，变成一个强连通分量，然后其内部的限制就可以忽略掉了。剩下的部分是树上的情况，差分即可。
CF1615F LEGOndary Grandmaster
TAGS：转化，DP
考虑一个神奇转换：将 $S$ 与 $T$ 偶数位置的字符取反，然后一次操作变成交换两个相邻不同字符的位置。然后策略就变得非常显然了，就能随便 DP 了。
这个转化使得不合法操作变得没有意义了，非常牛逼。
IOI2020 Stations
TAGS：通信题
实际要求是判断子树关系。我们考虑一个点 $y$ 在 $x$ 的子树中出现的充要条件是 $y$ 比 $x$ 后入栈，比 $x$ 早出栈，因此我们可以对于偶数层的结点记录入栈序，对于奇数层的结点记录出栈序。
IOI2020 Biscuits
TAGS：DP，思维
考虑小一点的数一定可以凑出大一点的数，因此如果要判断一个 $y$ 是否合法，我们一定会从高位开始贪心填数。
考虑这个填数的过程，设当前填到了第 $i$ 位，我们维护当前需要多少个第 $i$ 位的 $1$ 来补全之前没填完的部分，设为 $b_i$。则当 $b_i > a_i$ 的时候，我们会贪心的把这 $a_i$ 位用完，并将缺少的部分留到更低位去填，则会遗传 $2(b_i-a_i)$ 给下一轮。如果 $b_i \leq a_i$，则我们可以在当前位把之前的数全部填完，进入更低一位的时候相当于是一个全新的问题，这启发我们通过这个 $b_i \leq a_i$ 来划分 DP 的阶段。
设 $f_i$ 表示填到第 $i$ 位时满足 $b_i \leq a_i$ 的合法填数方案数，转移考虑枚举上一个满足 $b_i \leq a_i$ 的位置 $j$，然后在这 $[i,j)$ 位填的二进制数我们会得到一个合法区间，计算即可。
IOI2020 Plants
TAGS：思维，线段树，优化建图，倍增
先考虑如何构造出一种合法的排列。我们考虑从大到小放数字，如果存在一个位置 $i$ 满足 $r_i=0$ 且 $i$ 顺时针前面那些能够覆盖到 $i$ 的点没有一个满足 $r=0$ 的，我们就可以将当前最大值放在 $i$ 这里。然后看成将这个位置删除，将其顺时针前面 $k-1$ 个点的 $r$ 值减 $1$。将这个过程迭代 $n$ 次即可得到一个合法的排列。这个过程可以用线段树加 std::set 来维护。
按照这个构造方法，我们可以发现相邻 $k$ 个数的大小相对关系是一定能够确定的。现在要确定两个距离超过 $k$ 的数的相对大小关系，我们一定得通过找到一个连不等式链来确定。一个暴力的想法是每个点向相邻的 $k$ 个数连一条有向边表示大于关系，然后跑传递闭包。考虑优化，令连不等式的第一个元素是 $a_x$，我们实际上只需要让连不等式链的最后一个元素与 $y$ 的距离小于等与 $k$ 就行了。那么在这个靠近距离的过程中，我们对于每个数只需要保留一条出边，一条使得数字损失最小的边，即小于当前数最大的数，注意需要两种不等关系链。然后倍增优化即可。
IOI2020 Tickets
TAGS：贪心，MO
首先显然每轮取出的 $n$ 个数中，较小的一半贡献是 $-1$，较大的一半贡献是 $+1$。
我们直接给出一个超强的结论：从每个颜色中取出 $k$ 个数，一定能给出一组完整方案，使得每轮选取出的 $n$ 个数，一半在前 $\dfrac{nk}{2}$ 小里一半在后 $\dfrac{nk}{2}$ 小里，即一半贡献 $-1$ 一半贡献 $+1$。
证明考虑归纳，$k=1$ 时显然正确，只需要证明 $k>1$ 时能取出 $n$ 个合法的数进入 $k-1$ 的情况即可。考虑那些只能被分配到特定半区的颜色，每个半区一定只有至多 $\dfrac{nk}{2k}=\dfrac{n}{2}$ 个这样的颜色，那么就一定不会出现分配到最后面发现某个半区无颜色可用的情况。
现在要求出这 $nk$ 个数。首先显然每个颜色选取的数是排序后一段连续的前缀与一段连续的后缀，考虑在最开始钦定每个颜色都选了长为 $k$ 的前缀作为 $-1$ 贡献，然后需要调整一部分颜色去选取后缀，那么一步替换一定是将当前前缀的最后一个数 $a$ 丢弃，换成选取当前前缀前面那个数 $b$，这样子对答案贡献是 $a+b$，显然满足凸性，拿一个堆来维护即可。（也可以直接凸优化）
最后构造方案的时候，也只要仿照证明的过程，先分配那些只能分配到一个半区的颜色，然后剩下的看两个半区的颜色个数即可。
HNOI2022模拟测试十四 简单题
TAGS：集合划分容斥
我们考虑用容斥来处理 $a_i$ 两两不同的限制。考虑现在有一组分解方案 $\prod b_i$，我们将其中相同的数字划为一个等价类，则合法的方案都是等价类个数等于 $k$ 的方案。我们考虑枚举等价类的大小，注意这里大小相同的等价类是没有区别的。然后对于 $n!$ 的唯一分解 $\prod p_i^{q_i}$ 考虑 $p_i,q_i$，对于每个质因子我们用背包将它的指数用完全背包划分到各个等价类中，然后我们就得到了在当前钦定等价类分布情况下的方案数。
接下来要做的事情是调配容斥系数。首先显然这个容斥系数会跟等价类大小有关。我们希望，一个方案被计算的次数是 $\prod f_{size}$ 次，其中 $size$ 是当前方案里每个极大等价类的大小。那么，你可以期望 $f_1=1,f_{i>1}=0$。观察到，在上面我们钦定方案的过程里，一个真实情况的里的极大等价类的每种划分都会被枚举到，如果以类似的方式给钦定方案中每个等价类分配一个容斥权值 $g_{size}$ 的话，我们会有 $F(x)=\exp G(x)$（分别是两个数列的 EGF），因为 $\exp$ 的组合意义就相当于是将一些元素集合按有标号的方式拼合，其实就等价于我们上面提到的划分。那么我们还需要令 $f_0=1$，然后就可以得到 $G(x)=\ln F(x)=\ln (1+x)=\sum\limits_{i=0} (-1)^{i+1}\frac{x^i}{i}$，便有 $g_i=(-1)^{i+1} (i-1)!$。
CF1615E Purple Crayon
TAGS：贪心
最后分数等于 $(n-r-b)(r-b)=r(n-r)+b(b-n)$。考虑在 A 操作完后，每个红点覆盖了她的祖先，那么在剩余没有被覆盖的 $c$ 个点中，B 一定可以通过从叶子开始染色的方式使 $b$ 能够取到 $[0,c]$ 中的每个值。我们知道 B 要尽量使得 $b$ 靠近 $\dfrac{n}{2}$，那么对于 A 来说，在 $r$ 固定的情况下，她一定会使得红点覆盖尽量多的祖先来使得最终的 $b$ 离 $\dfrac{n}{2}$ 远一点，即减小 $c$，显然这个目标要通过将红点放在叶子处实现。考虑直接枚举在叶子处放了 $t$ 个红点，然后问题转化为尽量使得这 $t$ 个叶子覆盖多的祖先。注意到这个问题答案显然有凸性，然后可以建出一个费用流的模型，根据经典结论费用流不会退与源点相连的边的流，我们可以知道随着 $t$ 的变化方案是有包含性的，那么只需要考虑增加 $t$ 时增量的选出当前方案下最优的一个叶子加入方案。考虑用一个堆来维护所有可以使用的长链，每次覆盖祖先时遇到了覆盖过的点直接结束覆盖进程，然后将沿途遇到的长链加入堆即可。剩下一部分可支配的红点，可以认为随便放不改变覆盖祖先数，因为我们总是会枚举到最优解。
联合省选2020 魔法商店
TAGS：拟阵，保序回归
我们知道 $F_2$ 是个拟阵，因此在求价值最小或最大的极大基时都可以贪心，因此可以证明一个基是价值最小的基当且仅当不存在某个能够替换进去的元素价值小于被替换出去的那个，那么我们就得到了 $\mathcal O(nm)$ 个元素变量之间的变量关系，然后直接上保序回归即可。
雅礼集训2018 红蓝树
TAGS：多项式
容易知道 $f$ 的生成函数方程：
$$
F^2(2x^2+x)-F+2^x+x=0
$$
可以直接牛顿迭代 $\mathcal O(n\log n)$ 求解，我们接下来考虑线性算法。
我们知道 $[x^0]F=0$，因此得到：
$$
F=\dfrac{1-\sqrt{1-4(2x^2+x)^2}}{4x^2+2x}
$$
因为要构造线性递推式，我们考虑将分母移过去：
$$
F(4x^2+2x)=1-\sqrt{1-4(2x^2+x)^2}
$$
对于形如 $P=Q^{\frac{1}{2}}$ 的多项式求解问题，经典结论有 $P$ 是一个阶数为 $Q$ 的次数的常系数齐次线性递推式。直接求导得到：
$$
P’Q=\dfrac{1}{2}PQ’
$$
设 $Q$ 次数为 $m$，直接对比等式两边系数可以得到：
$$
Q_0(n+1)P_{n+1}=\sum\limits_{i=0}^{m} P_{n-i}Q_{i+1}(\dfrac{i+1}{2}-n+i)
$$
那么我们可以 $\mathcal O(v)$ 求解 $P(x)$。也可以很容易的写出 $F$ 的递推式：
$$
F_{n-1}=\dfrac{-P_n-4f_{n-2}}{2}
$$
接下来考虑如何求出 $h_{n+1}$。我们先假设 $h$ 是一个线性递推，考虑有：
$$
\forall c,\sum H_k h_{k+c}=0 \
$$
接下来就容易求解了，构造多项式 $H(x)=\prod (x-f_{b_i})$ 即可。
雅礼集训2018 序列
TAGS：保序回归，整体二分，最大权闭合子图，优化建图
差不多是保序回归板子题。
雅礼集训2018 进攻
TAGS：欧拉定理，单调栈，差分
比较暴力的想法是枚举交矩阵，然后算交为这个矩阵的方案。显然不太好算，考虑计算交包含某个钦定矩阵的方案，但是这样子显然会算重，考虑用这个东西容斥。考虑平面图欧拉定理 $V-E+F=2$，即一个矩形内 $1\times 1$ 的矩形个数减去 $1\times 2$ 的矩形个数减去 $2\times 1$ 的矩形个数再加上 $2\times 2$ 的矩形个数正好等于 $1$，这启发我们在这四种图形处计算交矩阵包含它们的方案，再以上面的容斥系数统计进答案，最后每个矩形会正好被算到 $1$ 次。
然后要做的事情就是统计覆盖一个区域的全 $1$ 矩形数量，考虑暴力的做法是枚举矩形然后对差分数组修改，最后做前缀和。我们直接考虑差分操作对于一次查询的影响，那么需要计算的即是钦定某个点为矩形某个角的矩形个数，使用单调栈即可。
具体细节：暴力统计的时候，一个比较直观的想法是把修改矩形截取，然后统计每个图形左下角点被多少个矩形覆盖，这个可以直接考虑每种差分修改对答案的贡献。但是注意到修改矩阵的某个坐标区间是 $[l,r],r<l-1$ 就不太能这么做，但是因为我们图形的边长至多是 $2$，对修改矩形截取的部分正好不会破坏这个限制，因此直接差分是没问题的。
JOISC2018 修建道路
TAGS：LCT，数点
考虑 LCT，每条实链维护一条颜色全部相等的链，然后统计答案的时候可以将 access(a) 过程中的所有实链拉出来，暴力跑二维数点。因为 access 拉出来的实链条数均摊 $\mathcal O(\log n)$，复杂度有了保证。
CF1043F Make it One
TAGS：gcd 卷积
容易发现答案 $\leq 7$，那么做至多 7 次 gcd 卷积即可求出答案。
NOI2017 蔬菜
TAGS：模拟费用流，反悔贪心
容易建出一个费用流模型：将每个蔬菜关于每一天拆一个点出来，每一天从之前一天继承的蔬菜有总量限制，然后模型久很显然了。
考虑动态加边加点的模拟费用流过程，容易发现我们增加一天增广的路径体现在方案上会是选择之前几个蔬菜的出售时间，然后做一个轮换，将最靠前的空位置留给新加入的蔬菜。但是这个轮换的过程显然是完全没法直接维护的。我们考虑，之所以在模拟费用流的时候需要做这个轮换，是因为费用流增广的时候路径在总权值方面是最优的，但是时间的规划并不一定最优。但是如果顺着时间轴做下去，总会无法避免出现新的可用时间然后需要轮换。那么我们考虑时间倒流，模拟退流的过程。因为第 $i+1$ 天的局面一定可以由第 $i$ 天的局面拓展而来，那么退流，也就是反悔的过程可以直接考虑第 $i+1$ 天的哪些蔬菜可以放进前 $i$ 天（通过替换某些蔬菜或者占领空位）。剩下的问题是如何得到一个天数为 $10^5$ 时的最优解。然后就是贪心的过程，因为一个蔬菜占领一个位置，优先使用权值最大的蔬菜并用并查集找到其能放置的最靠后的位置就行了。
IOI2021 Keys
TAGS：启发式合并，迭代缩点
注意到：若 $y\in P(x),x \in P(y)$，则有 $P(x)=P(y)$。若 $y\in P(x),x \notin P(y)$，则有 $|P(x)|>|P(y)|$。因此我们将所有 $P(x)$ 相同的点缩起来后，那些无出度且大小是全局最小的连通分量即是答案。
观察题目可以感知到求出每个点的 $|P(x)|$ 是不现实的，实际上确实很困难，但是我们可以将所有没有缩完点后没有出度的连通分量求出来。
考虑在最开始给每个点钦定一条出边，得到一个基环内向树森林。我们考虑迭代缩点，每次选出一个基环树将它的环缩起来，然后连一条新的出边连出去。当无法再选出一个基环后所有没有出度的连通分量就都被我们找出来了。注意到合并连通分量的时候需要合并钥匙种类，可用的出边以及不可用的出边，在这个过程会有一部分之前不可用的出边因为钥匙的获得变得可用，因此我们需要在启发式合并的时候以这三个总数的和为关键字来进行比较。
IOI2021 Dungeons
TAGS：倍增
注意到一个性质：如果在某一次被敌人 $i$ 打败时的能力值为 $x$，则第一次将其战胜后的能力值至少是 $2x$。这启发我们寻找“现在打不过的将来第一个能打过的敌人”，显然这类敌人只会在整个过程中存在至多 $\log_2 W$ 个。
假设目前的能力值是 $z$，$k=\lfloor \log_2 z \rfloor$，考虑值域区间 $[2^{k},2^{k+1})$，我们默认现在能打赢所有能力值小于 $2^k$ 的敌人，打不过所有能力值大于等于 $2^k$ 的敌人。在这个默认下，用倍增维护出从每个敌人开始往后走能够走到的敌人，获得能力值之和，以及考虑沿途获得能力值的前提下打赢某个能力值大于等于 $2^k$ 的敌人所需要的最少前置能力值。然后倍增跳到第一个能打赢的能力值大于等于 $2^k$ 的敌人，或者第一个让能力值累和大于值域区间 $2^{k+1}$ 的敌人。
但是这样子会被卡空间。我们考虑替换 $2$ 为其他整数 $c$，每次在值域区间 $[c^k,c^{k+1}]$ 里做至多 $c-1$ 次倍增查找。复杂度为 $\mathcal O(n \log_c W \log _2 w+Qc\log_c W \log _2 W)$，$c$ 取 $8$ 时能跑的比较快且将空间限制卡下。
PA2013 Raper
TAGS：wqs 二分，模拟费用流
增量-最小费用任意流 : 每次在图中增加一些点和边，并求解新的最小费用任意流。
只需考虑所有新的 “源到汇的负路径” 以及 “负环” 的贡献。
也可以看做源和汇之间有容量为无穷的边连接，这样“源到汇的负路径”实际上就是“负环”。
先考虑建出费用流模型：将 A 工厂与 B 工厂对于每一天都拆出一个点，一个 A 工厂可以向所有天数比它靠后的 B 工厂连边。因为有费用流模型，所以答案关于光盘数的函数是凸函数，因此考虑 wqs 二分。我们在用 wqs 二分去掉总流量先之后，发现就变成了一个 增量-最小费用任意流 问题。考虑把 A 倒着加入。则源汇路径对应的是选择一个未匹配的最小的 $b_i$ 与当前的 A 匹配。负环情况中，注意经过 $T$ 的负环一定是不合法的（因为费用流的局部最优性），因此对应的是替换之前一个花费较大的 A。
NOI2017 泳池
TAGS：DP，常系数齐次线性递推
最开始的暴力想法是 $f_{h,l,r}$ 表示横坐标区间 $[l,r]$ 有一个高大于等于 $h$ 的安全矩形，且不考虑矩形内部概率的概率。可以发现，因为整个地图中每个格子危险与否的概率是相等的，$f$ 的取值实际上只与 $r-l+1$ 与 $h$ 有关。考虑枚举第 $h+1$ 行第一个出现危险格子的位置，写出转移：
$$
f_{h,w}=p^w\times f_{h+1,w}+\sum\limits_{i=1}^{w} f_{h+1,i-1}\times f_{h,w-i} \times (1-p) \times p^{i-1}
$$
注意到我们需要保证 $h\times w\leq K$，在不考虑 $h=0$ 的情况下状态数是 $\mathcal O(k \ln k)$ 级别的。注意到 $h=0$ 的情况下，递推方程是一个常系数齐次线性递推的形式，使用 bostan-mori 算法加速即可。
NOI2018 冒泡排序
TAGS：DP，组合数学
首先需要意识到一点，交换次数达到下界意味着没有一次交换让一个数与其需要去的位置更远了，因此可以得出充要条件：不存在任意一个位置的数满足左边有比它大的，右边有比它小的。等价于最长下降子序列长度不超过 $2$。
考虑没有字典序限制的情况。设 $f(i,j)$ 表示填完了前 $i$ 个数其中最大值是 $j$ 的方案数。转移的时候考虑下一位填的数比 $j$ 大还是比 $j$ 小。如果比 $j$ 小的话，必须得填上还没有被填的数中的最小值，不然将来一定会出现大于 $2$ 的下降子序列，转移到 $f(i+1,j)$，注意 $i=j$ 时不能走这个转移。或者任意填上一个比 $j$ 大的数，转移到 $f(i+1,j+k)$。可以发现这个 DP 等价于计算这个问题：从 $(0,0)$ 开始走，每次可以往右或者上走，问走到 $(n,n)$ 且不碰到直线 $y=x-1$ 的方案数，其实就是卡特兰数。
考虑扩展到有字典序限制的情况上，每次贴合一段前缀，然后相当于是要钦定下一个位置 $i$ 填的数要比 $q_i$ 大。维护贴合前缀的折线，因为下一格填的数字必须大于 $\max(nowmax, q_i)$，我们钦定当前格往上走到了 $max(nowmax,q_i)+1$ 然后计算路径数。 注意如果贴合前缀的过程中折线碰到了 $y=x-1$ 就不能继续贴合了。
NOI2019 斗主地
TAGS：数学题
首先需要注意到：洗牌后，所有可能出现的牌序是等概率出现的。考虑暴力 DP 怎么写：设 $E_t(i)$ 表示做完 $t$ 次洗牌后 $i$ 位置牌大小的期望，转移考虑枚举被洗到 $i$ 位置的牌上一轮在 $j$ 位置，然后计算概率即可。
我们给出一个结论：$E_t$ 是一个关于 $i$ 的最高次数不超过 $2$ 的多项式。接下来将在证明这个结论的同时导出本题做法。
以 $type=1$ 的情况为例。在洗牌进程还未开始的时候，我们有 $E_0(x)=x$。然后考虑第一次洗牌的过程，假设现在切牌切成了左边 $l$ 张，右边 $r=n-l$ 张，考虑枚举左边的从上往下数第 $x$ 张牌对 $i$ 位置的贡献（注意这里是权值和，最后还要除掉总方案数）：
$$
\sum\limits_x \binom{i-1}{x-1}\binom{n-i}{l-x}x=\binom{n-2}{l-2}i+\binom{n-2}{l-1}
$$
这是一个关于 $i$ 的 $1$ 次多项式。因为可以在外层枚举次数，计算每一次项的贡献，相当于是一直维护这个多项式的系数。同理可以推得关于常数项与二次项的变换规则：
$$
&\sum\limits_{x} \binom{i-1}{x-1}\binom{n-i}{l-x}=\binom{n-1}{l-1} \
&\sum\limits_{x} \binom{i-1}{x-1}\binom{n-i}{l-x}x^2= \binom{n-3}{l-3}i^2+3\binom{n-3}{l-2}i+\binom{n-3}{l-1}-\binom{n-3}{l-2}
$$
我们还剩右边 $r$ 张牌的贡献没有讨论。观察如上多项式系数变换的过程，我们可以将这个过程在干的事情用语言描述出来：将前 $l$ 张牌的位置按 $1$ 到 $l$ 的顺序编号（虽然本来就是这样），现在知道编完号后第 $i$ 张牌的期望是一个关于 $i$ 的多项式，然后通过某种神秘的变换，我们得到了这 $l$ 张牌对 $n$ 张牌的贡献的多项式。因此要将这个变换套在右边 $r$ 张牌上的话，要先将这 $r$ 张牌的位置向左移动 $l$ 格子（变成从 $1$ 开始），显然只需要将上一轮的答案多项式复合 $x+l$ 即可。然后对于左右两个多项式都做完变化后加起来即可。
吐槽：因为答案多项式的最高次数是 $2$，在每一轮洗牌更新多项式的时候可以直接将左右两个多项式的前三项 $2^3$ 枚举算出来，然后插值。
NOI2019 机器人
TAGS：DP，多项式
考虑一个序列中最靠右的最大值，显然任意一个起点都无法走过这个点，因此可以递归判定。考虑用这个思路来 DP。设 $f(l,r,k)$ 表示区间 $[l.r]$ 中最大值为 $k$ 的方案数，转移枚举分割点。注意到枚举每次切割一个合法分割点后 $\sum len$ 是不大的。
写出转移式：$f(l,r,k)=\sum\limits_{mid}\sum\limits_{i\leq k} f(l,mid-1,i)\sum\limits_{j<k}f(mid+1,r,j)$。我们观察一下 $l=0,r=10^9$ 的情况，可以发现 $f(l,r)$ 是一个关于 $k$ 的 $r-l$ 次多项式。这是因为可以将转移看成先对 $f(l,mid-1)$ 与 $f(mid+1,r)$ 两个多项式做点值前缀和，然后将 $f(mid+1,r)$ 的前缀和多项式复合一个 $x-1$，然后将两个多项式点值相乘。回到正常限制的情况，可以发现每个 $f(l,r)$ 会是一个分段多项式函数，段数不超过 $(r-l+1)\times 2$，这是因为每次只会根据 $l_{mid}$ 与 $r_{mid}$ 将两个自变量区间的函数取值设置为 $0$。我们可以方便的在最开始就把这最多 $2n$ 个段的情况给预处理出来，具体实现为将 $[a_i,b_i]$ 变为 $[a_i,b_i+1)$，然后撒在数轴上，每次取出相邻两个点 $(a,b)$ 即可得到一个极大自变量区间 $[a,b)$。我们考虑依次计算每个段 $[c_i,c_{i+1})$ 的 $f$ 的前缀和多项式。首先因为多项式次数至多为 $n$，只需要算出 $n+1$ 个点值然后插值。我们考虑计算 $[a,a+n+1]$ 这个范围的点值，然后插值算出 $f$ 的前缀和在 $ c_{i+1}-1$ 处的取值。计算的时候因为已经知道每个 $f$ 在 $c_i-1$ 处的前缀和，可以直接 $\mathcal O(n\sum len)$ 计算，然后做一次插值。
JOISC 2019 矿物
TAGS：整体二分，交互
首先根据部分分的提示，我们可以用 $2n$ 次将矿物分成内部两两无边的两组。
然后考虑整体二分，每次从第一组中取出一半，查询第二组中有哪些矿物与取出的一半有连边，然后递归的做。然而这样子会被卡询问次数的常数。
分析一波询问次数，设每次从第一组中取出了 $p\times cnt$ 个矿物（$p<1$），则次数为 $f(n)=f(pn)+f((1-p)n)+pn+n$，根据分析我也不知道为什么 $p=\frac{3-\sqrt{5}}{2}$ 的时候最优。注意为了常数，不需要也不能撤销询问。
CF1479D Odd Mineral Resource
TAGS：随机化
莫队做法：直接树上莫队，然后对值域分块平衡查询与修改的复杂度。
随机化：考虑给每个颜色随机一个 $[0,2^{64})$ 中的权值，那么考虑一些点，将其颜色的异或和记为 $x$，当 $x=0$ 时我们判定这些颜色中没有出现奇数次的，显然这个判定算法只有 $\dfrac{1}{2^{64}}$ 的概率把有解判成无解，判定真实无解的情况是一定对的。要求出答案，只需要用主席树二分，每次往一个异或和不为 $0$ 的区间走。
CF348C Subset Sums
TAGS：根号分治
还是老话：看到这么离谱的操作可以考虑考虑分块/根号分治。。。特别是题目里还给出了 $\sum size \leq 10^5$ 这种经典限制
将集合按根号为阈值分为大集合和小集合。然后注意到可以 $\mathcal O(n\sqrt{n})$ 计算出任意集合与任意 大集合 的交集大小，然后讨论一下 $2^2$ 种贡献方式即可。
CF383E Vowels
TAGS：子集和
没搞懂这个长度为 $3$ 的限制有什么用。。。
显然这个异或是为了加速输出，因此我们要考虑把每种元音字母集合的答案都计算出来。
考虑直接递推：$f(S)$ 表示 $S$ 集合的答案，转移考虑去掉最后一位，计算只与这一位有交的单词个数。
CF1325E Ehab’s REAL Number Theory Problem
TAGS：图论建模，最小环
因数个数不超过 $7$ 等价于最多两种质因子，因为 $2^3=8>7$。然后把指数模 $2$ 后会得到如下模型：有若干个二元组 $(p,q)$，问最少选取多少个二元组使得其中非 $1$ 的数都出现了偶数次。我最开始的想法是 $(p,q)$ 向 $(q,h)$ 连一条边跑最小环，但实际上可以直接 $p$ 向 $h$ 连边。现在对于这张图，可以发现不可能存在两个都大于根号的数连边，也就是说最小环至少包含一个小于等于根号的点。直接枚举这个点然后 BFS 计算包含这个点的最小环即可。
CF547D Mike and Fish
TAGS：欧拉回路
属于是典中典了
每个对于给的每个点 $(x_i,y_i)$，从 $x_i$ 向 $y_i$ 连一条无向边，然后对于奇数度数的点向一个辅助点连一条边，容易证明总边数一定是偶数，跑欧拉回路即可，对于欧拉回路上的每条边交替染色即可。
CF986C AND Graph
TAGS：优化边数
观察得到 $x&y=0\Longleftrightarrow \lnot x & y=y$。那么考虑建立如下一张新图来计算连通块数：额外建出 $2^n$ 个点表示 $\lnot x$，每个 $a_i$ 向 $\lnot a_i$ 连单向边，然后每个 $\lnot x$ 向去掉一位的子集连边，再从 $\lnot x$ 连向 $a_i(a_i=x)$。边数是 $\mathcal O(n2^n)$ 级别的，注意不能显式地把边建出来。然后对新图 DFS 计算连通块个数即可。
CF508D Tanya and Password
TAGS：欧拉路径
将两个字符认为是一个点，则一个字符串可以连接其前缀与后缀。跑欧拉路径即可。
CF455D Serega and Fun
TAGS：分块
看到这么离谱的操作可以想想分块。对于每个块维护一个 std::deque 即可。
HNOI2022模拟测试七 简单的bzoj题
TAGS：wqs 二分，闵可夫斯基和
题意：带区间询问的种树
众所周知种树问题的答案有凸性，$80$ 分的暴力只需要用线段树维护当前结点对应区间的 DP 值数组，pushup 采用闵可夫斯基和，注意需要讨论端点的选取（限制形如可否种上树）。
考虑满分做法，采用常见的优化凸性最优化问题算法：wqs 二分。我们考虑用上面那个部分分做法里的线段树来加速 wqs 二分的计算切点部分。显然对于一个线段树结点对应的区间来说只要找到其凸包关于斜率 $k$ 的切点即可，可以采取二分相邻两点之间斜率的方法实现。但是这样子是三个 $\log$ 的，还是不太能过（常数巨大）。考虑层层递进形式的整体二分，对于每个线段树结点维护一个指针，把询问按照当前二分的斜率排序即可。
HNOI2022模拟测试七 简单的字符串题
TAGS：撒关键点，字符串
又是我完全想不到的牛逼撒关键点题。。。
$\mathcal O(n^2)$ 暴力是枚举两个位置 $x,y$，通过 $LCP(x,y)$ 来计算对 $(x,y)$ 对答案的贡献。
考虑枚举两个关键点的距离 $d$，然后在数轴上的 $d,2d,\cdots,kd$ 处撒上关键点，则此时两个开始位置相差 $d$ 且相交的相等串必然至少经过 $1$ 个关键点。考虑枚举“串 $x$ 所包含的第一个关键点 $kd$”，得知此时 $(k-1)d<x\leq d,kd<x+d\leq (k+1)d$，考虑计算出 $S[1:kd]$ 与 $S[1:(k+1)d]$ 的 LCS（Suffix) 以及 $S[kd:n]$ 与 $S[(k+1)d:n]$ 的 LCP，然后就可以获得可行的 $x$ 的范围，直接计算即可。
JOISC2019 聚会
TAGS：交互，随机化
每次随机两个点 $u,v$，然后把其他所有点与这两个点做询问，就可以知道哪些点在 $u$ 到 $v$ 的链上，或者到链路径上的第一个点。递归做即可。我也不知道为什么复杂度是对的。
HNOI2022模拟测试六 树
TAGS：数论
题意：树无标号，儿子有顺序，每个叶子的权值必须是给定 $m$ 个数中某个数的倍数，数权值总乘积小于等于 $n$ 的树个数。$n\leq 10^{10},m\leq 8$。
考虑答案的 DGF $F$，设 DGF $P(x)=\sum\limits_{i}[\exists x,a_x|i]i^{-x}$，然后考虑一个 DP 方式，懂得都懂，然后就有 $F=F^2+F(F-P)+P$，得到 $F=\dfrac{2F^2+P}{1+P}$，注意卷积系统是狄利克雷卷积，所求即是 $F$ 的前缀和。
$1+P$ 的前缀和是好算的，可以 $\mathcal O(2^m)$ 容斥，这启发我们使用杜教筛。于是还需要计算 $F^2$ 的前缀和，注意到 $F_1=0$，因此可以通过计算 $F$ 的前缀和以及整除分块来计算 $F^2$ 的前缀和。转移的时候大概是两个计算前缀和的函数互相调用。
JOISC2017 港口设施
TAGS：图论模型，边数优化
可以将限制描述的更为本质：任意两个有交且互不包含的区间不能被选进相同的栈。在所有这样的区间中间连边，则有解的充要条件是每一个连通块都是二分图，答案为 $2^{cnt}$，$cnt$ 是连通块个数。
然后考虑删掉一部分无用的边，为了快速查找可以连边的区间，可以将区间按左端点排序，然后扫描线，将每个区间放在其右端点对应的下标上，则一个区间能够连边的点即是目前所有右端点被放在目前区间里的区间，体现在线段树上就是单点插入，区间查询。注意到，如果某个点向点集 $x$ 中的每个点连边后，接下来如有一个点也要向 $x$ 连边，在我们所需要处理的数连通块以及判断二分图问题中，只需要保留其连向 $x$ 点集中的任意一条边即可。因此总边数是 $\mathcal O(n\log n)$ 级别的，删掉无用边后对于每个连通块染色判断即可。
HNOI2022模拟测试五 ODST
TAGS：自动机，矩阵转移，奇怪的栈
我们考虑建一个自动机出来，那么首先要做的事是划分等价类。称两个串 $S,T$ 是等价的，当且仅当对于任意串 $x$，$S+x$ 与 $T+x$ 的合法性都是相同的，显然等价关系满足自反性，对称性和传递性，因此把所有的串划分成了等价 类。这样子的性质是非常好的，因为可以通过 $A$ 与 $B$ 合法推出 $A+S$ 与 $B+S$ 合法，因此如果能快速判断两个串是否等价的话就能用 BFS 容易的构造出自动机。在判定两个串 $A,B$ 合法的时候我们不能测试任意的 $S$，选择测试所有长度小于等于 $10$ 的 $S$（正确性没人会证明，但它跑起来很对）。然后我们得知自动机大小为 $8$，很自然的可以想到用三种矩阵来描述转移，剩下需要做的事情就是维护整个序列每个位置所对应矩阵的乘积。
比较棘手的操作是 pop_front，考虑到单纯只是 push_back 只需要做一个类似前缀积的操作，但是 push_front 可能将前缀积破坏，因此我们考虑出现一次 pop_front 后直接将目前还存在的字符隐式反转（指计算前缀积的时候分开考虑），那么在 pop_front 这些字符的时候唯一需要做的操作是取出一个新的前缀积。具体实现可以维护两个栈，一个维护正常的字符，遇到一个 pop_front 就 pop 第二个反转栈，如果此时第二个栈为空就将第一个栈的所有元素插入第二个栈并清空第一个栈，然后对于第二个栈计算一遍前缀积。
记自动机大小为 $m$，可以注意到转移矩阵里只有 $\mathcal O(m)$ 个位置有值，因此转移矩阵乘转移矩阵可以做到 $\mathcal O(m^2)$。在最后统计答案的时候需要用到向量乘矩阵的技巧，也可以做到 $\mathcal O(m^2)$。
HNOI2022模拟测试五 subsequence
TAGS：颜色覆盖均摊，扫描线，ODT
扫描线后可以得到转化：对于一个长度为 $10^9$ 的序列每次需要支持对连续一段染上数字 $x$，以及全局查询小于 $x$ 的数的个数。
考虑维护极长相同颜色连续段，每次如果将所有会被影响到的段拿出来做 $\mathcal O(cnt)$ 的操作，复杂度均摊下来是 $\mathcal O(n)$ 的（$n$ 为操作次数）。那么再用一个数据结构维护每种颜色的区间长度之和即可。维护连续段可以使用 ODT 实现。
CF724E Goods transportation
TAGS：网络流建模，DP，转换
最大流模型是显然的，然后你可能会去考虑模拟费用流，但实际上并不用。考虑转化为求最小割，那么就可以简单 DP 了。
CF568E Longest Increasing Subsequence
TAGS：DP，卡空间
一道卡空间的屎题。
考虑维护每个 LIS 长度的最小结尾数，则对于已有的数字可以用一次二分来更新，gap 则可以暴力枚举填的数。比较麻烦的地方是求出方案。考虑对于每个非 gap 位置记录以其结尾的 LIS 长度和上一位位置（如果上一位非 gap），这个可以通过额外维护每个 LIS 长度最小结尾数的位置来实现。构造方案的时候，设当前处于数组 $p$ 位置，LIS 长度还剩 $i$ 没有构造，则先尝试在所有 LIS 长度为 $i-1$ 的非 gap 位置中找出一个数字比当前 $p$ 位置数字小的，这个过程的复杂度是均摊 $\mathcal O(n)$ 的。如果查找失败，则直接跳到 $p$ 前方第一个 gap 处。
CF585F Digits of Number Pi
TAGS：数位 DP，AC 自动机
比较显然要一个数位 DP，状态中记录是否顶着上限/下限，然后还需要记录是否出现过合法子串。在状态中记录目前匹配到的 SAM 结点已经匹配的长度是可行的，也可以直接将所有长度为 $\lfloor \frac{d}{2} \rfloor$ 的子串插入 AC 自动机中然后记录匹配到的 AC 自动机结点。
AGC030D Inversion Sum
TAGS：DP
分开考虑每一对 $(i,j)$ 的贡献（期望的线性性）。 设 $f(i,x,y)$ 表示考虑完前 $i$ 个操作后 $a_x>a_y$ 的方案，转移显然。注意到每次那些不可能被交换的位置的转移是乘 $2$，则可以直接每次暴力将那些转移不是乘 $2$ 的状态拿出来暴力做，然后对于每个状态记录其最后一次被非乘 $2$ 转移的时间即可。
FJWC2020 lg
TAGS：数论
题意：给出长度 $n$，计算 $\prod\limits_{x_i\in[1,m]} \mathrm{lcm}(x_i)^{\mathrm{gcd(x_i)}}$，模 $998244353$，$n\leq 10^8,m<200000$。
来跟着 iodwad 大力推一波式子（
$$
\begin{align}
\prod\limits_{x_i\in[1,m]} \mathrm{lcm}(x_i)^{\mathrm{gcd(x_i)}} &= \prod\limits_t\prod\limits_{x_i\leq \frac{m}{t}} (t\times\mathrm{lcm}(x_i))^{t\sum\limits_{d|x_i} \mu(d)} \
&= \prod\limits_{t}\prod\limits_{d}\prod\limits_{x\leq \frac{m}{t}} (td\times\mathrm{lcm(x_i)})^{t\times\mu(d)} \
&= \prod\limits_g \prod\limits_{x_i \leq \frac{m}{g}} (g\times \mathrm{lcm(x_i)})^{\varphi(g)}
\end{align}
$$
然后考虑如何计算 $\prod\limits_{x_i\leq \frac{m}{d}} \mathrm{lcm}(x_i)$。显然可以直接考虑每个质因子的贡献，复杂度大概是调和级数状物。
FJWC2020 rng
TAGS：线段树，期望
题意：给出 $a_i$ 的范围 $[l,r],l<r$，问期望逆序对个数，$n\leq 10^5$。
如果你跟我一样 sb 的考虑点对点的贡献，就会得到一个只能用 KDT 维护的暴力积分式子
考虑妙妙的做法，考虑查询的时候枚举数字在哪个长度为 $1$ 的块内，那么之前的数字中出现在后面块的贡献概率为 $1$，同块贡献概率为 $\frac{1}{2}$，前面块的贡献概率为 $0$，用线段树维护 $[x,x+1)$ 中期望数字个数和一堆奇怪的东西即可。
FJWC2020 graph
TAGS：DP，奇妙的转换
题意：给出一个每条边两端点差不超过 $12$ 的无向图，问有多少个导出子图是连通的，对 $2$ 取模。$n\leq 50$。
状压 DP：直接状压后 $12$ 点的联通块情况，状态数是 Bell 数。
组合意义：考虑计算 $\sum (2^{g(x)} \bmod 4)$，其中 $g(x)$ 是连通块个数。可以认为 $2^g$ 是在给连通块染黑白两色，则我们 DP 的时候每个点可以被染成黑白灰三色（灰为不加入任意一个连通块中），其中要限制相同连通块的非灰点同色。那么计算出模 $4$ 意义下的答案后直接除 $2$ 即可。
FJWC2020 string
TAGS：撒关键点，树上启发式合并，后缀数据结构
题意：为每个长度为 $m$ 的子串计算有多少个相似的串（至多一个位置不相同），$n\leq 10^5$。
2log 的题解做法：考虑两个长 $m$ 的串 $a$，$b$，他们相似的充要条件是 $\mathrm{lcp}(a,b)+\mathrm{lcs}(a,b) \geq m-1$。放在正反两棵 parent-tree 上就是 LCA 的深度（串长）之和大于等于 $m-1$。然后考虑在第一棵树上做启发式合并。在讨论轻子树对轻子树，重子树对轻子树的贡献时，考虑枚举将做出贡献的串 $x$，那么能被 $x$ 贡献到的串与 $x$ 在 parent-tree-2th 上的 LCA 深度有一个最小限制，用倍增找到这个最浅 LCA，做一次子树加法，查询时只需单点查询。然后是其他点对重子树的贡献，在查询的时候用类似的思路找到能够造成贡献的子树，做子树查询。记得讨论一些其他杂七杂八的情况。
根号的 zxy 神仙做法：$\mathcal O(nm)$ 的 Hash 做法很简单，需要配合一些索引数据结构。考虑在下标轴上每隔 $T$ 个撒一个关键点。我们知道每个长度为 $m$ 的串只会经过一个关键点，考虑枚举这个关键点，然后考虑对其造成贡献的串，这个串对应过去的关键点位置，称为对称点。在枚举关键点和对称点后，可以查询 LCP / LCS 来获得四段区间，形如“左/右端点落在这个区间里时其到关键点为止的子串的差异为 0”，然后就相当于是能获得一个合法区间，用前缀和记录答案即可。