Solution Set
CF1767F Two Subtrees
首先，考虑询问 \(u = v\) 的情况，发现需要使用线段树合并，或者分块/莫队。
问了一下，可以不用薯粉块啥的。但是 9s 啊 9s，为啥啊为啥。
考虑当前 \(u\) 最小众数是 \(x\) (不妨设 \(\max u_x > \max v_x\))。所以其出现次数是 \(p = u_x+v_x\)。
若 \(y\) 要想超越他，则 \(u_y > \frac{p}{2}\) 或 \(v_y > \frac{p}{2}\)。并且现在不满足这个限制，以后就更不满足了。
所以考虑根号分治？ \(B \leq p\) 的情况很好做，考虑 \(p < B\)。
报废了。
我们先得到一个重剖遍历结果，\(\{w_x\}\)。容易发现区间的总变化量是 \(O(n \log n)\) 的。
然后带权分块，保证每个块内的区间总变化量 \(\leq B\) ，并且再多一步就会 \(> B\) ，这样我们同时保证了块的数量和单块复杂度的问题。
再补一个值域分块处理什么插入删除和求取众数就做完了。
具体的我对出现次数做一个分块，再维护一个每个值域块内是否有出现次数为 \(x\) 的数字。
胜利了。
CF1392H ZS Shuffles Cards
考虑一下会抽到多少张鬼牌，这个可以 \(\min-\max\) 容斥算。
式子大概是：
\[ans1 = \sum_{i=1}^n (-1)^{i-1} \binom{n}{i} \frac{i +m}{i} \]后面式子就是说，选到集合里面的数就结束，否则选到鬼牌。选到数牌的概率就是 \(\frac{i}{i + m}\) ，所以期望轮数就是 \(\frac{i + m}{i}\)
然后每轮期望抽牌数一致。
\[d = \frac{n}{m + 1} + 1 \]这个式子的意思就是说将 \(n\) 张数牌分为 \(m + 1\) 段，第一段会被选，它的期望长度是 \(\frac{n}{m + 1}\)。
\[ans = ans1 \times d \]我猜我是正确的！！！！
模拟赛 20230215 出局
先假定一个选择顺序。
按照顺序去选择，那么当前点可能提前去世了，也可能是被点杀了。
讨论一下，定义 \(f_{i,j}\) 表示考虑前 \(i\) 个，攻击了 \(j\) 次的概率。
随便统计一下就好了。
模拟赛 20230215 打扫笛卡尔
这不比出局简单？这不比出局简单？这不比出局简单？这不比出局简单？
容易发现舒适度就是 \(\sum \frac{dep}{2^{dep}}\)。
做一个简单的卷积就得到了 \(n^2\) 做法。
细写一下，与后面有关。
令 \(f_i\) 表示序列长度为 \(i\) 的答案，\(g_i\) 表示序列长度为 \(i\) 时序列的 \(2\) 的深度次方和。
容易写出转移式：
\[f_i =i!+ \sum 0.5f_j \times \binom{i - 1}{j} \times (i - j - 1)!+0.5g_j \times \binom{i - 1}{j} \times (i - j - 1)!+0.5f_{i-1-j} \times \binom{i - 1}{j} \times (j)!+0.5g_{i-j-1} \times \binom{i - 1}{j} \times (j)! \\ g_i =i!+ \sum 0.5g_j \times \binom{i - 1}{j} \times (i - j - 1)! + 0.5g_{i-j-1} \times \binom{i - 1}{j} \times (i - j - 1)! \]卷和，但是对称，所以有：
\[f_i =i!+ \sum f_j \times \binom{i - 1}{j} \times (i - j - 1)!+g_j \times \binom{i - 1}{j} \times (i - j - 1)!\\g_i =i!+ \sum g_j \times \binom{i - 1}{j} \times (i - j - 1)! \]可以拆开组合数，简单移项：
\[\frac{1}{i!}f_i =1 + \sum \frac{1}{j!}f_j +\frac{1}{j!}g_j\\\frac{1}{i!}g_i =1+ \sum \frac{1}{j!}g_j \]那得到了依赖逆元的线性做法。
发现答案最后要乘以 \(n!\) ，考虑把这个东西提前乘进去。
那么发现最后产生贡献的就是一个又一个的 \(1\)。考虑这些 \(1\) 对最后的贡献，相当于考虑每一位是否乘以 \(i\) 之类的。
然后就做完了。
CF1204E Natasha, Sasha and the Prefix Sums
应该比较简单，但在打摆发呆，战线有些长。
定义 \(f_{n,m}\) 为用 \(n\) 个 \(1\) ，\(m\) 个 \(-1\) 的贡献数，\(g_{n,m}\) 为非 \(0\) 贡献方案数，\(h_{n,m}\) 为 \(0\) 贡献方案数。
枚举第一个数，随便转移就好了。
集合 (20230215 练习题)
容易得到一些暴力的式子：
\[A_k = \sum_i \binom{n - i}{k - 1}T^i \]然后可以得到 \(O(n)\) 做法，很粗暴，然后我就不会了。
题解说，我们可以用组合数递推公式做转化。
\[A_k = \sum_i (\binom{n-i+1}{k} - \binom{n-i}{k})T^i \\ A_k = T\binom{n}{k} + (T-1)A_{k+1} \\ \]迭代可得：
\[A_k = T(T-1)^{-k}\sum_{i=k}^{n} \binom{n}{i} (T-1)^{i} 1^{n-i} \]二项式定理处理一下就好力！
Gym103470 G Paimon's Tree
最大直径，其实就是找最长路径。
定义 \(dp_{u,v,t}\) 表示填了 \((u,v)\) 的边（\(u,v\) 相邻的没填），用了 \(t\) 条边的最大路径权值。
因为路径确定，所以可以算出最多可以丢多少垃圾，随便转移一下就做完了。
模拟赛 20230216 年初购物
被打烂了。
但是 \(wqs\) 二分一下，然后反悔贪心就做完力！
总结是，反对针对单一算法的专题练习，从我做起。
Gym104160 Meet in the Middle
一个粗暴的做法就是枚举一下相遇点，然后我们就可以在 \(n^2\) 左右的时间完成计算。
于是，这启发我继续枚举中间点，但是完成一个计算后，之后的计算就会因为必然不优而终止什么的。
大概类似于整体二分什么的？
做法很巧妙。先提供一种转化，对于询问 \((a,b)\) ，我们将第二棵树的每个点 \(i\) 连上一个新点，边权为 \(dis1(a,i)\)。然后就是维护第二棵树的直径。
考虑离线，按 \(dfs\) 序枚举每个点 \(a\) ，则一次性是一个区间的点的额外边的边权有变化，那么这个区间的点的直径一定不变。那么我们就可以再线段树上维护点集的直径，然后就做完了。
CF1726G A Certain Magical Party
容易发现地，找到最小值 \(x\) ，如果是 \(0\) 类，则最大值等于最小值；如果是 \(1\) 类，则最终值等于 \(x + n - 1\)。
剔除已经是目标值的部分，这些值若为 \(1\) 则随便插入，如果为 \(0\) 则需插入至尾部。
如果存在多个 \(1\) 类值相同，则必不可能有答案。
考虑最大的 \(1\) 类值，它的放置位置是确定的。
以此类推，所有 \(1\) 类值位置均确定。
考虑 \(0\) 类值，先考虑最大的。容易发现，如果有解，那也是固定解。
所以问题是判有没有解。
其实最好是从大到小插入，然后值相同，先插 \(1\) 再插 \(0\)。
每次判断是否有空位就好了。
CF1795G Removal Sequences
对于 \(a_i = deg_i\) 的，他一定在他的邻接点之前删除。
同时，更新邻接点的度数。继续判断度数更新，建出 \(DAG\)。
若 \(x<y\) 且 \(x,y\) 互不可达，则计数。
瞎写个 bitset ，然后分下块卡卡空间应该就可力！
CF1342F Make It Ascending
鉴定为，分高是因为赛时少有人敢写。
考虑拼装出最后的递增序列，每次选定一个集合作为下一个位置的权，肯定选定能选的最小的位置不删最优，记录一下花费和上一个不删的位置在哪儿即可。
复杂度 \(O(n^23^n)\)。
CF919F A Game With Numbers
鉴定为简单题。
搜出所有 \(\binom{12}{4}^2\) 种状态，然后可以根据转移建出有向图，然后跑类拓扑排序确定先后手必胜。
平局一定是转移有环，并且其他转移点一定是先手必胜。
预处理一下就做完了。
CF1463F Max Correct Set
题解说，长为 \(x + y\) 段的不断重复一定是合法的。
因为对于两个数 \(a,b\) 满足 \(a+x=b\) 或 \(a+y = b\) 等价于 \(b - a \equiv \pm x \bmod (x +y)\)。
然后状压 \(dp\) 即可。
CF1523F Favorite Game
完成了 \(i\) 个任务，并且激活了 \(s\) 的传送门的最小花费。
预处理一下最短路啥的即可。
可能是复杂到不可转移的。
仔细想想，定义 \(f_{s,i}\) 表示激活了 \(s\) 的传送门，且刚完成 \(i\) 号任务，最多完成多少任务。
定义 \(g_{s,i}\) 表示激活了 \(s\) 的传送门，且完成了 \(i\) 个任务，立足于传送门之上的最小时间。
转移是 \(f \rightarrow g\)，\(f \rightarrow f\)，\(g \rightarrow g\)，\(g \rightarrow f\)。
CF1712F Triameter
暴力出奇迹。
先找原树直径 \(L\)，然后如果 \(x > L\) 那就是 \(L\)。
否则需要找到经过 \(x\) 的路径。
计算每个点到叶子的最短距离，即找 \(mn_u + mn_v + x \leq dis_{u,v}\)。
然后 \(dsu\) + \(bit\) 可过。
CF1776M Parmigiana With Seafood
好喜欢这道题目。
如果 \(n\) 为偶数，那么 \(A\) 一定可以选 \(n\)，因为他可以一直苟着不选，知道最后 \(B\) 被迫把 \(n\) 露出来。
首先，\(A\) 可以选择叶子！
其次，对于一条长为奇数的链，\(A\) 至少能选其中一个端点，同理，继续苟着。
最后，对于一个三元组，他们距离一个点 \(m\) 距离为偶数，且 \(m\) 是这三个点的割点，则这三个点的 \(A\) 至少能选一个，因为也可以一直苟着，到最后不行了，\(B\) 让他选哪个他就能选哪个。
然后以 \(n\) 为根跑一遍就完力！
CF1776C Library game
考场就会做了，但老早就被看门阿姨赶走了，没有开始调。
具体的，首先分析简单情况，\(B\) 什么时候必胜。容易发现最粗浅的就是如果存在两个大于 \(\frac{m}{2}\) 的就一定可以必胜，因为可以选正中间的点。
考虑将这一思想扩展。如果存在一个阈值 \(B\) ，满足大于等于 \(B\) 的至少有\(\frac{m}{B}\) ，我们发现一定必胜，因为考虑分块，我们每次可以选择两个块的交界点，根据鸽巢原理，必然能选某个点两次。
不妨大胆猜测这是充分必要的。不妨对于每个 \(B\) 定义势能为当前的交界点数量，发现无论下个点点在哪里，势能最多减少 \(1\) 。那么 \(A\) 只用闭着眼睛随便挑合法的区间就能赢了！
CF1783G Weighed Tree Radius
哈哈，这我熟！
对于每一个点 \(x\)，连一个新点，边权为 \(a_x\)。那么偏心距就是到直径端点的最长长度力！
答案就一定是直径上的点诶！那不是做完力！
CF1103D Professional layer
是不是，因为 \(10^{12}\) 以内只有 \(11\) 种质因子，所以直接状压每种因子是否被处理过就好了嘞？
但是对于每个 \(a_i\) 处理每个质因子占用的大小是不同的。
本质不同的 \(a_i\) 感觉不多。听说能过。
但好像有更优秀的做法。哦，一共只有 \(k \times 2^k\) 个转移状态，找到然后用他们依次转移即可！
P4511 [CTSC2015]日程管理
考场写了个基于数据随机化的暴力，冲了很多分。
哦，原数据也冲的过去。
听说存在一个贪心是选择分最多的任务给他选进去，能选就选最晚的时间点处理。
显然正确，考虑怎么维护。
其实我不关心每个任务具体在什么时刻被完成了，我只需要知道这些任务是否能被完成。
所以就好维护了，我是哈卵。
P5333 [JSOI2019]神经网络
这题简单，但看见的时候已经来不及写了。
就是先算一下把每个树拆成若干个链的方案数。
然后做一个背包，进行容斥，相邻两个链不属于一棵树。
注意还要钦定最后一个链不是第一棵树的，这个再容斥一遍钦定他是即可。
好难写啊，口胡了，不写了。
CF1336E Chiori and Doll Picking
学习了 easy version 的做法，使用线性基进行折半搜索，然后 \(FWT\) 合并。
自己想了想 hard version ，继续考虑线性基，然后把他经过一定的变换，使得其正交？
考虑其大小为 \(k\) ，那么当他很小时，我们可以 \(2^k\) 处理了。
题解区给出了一种惊艳的 \(2^{m-k}\) 的做法。
现在我们有一个线性基 \(A\) ，我需要构造出另一个线性基 \(B\)。
使得对于所有 \(x \in A\) ，\(y \in B\) 满足 \(pc (x \& y)\) 为偶数！
那么 \(FWT(A)\) 中为 \(2^{k}\) 的位置一定与 \(A\) 中每个元素与起来的位数为偶数！
那么 \(B\) 张成出来的数一定在 \(FWT(A)\) 中不为 \(0\)。
先说说如何构造出 \(B\)。
考虑我们的构造的目标就是让我们其中的每个元素都与上面的元素与值的位数为偶数，那么我们对那些在 \(A\) 中不存在的位进行考虑，先让其为 \(1\) ，那么对于他前面的位，如果这一位也为 \(1\) ，那么我把他的最高位也添加到当前元素，就满足与值位数为偶数(2)了！否则与值位数为 \(0\) ，同样为偶数。
那么我们可以在 \(2^{m-k}\) 的时间内求出 \(FWT(A)\)。
然后再构造一个 \(G^c = \sum z^x [pc(x)=c]\)。
所以我们可以继续去处理出一个 \(FWT(G^c)\)。容易发现，二进制为 \(1\) 的位数相同的位值也相同。
那么对于一个 \(pc\) 为 \(d\) 的位，我们发现 \(FWT(G^ c)\) 的值为 \(\sum_{i} (-1)^i\binom{d}{i}\binom{m-d}{c-i}\) 。
其中，枚举的 \(i\) 是与值的为 \(1\) 的位数，他的值的来源一定是 \(pc\) 为 \(c\) 的位置！
于是再做一个 \(IFWT\) 即可。
另外 \([x^0]IFWT(X) = 2^{-m}[x^0]FWT(X)\)。好像是手算 \(IFWT\) 得到的。
CF1326F Wise Men
easy version 还是比较简单。发现从 \(14\) 个数中选择 \(7\) 个数的排列数是 \(17297280\)。
枚举出来，当做枚举左右段的元素集合及其排列，然后存放入首末位元素中，本质上就变成了一个或卷积。算一下就做完了。
考虑 hard version。\(n\) 变得很大，我们不能暴力枚举左右的排列数了。但是左右的集合数依然是可以枚举的。
考虑容斥，钦定一些位置是 \(1\) ，其他位置随便是 \(1\) 或 \(0\) 的方案数，那么只要算出来就是一个高维差分就可以算出结果。
发现可以划分成若干连续全为 \(1\) 的段，长度为 \(i\) 的全为 \(1\) 段可以 \(dp\) 处理。
但是每个人不能被重复选，所以就要把这些预处理的连续段 \(FWT\) 卷起来，就可以算出。
发现与相对顺序无关，那么枚举 \(n\) 的划分数，每个算一遍就好了。
CF1034E Little C Loves 3 III
先罗列一些事实：\(2 \times 1/3 = 2\)，\(2 \times 2 = 0\)，两奇数则相同为 \(1\)，不同为 \(3\)。
发现两奇数的情况与异或只能说是一模一样。
被干碎了。就是给每个东西乘上一个 \(4^{pc(x)}\) 的系数，那么就可以做一个 \(|\) 卷积，得到的东西除上 \(4^{pc(x)}\) ，那么最后不满足 \(i \& j = 0\) 的位置的贡献 \(\bmod 4\) 等于 \(0\)。所以就做完了。
Gym 102798E So Many Possibilities...
定义 \(f_{s,i}\) 表示当前已经使用完成了 \(s\) 集合的元素，并且当前最后一个结束位置在 \(i\) 的概率。
然后我们枚举下一个结束位置以及使用元素，同时概率提前乘上。
最后再乘一些预处理的尾巴情况，即那些没有用完的数，最后也没有被用完，但是填了一些位置的方案数。
复杂度 \(O(m^2n2^n)\)。爆炸力！
好像滚一个前缀和就好了？锤子，爆了。
哦，敢写就敢过，\(O(m^2n2^n )\)肯定跑不满，创过去了。
CF1768F Wonderful Jump
我不会又要挨揍了吧？这个贡献啊，他是乘积结构，相当复杂，使用李超树维护大概是困难的。
首先，他这个 \(dp\) 值甚至不单调。破破破破破破防。
我不相信，转移里面好像有什么不可告人的秘密！！！
考虑两个转移区间 \((l_1,r)\) 和 \((l_2 , r)\)，不妨假定 \(l_1 < l_2\)。
如果他们最小值相同...
爬开，讨论个锤子。
仔细观察，可以发现一个值好像会被利用两遍诶。
就是说，如果我从 \(l \rightarrow r\)。
那必须满足区间 \((l,r)\) 里面的最小值不小于 \(\min(a_l,a_r)\)，否则我拆成两段一定更优。嘿嘿。
那是不是可以盘一个单调栈，然后捏我的转移点只能是在单调栈里的点。
然后对于所有他前面的点都可以假定最小值是他自身来转移，那么可以李超树维护，因为我要求的是最小花费。
然后就是单调栈里的内容。那怎么办怎么办怎么办，啊啊啊啊啊啊啊啊啊。
我在说什么，直接维护李超树的右半部分，因为肯定以端点为权值转移最优！做完力！
我在放屁。以自身为最小值根本没法转移 /hsh。
题解好厉害，首先我找到是性质是有用的。
其次，考虑另一种现象：\(\min \times len^2\) 与 \(n \times len\) 的选择。
意思就是选择一整段，或者一步一步跳谁优。
容易发现，前者优的时候 \(\min \times len \leq n\) 。
首先假设最小值是左端点。
那么阈值分治，假设 \(\min > B\) 直接暴力枚举长为 \(\frac{n}{B}\) 的一段。
假设 \(\min \le B\) 则把这些值中最靠右的拉出来转移。
其次，最小值是右端点。
那么如果他大于 \(B\) 则已经完成转移。
否则，我们不断向左找转移点，直到找到第一个大于等于他的位置。
这样复杂度是正确的，因为每个点最多只会被 \(B\) 个点转移到。
做完了！
【20230223 模拟赛】 砂糖的糖果罐
考察一个区间能否被删空，如果里面存在与端点相同的值那就一定删不空。然后，考虑枚举最后一步删除的元素，如果有多个，那就一定删不空。
否则递归考察，直到删空，于是得到了 \(n^2\) 的判区间做法。进而得到 \(n^2\) 做法。
你竟然不留 \(n^2\) 的分？乐死我了。
再仔细观察，发现能被删空的区间一定有单调性：单调不增，单调不减。
注意到区间差会迅速缩小，也即迭代不了几次就会变成完全一样。锤子，实际上如果开始不一样，那永远不会一样捏。由此推出如果一个区间存在两个数相同，除非整个区间相同，否则也删不空。
然后可以迅速迭代。\(\log\) 级别的复杂度？但是两只 /baojin。
强行开各种奇怪的桶应该可以一只 \(\log\) 吧，shabi 鱼。
时限不考虑现实，哈卵。
【20230223 模拟赛】 ANIME-19/一个人举不起克维音之石
自我厌恶了。带权莫队板子题，浅补一下自我反省。
【20230223 模拟赛】 带星者
考虑一个排列的逆，如果和自身不同，但其逆序对数相同，会算两遍，对奇偶性无影响。
然后问题转化成对排列做这个问题。 bitset 随便做一下就完了。
CF1442D Sum
首先最多有一个栈只选了部分，其余的要不不选，要不选满。
哦，然后分治 \(dp\) ，讨论在左区间有没选满还是右区间有没选满。
唔，如果不知道是分治那还是很有难度吧。
AGC002D Stamp Rally
整体二分，做完了。哦，注意一下，要先保留当前的并查集的信息去右区间，要写一个可撤销并查集。
Gym 101623 Factor-Free Tree
先对每个数算一个左边第一个不互质的位置，以及右边第一个与他不互质的位置。
如果相邻两个数不互质，则一定不可能，反之好像一定可能。
AGC044D Guess the Password
首先对每个字符问一遍，算出每种字符的出现次数。
然后对字符种类归并排序，然后就做完了。
【20230224 模拟赛】 大梦的曲调
考虑扩展法。从一个中心开始，不断向外扩展，即 \(2\) 无限扩展，在左右同时找到两个 \(1\) 然后一起扩展一步。
容易发现，任何一个子段都可以由扩展法得到。
那么具体地，我们只需要知道左边有多少个 \(1\) ，右边有多少个 \(1\) 即可算到可扩展区间。
那么对于每一个 \(x\) ，我们易于算出扩展中心。然后二分一共扩展了多少个 \(1\) ，害，真麻烦。
写着真的真的真的很烦欸。
【20230224 模拟赛】 方碑解密
不妨定义一段无效为其 < 与 > 个数相同且存在一种 + 和 - 的匹配使得他们中间的 < 和 > 个数也相同。哦，其实 + 与 - 的位置可以直接用全局位置描述，因为大体等价。
那么去枚举左端点，可以求出区间期望的全局最小位置是多少。
哦，可以预处理后缀，枚举前缀，然后 \(hash\) 解决啊。
但是好像有一点除法，那就要用质数模数 \(hash\)。不知道范围够不够。
先写一下，看看实际情况决定写不写双 \(hash\)。
果然 \(hash\) 爆炸了，得写双 \(hash\)。可恶！
还是跑得相当快，真好！
[清华集训2016] 汽水
二分答案，然后考虑类似分数规划那样去 check。
维护其是否在两段区间存在数。我只用维护是否存在，所以维护一下极值即可。
哦，就是先排一遍序，然后再把他们慢慢加进来。
[WC2018] 通道
边分，建虚树，维护直径。像坨答辩，写个锤锤。
[ARC146E] Simple Speed
考虑连续段 \(dp\)。
\(f\) 为两头未钦定，\(g\) 为两头确定一头，\(h\) 为两头都确定。
\[f_{A - i} = f_i \times \binom{A - 1}{i} \]这个是说，我有 \(i\) 段，先花 \(i\) 个放在右边，还剩下 \(A-i\) 个元素，把连续段插进 \(A - i\) 个缝里面。
\[g_{A-i+1} = f_i \times \binom{A-1}{i-1} \times 2 + g_i \times \binom{A-1}{i - 1} \]\[h_{A-i+2} = f_i \times \binom{A-1}{i-2} + g_i \times \binom{A-1}{i-2} + h_i \times \binom{A-1}{i-2} \][ARC150F] Constant Sum Subsequence
好厉害，根据 \(dp\) 有单调性，考虑分治处理，剪去冗余转移。发现转移是由区间转移到后缀，二分出转移区间即可。
CF1083E The Fair Nut and Rectangles
先按 \(x\) 从小到大排序，然后尝试 \(dp\)。
\[f_i = \max{f_j + x_j \times y_j - y_i \times x_j - a_j} \]然后简简单单李超树。
Walking Plan
一眼类似倍增 \(Floyd\)。
预处理完成后单次询问是 \(O(n^2 \log n)\) 的，跑的是真滴慢。
Rhythm Game
容易发现，问题表述就是让我们将原序列划分成 \(n - k + 1\) 段，然后每个段会带来 \(P\) 的贡献。
因此考虑 \(WQS\) 二分，记录当前有了多少连击，做完了。
完力！这个他不是恰好那么多个 \(miss\) ，而是至少那么多。
定义 \(f_{i,j}\) 表示考虑到第 \(i\) 个键，有 \(j\) 个击中了的最大贡献。
注意到 \(C\) 是单调不增的，\(A\) 是正数。那就是一个单调队列。
萎了，不能用单调队列维护。但是有决策单调性。
CF1152F Neko Rules the Catniverse
从小到大插入！然后状压一下就做完力！
Buffed Buffet
离散食物做背包，同种重量共同处理。
连续食物二分一下吃多少。
[AGC017F] Zigzag
类似轮廓线 \(dp\) ，一条线一条线地考虑。
然后这条线不严格在另一条线的右边，当且仅当前缀 \(\operatorname{popcount}\) 不严格小于上一个。
然后每次选 \(1\) 的时候删去上一条线的一个 \(\operatorname{lowbit}\) 即可。
CF1610G AmShZ Wins a Bet
一个性质是每次删除的一定是合法括号序列。
因为如果删除的是 (?....) 那么如果 ? 是 ) 那么删除 ? 可以使 ) 更靠后。
如果 ? 是 ( 那么删除 ? 可以使 ( 更靠前。
那么考虑 \(f_i\) 表示 \(i\) 后面得到的最小括号序列。然后倍增 \(hash\) 即可维护。
2022-2023 集训队互测 Round 6 >.<
发现这个东西类似 \(AC\) 自动机。那么我们尝试建 \(AC\) 自动机，并且也把单点插入，发现这些位置一定不同，在同一个位置一定完全等价。
那么我们尝试跑最短路。边的数量可能是很大的，因为一个点可能会在自动机上大量出现。
但是每个点的许多转移点与他的 \(fail\) 点一样，只有在自动机上有边的位置才与上面不同。
并且这些转移点只用被这些点转移一次。那么主席树维护，每个叶子只会被转移一遍。做完了。
CF1523H Hopping Around the Array
定义 \(f_{i,j,k}\) 表示从 \(i\) 开始，跳 \(2^j\) 步，删除了 \(k\) 个点，能走到最远的点的点。
很巧妙的定义，规避了大量的数据结构工作，将区间转移变成了单点转移，很厉害。
类似地，在线处理询问，定义 \(g_k\) 表示从起点出发，删除 \(k\) 个点，花费了当前花费步的能走到最远的点的点。
绕了一点，但思路与前面类似，然后就在线做完了。
CF1799F Halve or Subtract
要求和最小啊，和最小。先 \(1\) 再 \(2\)。
我如果知道了哪些位置使用了 \(1\) 操作，那答案就很显然力！
对于一个小于 \(b\) 的数字，\(1\) 操作与 \(2\) 操作只能选择一个。
从大到小排序，那么被操作的数一定是一个前缀，并且先 \(2\) 再 \(1\)。
对于大于 \(2b\) 的数，\(1\) 操作不会干扰 \(2\) 操作，直接从大到小选择使用 \(1\) 操作，然后 \(2\) 操作补刀。
剩下的数，\(2\) 操作肯定先操作没操作 \(1\) 操作的。然后从小到大排序，状态依次为没操作，进行了一次 \(2\) 操作，进行了一次 \(1\) 操作，都操作了的，结合小于 \(b\) 的情况就做完了。
CF1799G Count Voting
首先可以缩成团队考虑，团队内部用多重组合数计算方案。
然后定义 \(f_{i,j,k}\) 表示到第 \(i\) 个队伍，前面有 \(j\) 张票剩余。
CF1799H Tree Cutting
我感觉是一个大大的换根 \(dp\)，复杂度 \(O(n 3^k)\)。
但很难写。
CF1796E Colored Subgraphs
二分，\(dp\)，定义 \(f_{i }\) 表示子树内最少有多少个不合法的链，此时当前链最大是多少。
CF1789E Serval and Music Game
调和级数算一下就好。
CF1789F Serval and Brain Power
\(k \le 3\) 的时候，枚举终点，然后算最长公共子序列。
\(5 \le k\) 的时候，枚举循环节(长度不超过 \(16\)) ，然后 check。
CF1603E A Perfect Problem
一个序列合法，当且仅当从小到大排序后，每一个前缀均合法。
考虑枚举最小值。然后记录选择的和，当前选到的位置，以及当前数选择多少个，已经 \(O(n^5)\) 了。
性质分析题目啊。
首先很显然但是很有用的结论是 \(a_k \geq k\)。
其次是如果 \(a_k = k\) ，那么推出 \(\forall i \leq k\) \(a_i = k\)。
由此，推出 \(a_n = n\) 或者 \(a_n = n + 1\)。
其中，\(a_n = n\) 时，序列确定。
讨论 \(a_n = n + 1\) 的情况。
\((n+1)a_1 \geq \sum a_i\) 即 \(a_1 \geq \sum (a_i-a_1)\)。
因此可以推出整个序列满足条件，并且 \(a_i \geq i + 1\) 则合法。
那么从后往前，算到第一个 \(a_i = i\) 的位置，那再往前的位置的值就确定了。
枚举最小值 ，这样的值只有 \(O(\sqrt{n})\) 个。那么这部分的复杂度就是 \(O(n^3 \sqrt{n} \log n)\) 的。真的很难。
CF732F Tourist Reform
边双，然后发现能变点双当且仅当是边双。
然后把所有点双连向最大的一个，然后就做完了。
[AGC007F] Shik and Copying String
每次复制相当于给每个位置的字母一个扩展区间。从该位置向右扩展的一个区间。
最少复制几次？期望得到线性的做法。
考虑对目标情况的每个字符进行一次溯源，考虑他们的来源。
每个连续段肯定有一个来源，不同连续段一定有不同来源。
因此可以看做若干条不交路径，使得他们纵坐标最大值尽可能小。
于是不妨用队列维护向右转折的点，随着检查点的不断向左移动，那么转折点至少向左下移动。
但是新路径可能会提前到达目标点，这个时候贴着上一条动，那么一定不会增加一行。弹掉会留出空隙的转折点即可。
【20230313 模拟赛】 糖果大赛
做一些简单情况的思考。
如果集合只有一种数 ，那么如果该数不大于 \(2\) 则先手必败，否则必胜。
更进一步，如果集合里面有奇数，并且集合不为 \(\{1\}\) 那么先手必胜。
现在考虑全是偶数的情况。
显然，每个人都不愿意为对方创造出奇数。
那么都会尽可能将 \(w\) 取为偶数。直到只剩下一种数则可以定胜负。
继续考虑特殊情况，如果这些偶数不全为 \(4\) 的倍数，则先手必胜，因为可以操作一次 \(4\)，使得只剩下 \(2\) 。
剩下全为 \(4\) 的倍数，那么如果他们 \(\bmod 3\) 相同，则先手必胜。
否则如果集合为 \(\{4,8\}\) 则先手必败。否则，先手操作一遍 \(12\) 则集合变为 \(\{4,8\}\) ，于是先手必胜。
md，原来是复杂度骗子！
奶奶滴！有 Corner，如果全是 \(12\) 的倍数需要单独考虑！具体地状压就是。
「JOISC 2017 Day 2」门票安排
好厉害的题目。
首先考虑哪些区间翻转。翻转的区间显然有交集，否则不翻转更优。
不妨记 \(a_i\) 为 \(i\) 位置在区间翻转前被覆盖次数。
\(b_i\) 为 \(i\) 位置在区间翻转后被覆盖次数。显然 \(\max b_i\) 就是答案。
考虑交集 \([x,y]\)，我声称存在 \(t \in [x,y]\) 满足 \(b_t \geq \max b_i - 1\)。
不妨假设不成立，那我翻转一个右边界为 \(y\) 的区间和一个左边界为 \(x\) 的区间那么 \(b_t\) 增加 \(2\) ，其他不增甚至减少，于是答案不会变劣。
另外 \(a_t = \max a_i\) ，因为假设 \(a_k > a_t\) ，那么 \(k \not \in [x,y]\)，因为区间里面元素变化是等价的。
如果在里面 $ b_t$ 就不是最大值力。那么一定有一个翻转了的区间翻转前不包含 \(k\) ，由于这个区间 \(t\) 的会减少 \(1\) 的覆盖次数，\(k\) 会增加一次，于是就带来 \(2\) 点的变化量差。于是有不等式 \(a_k - b_k \leq a_t - b_t + 2\) ，整理可得 \(b_k - b_t \geq 3\)。与上一条性质矛盾了。
同理我们也可以证明所有 \(a_k = \max a_i\) 一定有 \(k \in [x,y]\)。
因此我们就可以算出交集至少是多少。接下来我们二分答案，根据性质我们就可以算出至少我们需要翻多少个区间。
然后从小到大贪心地让每个 \(a_i\) 都不超过二分的答案，检查是否可行。具体地我们开一个堆维护区间，每次选择右端点最大的翻转，因为这样造成的代价是最小的。
很厉害的题，做完了。
CF1804E Routing
本质上是找一个环，这个环的邻接点集合是全集。
那枚举一个起点，记录当前集合以及当前点是否可行，然后转移。
这是什么 \(O(2^n n^3)\) 的巨大复杂度算法。
哈哈！我是哈卵！
枚举一个点集，然后判环。关于判环，我只需要钦定起点是最小的点即可！
CF1804F Approximate Diameter
我考虑瞎选一个点，找到距离离他最远的一个点与他的距离。
这个距离一定是满足下界的，而且卡的很严格。应该是正解的一部分。
然后问题是这个距离的上界实际上是 \(d(G_i)\) ，离要求的上界还很远，感觉相当浪费。
并且计算最远距离也是一件不容易的事情。
考虑一下这个上界是怎么来的。
如果加入了一条边，会影响我的直径，那么最多最多会让我的直径变化为原来的一半。
但你能减半几次？乐！
那么大概思路就是，我先找到一个答案，然后在发现答案不行了之后重新算一个答案。
二分，我二分一下我的答案在什么时候减半。做完了。
【20230314 模拟赛】 游戏
列举一些性质。
倘若两个个元素被交换，那么必然意味着其中一个会被单杀。
如果大招没有把怪杀到 \(k\) 个，那么死去的怪必然连续。
否则死去的 \(k\) 个怪一定是区间内最大的，区间内其他没有被选中的一定是被单杀。
但是好像可以按顺序依次贪心欸。先只考虑算前缀的答案。
那么每个数可以直接被抽象为权值 \(a_i - i \times w_s\)。
那爷每次选择最大的不tmd就好了。被诈骗了。哈哈哈哈！
【20230314 模拟赛】 划分
这里有两个做法，一个是理论复杂度 \(O(d(a_1)n)\) 的做法，一个是理论复杂度 \(O(n \log^2 n)\) 的标算做法。
其中 \(d(a_1)\) 是 \(a_1\) 的因子个数。但是数据并没有刻意卡满，因此可以通过。
下面我们默认已经将 \(a\) 从小到大排序了。
结论 1： 在最优情况下，最多只会有一个集合内部存在两个不同的数。
证明： 如果存在这样的两个集合，我们可以把两个集合拼起来，然后把最大的数踢出集合单独组成集合，可以发现集合个数不变。现在我们讨论权值变化。设两个集合的最大公约数分别为 \(d_1,d_2\)，最大值分别为 \(mx_1,mx_2\)，那么一定有 \(d_1 \leq \frac{mx_1}{2}\) 且 \(d_2 \leq \frac{mx_2}{2}\)。所以一定有 \(d_1 + d_2 \leq \max(mx_1,mx_2)\) 证毕。
下面我们称这样的集合为 大杂烩。
结论 2： \(a_ 1\) 一定在大杂烩内部（如果有这样的集合）
证明： 反证。假设 \(a_1\) 不在该集合中，那么把 \(a_1\) 加进该集合并且把该集合最大数拉出来单独组成集合更优。设该集合的最大值，最小值，最大公约数分别为 \(mx,mn,d\)。那么有恒等式 \(d \leq mx - mn\)。所以可以得到 \(a_1 + d \leq a_1 + mx - mn \leq mx\)。证毕。
Solution 1:
我们枚举大杂烩的最大公约数至少为 \(d\)。显然一定是 \(a_1\) 的因子。
现在我们尝试把集合的数量压制到最小，然后慢慢放开限制。
然后我们把能被 \(d\) 整除的数压成一个集合作为我们的大杂烩。剩余的数相同的放在一个集合。
然后我们慢慢地把我们使用的集合数目变大，即每次选出一个不单独成为一个集合的最大的数拉出来单独组成一个集合，这样一个过程一定是在当前枚举意义下最优的。
做完了。复杂度 \(O(d(a_1)n)\)。卡掉该做法也很简单，因为在 \(10^{12}\) 以内，因子最多的数有 \(6720\) 个，找到他作为 \(a_1\) 就好了。
结论 3： 存在最优情况，使得大杂烩由一段前缀和最多一个其他的数并起来得到。
证明： 继续考虑反证。假设存在一个最优情况，该集合为 \([1,p-1] \cup \{x , y\}\) 且 \(p < x\)，\(x < y\)。
那么，我声称集合 \([1,p] \cup \{x\}\) 一定更优。考虑前者的权值为 \(\gcd(d_1 , a_x , a_y) + a_p \leq a_p + a_y - a_x < a_y\) ，后者权值为 \(\gcd(d_1,a_p,a_x) + a_y\)，所以容易发现后者更优。 矛盾了，证毕。
Solution 2:
由结论 \(3\) ，我们想到去枚举前缀 \(\gcd\)。容易发现，不同的前缀 \(\gcd\) 只有 \(O(\log A)\) 个。
我们找到最长的一个前缀 \(\gcd\) 为 \(d\) 的前缀，考虑计算答案。这样做可以尽可能地压缩我们的集合数量，以算到更多的答案。
这里需要先枚举一个最优的并进这个前缀集合的数，把并进去和不并进去答案都算一遍。
然后后面的数跟 Solution 1 的处理方法类似。把剩下的相同的数并在一起，压缩集合个数，然后每次选择一个最大的数拉出来单开集合，解压集合个数。
还需要单独处理前缀 \(\gcd\) 为 \(d\) 的其他前缀的答案，但如果需要单独处理，说明这个前缀右边的每个数都单独组成集合。
继续考虑反证，因为把这个前缀往右边扩展一步，他的前缀 \(\gcd\) 不变，于是就可以把右边的一个集合拆开，集合个数没变，但答案一下子就变优了。
然后就做完了！
「雅礼集训 2018 Day7」C
看了一点提示，原来点与点之间关系很小啊。流汗！
那不妨假设 \(f_{i,0/1}\) 表示恰好有 \(i\) 个 \(1\) 的时候，为 \(0/1\) 的数字的期望访问次数。
那么有转移方程如下：
\[f_{i,0} = \frac{n-i-1}{n} f_{i+1,0} + \frac{1}{n} f_{i+1,1} + \frac{i}{n} f_{i-1,0} + \frac{1}{n} \times (i \not = n-1) \]\[f_{i,1} = \frac{1}{n} f_{i-1,0} + \frac{i-1}{n} f_{i-1,1} + \frac{n-i}{n} f_{i+1,1} + \frac{1}{n} \times (i \not = 1) \]然后递推解方程就是了。
「LibreOJ β Round #4」求和
推式子！
我们不妨假定 \(N \leq M\)。
\[\sum_{i=1}^N\sum_{j=1}^M \mu^2(\gcd(i ,j)) \\ \sum_{d=1}^N \mu^2(d) \sum_{i=1}^{\frac{N}{d}} \sum_{j=1}^{\frac{M}{d}} [\gcd(i,j)=1] \\ \sum_{d=1}^N \mu^2(d) \sum_{i=1}^{\frac{N}{d}} \sum_{j=1}^{\frac{M}{d}} \sum_{T|i,T|j} \mu(T) \\ \sum_{d=1}^N \mu^2(d) \sum_{T=1}^{\frac{N}{d}} \mu(T) \lfloor \frac{N}{Td} \rfloor \lfloor \frac{M}{Td} \rfloor \\ \sum_{T=1}^{N} \mu(T) \sum_{d=1}^{\sqrt{N}} \mu(d) \sum_{i=1}^{\frac{N}{d^2T} }\lfloor \frac{N}{Td^2i} \rfloor \lfloor \frac{M}{Td^2i} \rfloor \\ \sum_{d=1}^{\sqrt{N}} \mu(d) \sum_{T=1}^{\frac{N}{d^2}} \mu(T) \sum_{i=1}^{\frac{N}{d^2T} }\lfloor \frac{N}{Td^2i} \rfloor \lfloor \frac{M}{Td^2i} \rfloor \\ \sum_{d=1}^{\sqrt{N}} \mu(d) f(\frac{N}{d^2},\frac{M}{d^2}) \]然后我现在尝试推导 \(f(n,m)\) 的计算，我尝试在 \(O(\sqrt{n})\) 的复杂度完成计算。
\[f(n,m) = \sum_{d=1}^n\mu(d) \sum_{T=1}^{\frac{n}{d}} \lfloor \frac{n}{dT} \rfloor \lfloor \frac{m}{dT} \rfloor \\ = \sum_{d=1}^n \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \sum_{T|d} \mu(T) = nm \]可以 \(O(1)\) 计算，太草了吧。做完了。
CF1427E Xum
每次处理最高位。把最低位和最高位对齐，然后经过一定变换，容易得到最高位的两倍。
用这个把前面的位消掉，就得到了消掉最高位的数。
做完了。
[AGC018C] Coins
维护 \(a\) 变 \(b\) 的堆，然后每一次考虑每一个人选取最大的一条路径即可。
芒果冰加了空气
链是易于解决的。然后我们考虑对子树计算。
不妨考虑我们是在什么时候选择的当前根节点，所以设 \(f_{ i,j}\) 表示以 \(i\) 为根的子树，\(i\) 至少被下面 \(j\) 个分治中心给覆盖到。然后做背包就好了。
关键就是根节点是在怎样的相对时间里作为分治中心，因为这决定了子树内的方案是否独立！
Mergesort Strikes Back
首先因为 \(n\) 确定，我们可以发现归并排序的区间是固定的呢。
然后区间内已经是逆序对的，之后会一直形成逆序对。
我们可以给每段缩成一个上升序列，那么两个序列合并本质上是对这两个上升序列进行合并。
并且上升序列后面跟着的数一定是连续紧跟的。
草，真是按照概率去做！
然后算段间两个元素形成逆序对的概率。假设 \(a_i > a_j\) ，设 \(p_i\) 为 \(a_i\) 在小段内位置，\(p_j\) 为 \(a_j\) 在小段内位置，然后发现这 \(p_i+p_j\) 个元素最大值要在前 \(p_j - 1\) 个中，那么概率为 \(\frac{p_i-1}{2(p_i+p_j)}\)。
无序概率为 \(\frac{p_i+p_j-2}{2(p_i+p_j)}\)。然后发现概率只与 \(p_i + p_j\) 有关系。
【20230316 模拟赛】 小水题
本质上是每次选择最小的点，逐渐联通，这样会形成树状结构。
放海绵放在叶子节点最优。那么长剖，每次选择最长的链加进去就好了。
CF360D Levko and Sets
找到原根，然后 BSGS 计算每个 \(a_i\) 的次数。
然后就转化成了和的问题。
不急，我先别急。先考虑 \(n = 1\) 的情况。
这不弱于去找 \(m\) 个数在模意义下组成的数的种类数。
裴蜀定理！
在 \(n = 1\) 的时候乘上了一个系数。一样算就好了！
然后 \(n\) 大了，我就把那些数从小到大排序，取一个前缀算一下公倍数，大的就直接暴力枚举。
不知道能不能过。不能过。
但是可以把每个因子拉出来跑，得到一个仅由该因子管辖的数的数量。
做完了。
【20230317 模拟赛】线性代数
不取模！说明答案真的很小。
基不同，集合一定不同。那么我们就去构造基。
然后这个集合能够张成出的最大的数一定是所有数全部异或起来。
定义 \(f_{i,j,0/1}\) 表示从大到小考虑到第 \(i\) 位，基的大小恰好为 \(j\) 的方案数，最大值是否达到上限的方案数。
做完了，虽然还是不懂为什么不用取模。
你妈。要写高精，这就是你不取模的理由吗？组题人纯 nt。
【20230317 模拟赛】森林
好，组题人成分鉴定完毕，现在我们带上有色眼镜来看这道题。
首先 \(6s\) 时限很特别，值得深思。
然后一个点集，在 \(T_1\) 中是连通块，在 \(T_2\) 中是链。
我觉得，链的性质优于连通块的，连通块的又优于点集的。
我尽可以枚举一条链，并且使用可撤销并查集判断是否构成连通块。
这就是 \(60pts\)。好多，不过组题人都是这种成分了，什么不正常呢？
\(T_2\) 为链的部分，可以分治。是的！
我在 \(T_2\) 中分治，计算经过分治中心 \(mid\) 的合法链。
那么我在 \(T_1\) 中以 \(mid\) 为根，扩展出一个每个点都在分治区间内的连通块！
那么就可以发现选定某个点就要求其父亲也能被选择。枚举左端点，右边维护一个前缀 \(\min\) 即可计算
会了 \(80pts\) 了，不错！
然后考虑整个问题。不妨继续分治，做一个淀粉质，这个东西的常数很符合时限 \(6s\)，数据范围 \(10^5\) 的现实。
我对 \(T_2\) 进行点分治，同样每次在 \(T_1\) 中扩展连通块，确定前驱限制。限制本质上是必选哪个点。
每个点只有一个父亲，所以只有一个需求。从根往下枚举链，显然就需要他们的需求要不就在自己子树内，要不就构成一条链。同时也找找每个点被哪些点需求，打上标记。
需求也分很多种，一种是向子树外需求，一种向祖先，一种向后代，最后一种怎样也无法满足，摆烂。
维护的时候，向子树外的需求不管，向祖先的直接打上硬标记，向后代的在后代上打标记。
然后计算的时候，就同样打标记，但是得找到向子树外的需求，使得他们构成链。
每加进一些点就去满足前面的一些子树的需求，当前链的需求被满足穿了之后就去统计子树外的那条链的子树内还有多少的需求被满足穿了。不太好写，常数很大，但优势在我。
「2021 集训队互测」序列
想到 2-SAT 过后，后面的部分就不难了。
没想到的同学看到这里可以再去想想。
就是说对于每个数，将关于他的限制拉出来。按权值从小到大排序。
对于每个限制，可以限制出该数 \(< x\) 或者 \(\geq x\)。
以此拆成两个点，然后该数内部点之间连限制边，逻辑类似该数小于一个数那么也应该小于更大的数。
然后接下来我们要连边去满足限制。
对于一个限制 \(i,j,k,x\)，我们对点 \(i\) 考虑。如果 \(a_i < x\) , 那么就要求 \(a_j,a_k \geq x\)。
如果 \(a_i > x\)，那么就要求 \(a_j,a_k\) 小于关于他们的限制权值中，\(x\) 的后继的那个值。
然后跑 2-SAT 就做完了。
【UNR #3】百鸽笼
我会一个 \(O(2^n n \sum a_i)\) 的做法力！
啊啊啊，可以认为已满的列也可以塞管理员。
定义
\[G_{k}(x) = \sum_{i=0}^{a_{k} -1} \frac{x^i}{i!} \]令我们在计算第 \(k\) 列，则答案的生成函数为
\[F(x) = \frac{x^{a_k-1}}{(a_k - 1) !} \prod_{i != k} (e^x - G_k(x)) \]好厉害。可以去处理 \(x^i(e^x)^j\) 的系数，记为 \(f_{i,j }\)，可以背包 \(dp\) 处理。
\[ \frac{f_{i,j}}{n^{i+1}} \sum_{d=0} (d+i)! \frac{j^d}{n^{d}d!} \\ \frac{i!f_{i,j}}{n^{i+1}} \sum_{d=0} \binom{d+i}{i} \frac{j^d}{n^{d}} \]由广义二项式展开得到：
\[(x+y)^{-n} = \sum_{d=0} (-1)^d \binom{n - 1 + d}{n - 1} x^dy^{-n-d} \]于是转化上式得到：
\[\frac{i!f_{i,j}}{n^{i+1}} \sum_{d=0} \binom{d+i+1-1}{i+1-1} (-1)^d (-\frac{j}{n})^d \\ \frac{i!f_{i,j}}{n^{i+1}} (1-\frac{j}{n})^{-(i+1)} \\ \frac{i!f_{i,j}}{n^{i+1}} (\frac{n}{n-j})^{i+1} \\ \frac{i!f_{i,j}}{(n-j)^{i+1}} \]「Nowcoder 48C」铬合金之声
感觉就很生成函数，是吧。
先枚举点，再枚举生成树。
定义：
\[F(x) = \sum_{i=1} \frac{i^{i-1}}{i!} x^i \]答案就是：
\[n![x^n]F^m(x) \]草，构造度数为 \(n - m\) 的虚点。Prufer 序列，做完了。
「ZHYOI」Round 2 variance
就是说，前缀或值共有 \(\log\) 种。平方和计算比较麻烦。
然后全部拆开按位算。
[NOI2013] 树的计数
考虑对 \(bfs\) 序分层，一个分层合法，要求每层内部是升序。
那按 \(bfs\) 序分段，check 一下在什么时候可以分段即可。
细节题都去死啊啊啊啊啊。
「BZOJ4833 Lydsy1704月赛」最小公倍佩尔数
简单列一下式子。
\[f_n = \sum_{i=1,i \bmod2 \equiv 1} \binom{n}{i} 2^{\frac{i-1}{2}} \]完全错了，不会就是不会。
得到递推式：\(f_n = 2f_{n-1}+f_{n-2}\)。
然后也有 \(\gcd(f_a,f_b) = f_{\gcd(a,b)}\)。
考虑 \(\gcd\) 与 \(lcm\) 互化。使用 \(\min-\max\) 容斥。
\[g_n = \prod_{T \subset S} f_{\gcd(T)}^{(-1)^{|T|-1}} = \prod_{i=1}^n f_{i}^{\sum [\gcd(T) = i](-1)^{|T|-1}} \]尝试对上面进行莫比乌斯反演。
\[H_x = \sum_{T \subset S} [\gcd(T)=x] (-1)^{|T|-1} \\ = \sum_{x | d} \mu(\frac{d}{x}) \]然后就可以递推了。
「BZOJ4231」回忆树
从根节点到 \(u\) 的贡献可以离线建 AC 自动机计算。
然后在 LCA 处差分。然后发现在 LCA 处会算多或者算少一些东西，kmp 统计一下即可。
P9150 邮箱题
是我可以做的题！
使用 钥匙 这个限制，就可以把问题拆成若干个无关的部分。每个部分都是一个环。
然后对于环上任意一个点，他遍历点的顺序都一定是按照环上的顺序依次遍历。
先考虑 \(O(n^2)\) 的做法。
问题是问每个点出发的可达点数量和所在强连通分量大小。
他的强连通分量一定是一个区间。
开个栈，维护可达点的强连通分量。每次加入一个点，检查最靠右的那个强连通分量是否有到该点的入边。然后确定是否可加入，若可加入，那么判断他最远可以到达哪个点，把这之间的强连通分量都可以合并。
然后就在 \(O(n^2)\) 的时间里解决了问题。
考虑更进一步，去计算我们所有的答案。上述做法我们是确定了起点的，向后扩展答案，感觉难以优化。
不妨换个角度，我们倒着来，从后往前枚举起点！
我们可以维护两个栈，一个维护可达区间，一个维护强连通分量区间。
每次向前面加入一个点，于是可以检查是否可以把栈顶的两个可达区间合并。
实际上就是检查后面那个区间开头的点是否往当前区间有入边。排个序二分一下即可。
其次，如果可达区间可继续合并，当且仅当上一次合并完的区间整体构成强连通分量，否则最靠右的强连通分量不变可达性就不会改变。
现在我们需要进行强连通分量判定。即右边是否存在一个强连通分量对当前强连通分量有入边。
本质上是矩形内检查点的存在性，当然可以主席树，但被卡空间了。
我们更多地去利用性质。注意到同一个可达区间的联通分量，靠右的不会向靠左的有出边。
直接用所有的前向出边减去同一个强连通分量的前向出边就是右边的强连通分量对当前强连通分量的出边数量了！
树状数组即可维护！做完了！
P9151 计数题
嗯，总结一下这道题的心路。
就是说第一反应是去构造生成出来的那个串，枚举下一位填 \(0/1\)。
然后标准化我们的构造，使得我们的构造最优（即对后面的影响最小）。
但是从实际上我们发现，最小化我们使用的原串元素个数不一定能使下一个数更容易填。
发现如果下一个数与当前数相同，那肯定当前数越靠前后面的数越有可能被成功选择。
但是，如果不同则不然。比如说 0001 生成 01。
于是想到相同的子段是容易决策的，不同是不容易的，于是我们着重考虑从连续的一种到连续的另一种的转移。
考虑到方案的变化只能从原来向外扩展偶数个元素，偶数个元素瞎合至少会出现 0/1 中的一个，那如果他被夹在一段连续的 1 和一段连续的 0 之间，那他就可以被删去！
于是这就相当于在 \(S\) 中选出若干个不交的区间，相邻两个区间之间相隔偶数个位置，这样我们可以把那偶数个位置随便合，然后再跟左边合一下，因为如果能跟右边合就一定可以在更早的起点被找到。
于是维护 \(f_{i,j,0/1}\) 表示从 \(i\) 开始得到 \(j\) 个 \(0/1\) 的最小长度。
题解声称，如果 \(f_{l,a , 0} = x (a \geq 1)\) 那么有 \(f_{l,a+1,0} = x + 2k + 1\) ，其中 \(k\) 为最小的一个正整数使得 \(S_{x+2k} = S_{x+2k+1} = 0\)。
这个结论是充分的，因为这样的 \(f_{l,a+1}\) 确实能形成 \(a+1\) 个 \(0\)。
考察其必要性，即满足我们最小的这个条件。
首先，\(x\) 这个位置一定是 \(0\)。那么你不断往后面加数，第一个数过程中始终是 \(1\) 。
加入偶数个数过后再加一个数才有变成 \(0\) 的潜质，对于任意一个奇数前缀一定只能变成 \(1\)。
那么证毕？
最后还要枚举一个后缀使得这个后缀能被缩成两个数，使得其中之一与最后一个数一样。
显然对于同一个生成序列，在 \(S\) 中越靠前越容易被满足。
写的 \(O(n^3)\) 的。但很好优化，瞪瞪代码就会了。
啊，这题好厉害！我好爱！
P9152 Gauss(3500)
这题不是很有意思，有科技成分，我不喜欢。
首先建笛卡尔树做子树 \(dp\) ，这是平凡的。
然后扫描线处理询问，这也是平凡的。
然后树上撒点分块，对于关键点计算对它的祖先计算贡献系数，然后滚前缀和。
这是科技化的。做完了。不想写，那就不写了。
【UR #2】树上GCD
容斥一下，变成算特定东西的倍数。阈值分治，长剖处理。
#29913. 加减
奇偶性相同的 dp 值之间存在凸性。然后分治闵可夫斯基和合并。
「BZOJ4899」记忆的轮廓
先对错误节点跑一个 dp ，大体上是从当前点开始到进行回档至少用多少步。
然后就可以再以此做一个预处理 \(g_{l,r}\) 表示从存档点 \(l\) 走到 \(r\) 中间不存档的期望步数。
最后再算一个 \(f_{i,j}\) 表示到第 \(i\) 个点，使用 \(j\) 个存档点且当前点存档的最小期望步数。
CF830E Perpetual Motion Machine
纯分讨+手玩，呕吐了。
不写题解了。
[AGC013F] Two Faced Cards
好像是可做题吧，但是好累，不想想了。
先把序列变成前缀和。
然后消除小于 \(-1\) 的位置。
接下来离线处理询问，把最早的 \(-1\) 往右推，就可以查询答案了。
做完了。
【20230324 模拟赛】 行列式
将行列式拆成两个矩阵，一个是全为 \(x\) 的矩阵，另一个是剩下的部分。
原矩阵就是两个加起来。发现第二个矩阵关于对角线对称，类似于图的邻接矩阵。
考虑建图，又因为其保证 \(p_i < i\) ，所以图是一棵树。
类似地第一个矩阵则可以看做完全图的邻接矩阵。
一个经验性的性质是，排列的逆序对奇偶性等于 \(n\) 减去环的数量。
所以我们考虑在图上按环计算。
另一个经验是行列式往往可以通过变换消去大量情况。
我们考虑复现这样的经验，仔细观察发现在我们的选环方案中出现两个 \(x\) 边，则可以把他们合并或拆开，环的数量变化 \(1\) ，贡献权相反，因此抵消。
于是我们得到了只能存在不超过一个 \(x\) 在我们选定的环中这个性质。
简单 \(dp\) 一下就做完了。
CF1809G Prediction
另 \(Mx_i\) 表示前缀最大值。
简单转化得到对于所有 \(i\) 都有 \(|Mx_i - a_{i+1}| > k\)。
然后考虑 \(dp\)。从后往前不断去钦定前缀最大值是多少，依次考虑每个数，考虑他是否成为前缀最大值。
不成为的话可以放在比他大的任意一个数后面。成为的话需要满足条件。
为了满足条件，我们可以从一个前缀最大值直接转移到另一个。具体地，考虑 \(a_i\) 是一个前缀最大值，第一个小于 \(a_i - k\) 的位置是 \(j\) ，这中间的数显然可以放在除了 \(i\) 的之外的任意一个数后面。
然后同时，我们可以让当前的前缀最大值放弃成为前缀最大值，转而插入到比他大的数后面，而让下一个数插在最前面成为前缀最大值，这样一定可以让下一个数满足限制，因为更大的数都能满足，小一点就更可以了。
CF1792F1 Graph Coloring
对于一个图，其不连通则其补图一定联通。
现在考察原问题。
假设原图红色联通块联通，蓝色不连通。则若点集在不同蓝色联通块则一定满足条件。
因此我们只需要让每个蓝色联通块都满足条件。
定义 \(f_i\) 表示 \(i\) 个点的子图，红色联通，蓝色不连通并且满足条件的方案数。
直接枚举 \(1\) 所在蓝色联通块即可转移。
一看就可以分治 NTT ，但是好像有更多细节，要省选了，暂时不深究。
【20230325 模拟赛】 上古遗迹
对每种权值考虑，算出 \(O(n)\) 个掌控区间，表示这个区间的任意一个子区间都可以使用这个权值。
然后把询问离线下来，按左端点排序，跑 cdq 分治，讨论右端点大小，然后李超树维护一下。
【20230325 模拟赛】吞天得手
考虑枚举队伍的战斗力序列。只要保证每次枚举都能输出复杂度就正确。
实现就是 dfs ，记录当前状态的最靠前的结尾位置，然后每次找到最小的转移点。
找到的方法就是对每个值最后出现的位置维护线段树，查就线段树上二分即可。
做完了。
[ARC122E] Increasing LCMs
倒着考虑，每次把一个数放到最后，那么其前面的数的 LCM 是确定的。
因此可以清楚判断当前位置这个数能否填，此时发现没有后效性。
如果有多个数可以填在此处，则瞎填一个都是正确的。因为其他数不会因为填了这个数而在靠前的位置无法填了。
做完了。小清新。
CF757E Bash Plays with Functions
显然，\(f_0(n) = 2^{d(n)}\) ，其中 \(d(n)\) 为 \(n\) 因子种类数。
其次，\(f_{r}(n)\) 是被递推定义的，可以看做向下分配素因子。最后再除以 \(2^r\)。
那相当于是对每个素因子单独考虑。枚举一下这个素因子被分配给了 \(2^r\) 次方中的多少个数。
那就是 \(\binom{2^r}{x} \times \binom{d-1}{x-1}\)，做完了。草，是求和不是求积。
求和的话，那就对于每个数考虑他的贡献乘以其余的方案数，显然每个数等价。
[AGC024E] Sequence Growing Hard
考虑 \(A_i\) 与 \(A_{i+1}\) 之间的关系。
本质上是去插入一个数，这个数一定大于插入后在他后面的数字。
从另一个角度考虑，我们倒着删数。
那么可以不断钦定删除最小的数的时间计算即可。
因为最小的数一定可以把原问题划分为前后两个完全独立的问题，因为最小的数被删除了，那么他后面的数应该在他之前被删除。
所以定义 \(f_{i,j}\) 表示 \(i\) 个数用前 \(j\) 个元素去生成的方案数。
每次枚举最小的数的位置以及删除时间即可转移，是容易优化的。
【集训队作业2018】喂鸽子
一眼 \(\min-\max\) 容斥。
每个鸽子等价。
即，我需要计算 \(f_i\) 表示喂饱 \(i\) 只鸽子中的一只的期望时间。
我们先计算，\(f_{i,j}\) 表示只考虑 \(i\) 只鸽子，喂了他们 \(j\) 次，还没有鸽子吃饱的方案数。
然后把剩下 \(n - i\) 只鸽子拉过来一起考虑。
令 \(p = \frac{n - i}{n}\)。
然后 \(i\) 只鸽子有鸽子被喂饱的最早期望时间实质是：
\[\sum_{j=0}^{i \times (k-1)} f_{i,j} \frac{1}{n^j} \sum_{x=0} \binom{j + x}{x} p^x \]感觉，他类似牛顿二项式定理，但我不记得了，所以先抄一个式子。
\[(x+y)^{-n} = \sum_{d=0} (-1)^d \binom{n - 1 + d}{n - 1} x^dy^{-n-d} \]容易得到：
\[\sum_{j=0}^{i \times (k-1)} f_{i,j} \frac{1}{n^j} \sum_{x=0} (-1)^x \binom{j + 1 + x - 1}{j} (-p)^x 1^{-j-x} \\ \sum_{j=0}^{i \times (k-1)} f_{i,j} \frac{1}{n^j} (1-p)^{-j-1} \]INOH Round 1 狂气
首先 \(a_1 \equiv 1\)，\(a_2\) 等于 \(1\) 操作的个数。
\(a_3\) 等于每一个一操作后面二操作的个数。
那其实本质上就是路径数咯。明明数字个数不多，但他不让我输出，必有蹊跷。
没意思。分治，NTT 卷一下就做完了，太愚蠢了。
INOH Round 1 意外
好厉害。我对 100 个数计算一定数量的点值，重复 \(k\) 遍，发现只要我能保留下 \(100\) 个绝对正确的点值就可以得到结果。绝对众数一定绝对正确。
调一下参数，做完了。
CF1798F Gifts from Grandfather Ahmed
一个定理是，对于任意 \(2n - 1\) 个数，一定能选出 \(n\) 个数使得他们的和是 \(n\) 的倍数。
然后就跑个背包随便做了。
贪玩蓝月
对顶栈，直接背包就做完了，只能说典中典。
哦，合并的时候是一个滑动窗口，得写一个单调队列。
CF1750F Majority
考虑什么样的串是不好的。
那么就存在两个 1 之间有着不可逾越的鸿沟。
那么就一定存在一种划分，使得将原序列划分为 \(2p + 1\) 段，奇数段能变成全 \(1\) ，偶数段两端的 \(1\) 不能合并。一段能变成全 \(1\) ，显然是子问题。那么就可以进行 \(dp\)。
定义 \(g_{i,j}\) 表示将长为 \(i\) 的序列划分为奇数段，最后一段长度为 \(j\) 的方案数。
答案显然就是 \(g_{n,n}\)。这样定义是易于计算和优化的。
还是对子问题和转化的可做性的洞察不够敏锐！
大冬天题
两个奇数的差如果是 \(2\) 的幂次，则互质。
所以一定可以递归构造使得每个数都能找到相差为 \(2\) 的幂次的数。
具体地，每次找到最小的数，在大数区，最大的数与他的差是最小的数与他的差的两倍。
中间一定夹了一个 \(2\) 的幂次。
CF1808E Minibuses on Venus
不会做，来学习代码。讨论 \(k\) 的奇偶性。
如果 \(k\) 为奇数：
容斥。用总的方案减去不合法的。
具体地，对于一个数 \(x\)，我们使用一个 trick ，就是我们把其他数减去一个 \(x\)。
那么所有数都被规约到了一起。那么，我们枚举一个关键数，当和为只有这个关键数满足和的限制且关键数不存在的时候即不合法。我们根据 \(0\) 不出现算出对于每种和的方案数，发现大于 \(0\) 的部分等价，且与等于 \(0\) 的部分方案数绝对值相差为 \(1\)。
那么就可以算了。
唔，对于 \(k\) 为偶数：
不一样的地方在于一个和可以对应两个关键数！
于是对于每一个和，我们计算时把所有数减去较小的那个数。
两个关键数的差值恰好为 \(\frac{k}{2}\)。
然后一样地讨论计算即可。
CF1805F Survival of the Weakest
先看 F1 难点在于存数。道理是存差分数组就好了。
然后最后答案再垒上一下系数。
然后差分数组每一位都不会变大。这是显而易见的。
现在考虑一下满数据范围的情况。
啊呀！实际上只用保留最小的 \(2 \log a\) 个数。
因为假设 \(a_1 + a_2 < a_n\) 则可以删去，否则 \(a_n\) 会在两步之内变成原来的一半，做完了。
CF1814F Communication Towers
考虑将点的限制转化为边的性质。
我想线段树分治，然后我就知道了每个时间点的一号节点的联通块。
但是打上标记是困难的。维护可撤销并查集，然后打懒标记就好了。
CF1797F Li Hua and Path
首先每次加入一个叶子，意味着好对子数不会变少。
其次，每次加入一个点，该点都是最大的，那么能够与其组成好对子的点一定不能是路径最小的点。
然后对子树容斥一下大概就是一个二维偏序。 \(O(n \log^2 n)\) 的复杂度，\(T\) 飞了。
啊啊啊，又是笛卡尔树，建完就做完了。
CF1815D XOR Counting
\(m = 1\) 和 \(m \geq 3\) 的部分是平凡的。
考虑 \(m = 2\) 的部分。事实上，我们每次考虑最低位，然后做一个 dp 就好了。
[北大集训 2021] 基因编辑
随便讨论一下，线段树维护一下就做完了。
[北大集训 2021] 魔塔 OL
在偏序限制下，我需要完成一个贪心的决策。
首先是回血怪，肯定比扣血怪先吃。
先吃消耗血量少的回血怪，再吃多的。
然后是扣血怪，则经推倒得到，按照治疗量从大到小排序吃。
事实上，在此基础上，我可以先排序，然后利用 bitset 求得一个偏序关系。
然后利用这个偏序贡献关系求得答案。而求答案的过程也可以利用分块，块内指数级预处理，然后直接计算。注意要按块处理，否则空间起飞。
标签：Set,frac,春测,sum,然后,times,枚举,考虑,集训 From： https://www.cnblogs.com/Reanap/p/17342449.html