千题计划，始于键盘之下
spdarkle
·
·
个人记录
RT，本文用来存自2023.9.25起自主做题记录。
初三目标：NOIP 一等奖+北大学科营。
EDU155
第二个version rk1289。rating+=12.
CF1879D
给定 a_i，设 f(l,r)=a_l\oplus a_{l+1}\oplus\dots \oplus a_r，求 \sum_{i=1}^n\sum_{j=i}^n(j-i+1)f(i,j)，其中 1\le n\le 3\times 10^5
简单的问题。也不知道pzj是在干嘛(bushi)
首先设 s_i=s_{i-1}\oplus a_i,s_0=0。
然后我们按位统计贡献,将 (i-j+1)s_i\oplus s_{j-1} 拆为 i\times (s_i\oplus s_{j-1})-(j-1)\times(s_i\oplus s_{j-1})
设当前统计到了第 k 位，每一位贡献位 2^k。
统计 b[i]=(a[i]>>k)&1，对于每个数统计贡献就只分四种情况：b_i 的取值和其作为 l-1,r 其中之一的取值。
设 pre_i=pre_{i-1}+b_i,pre_0=0,suf_i=suf_{i+1}+b_{i},suf_{n+1}=0。
然后，分类讨论，取 i 从零到 n：
-
b_i=0$，此时作为 $r$ 的贡献为 $2^k\times i\times pre_i$，作为 $l-1$ 的贡献为 $-2^k\times i\times suf_i
-
code
CF1879E
题意简述：
给定一颗以 1 为根的树，现在来玩一个游戏。这个游戏规则如下：
首先，你需要将边染为 k 种不同的颜色，然后有以下操作：
我们提前选好一个点 x，现在你需要以最小的步数将 x 移动到根节点。(你不会知道 x)。
我们每一次会告诉你当前走到的点，连接它的所有边的每一种颜色的边的个数。
求在确保在最坏情况下仍然能以最少步数移动到根的情况下，所使用颜色最少。
首先，一个直觉的想法是，每一条边按照儿子的 dep 进行染色。这样我们只需要每一次找到给出的边的颜色最小值走就可以了。
那么进一步思考发现，我们必须要保证可以在最坏情况下每次仍然可以找到当前点的父亲节点。
这是染色方案合法的充要条件。
那么我们来思考一个普遍性的情况。
注意到一个性质：若对于每个点，连接父亲的边和连接儿子的边的颜色是不同的。则连接父亲的边的个数必定为一。这是另一个判定的条件。
首先对于叶子节点，也即有唯一边可以走的，我们当然走，然后考虑利用这个性质。
注意到，我们可以给边固定顺序，染色时按照 1\rightarrow2\rightarrow 3\rightarrow 1 的顺序给每层边染色，接着我们每次就只会得到两种颜色的边。且知道这两种边的颜色，这会让我们直接判断出父亲节点的边。
如 (1,2) 颜色存在，就走 1，若是 (2,3)，走 2，若是 (1,3)，走 3。
那么可以得到 k\le 3。
事实上，这样的3的循环染色非常常见。
现在考虑 k=1,k=2 的两种情况。
$k=2$ 是烦恼的。
叶子节点不必多说，我们现在来考虑颜色1和颜色2的数量分别是 $(a,b)$ 的情况。我们现在是进行黑白染色。
首先，$a,b$ 之中必然至少有一个为一，若有且仅有一个，则走为一的边即可。
那么我们真正要处理的是 $(1,1)$。
这时候怎么判断？明显，我们得到这个输入，就必须指定走某个颜色。
而什么情况下当我们得到 $(1,1)$ 选择走 $1$ 都是正确的呢？（选择走 $2$ 由对称性可知等价。）
那么就必然有，这一类点连父亲的边全部都被染成了 $1$。
这一类点，本质上是 $|Son(u)|=1$ 的点的集合。
若想要这些点的都被染为一，则必然有这些点的深度的奇偶性相同。这样我们可以通过选择第一层的颜色确保这些边颜色全部为一。
真的是这样吗？注意到根节点 $1$ 的不同子树无关系，可以对于每一颗子树单独选择起始颜色。那么我们对每一个 $1$ 的子树跑一遍，判断是否合法即可。
[code](https://codeforces.com/contest/1879/submission/225085291)
------------
[CF1879F](https://codeforces.com/contest/1879/problem/F)
**谨防双指针引起复杂度退化**。
> 给定 $n$ 个怪，每个怪有 $h_i$ 条命，每条命有 $a_i$ 格血。
>
> 你可以选择一个正整数 $x$。在每一回合中，你将会对每一个还活着的怪造成 $x$ 点伤害。当一个怪的血条归零后，就会消耗一条命并且满血复活。
>
> 定义一个怪的得分（奇怪为什么不是玩家的得分）为：
>
> - 如果这个怪没有存活到最后一轮，亦或者和其他怪一起在最后一轮死去，得分为零
> - 如果这个怪存活到了最后一轮，得分为有且仅有这个怪存活的回合数。
> 求对于所有的 $x\in\mathbb{Z^+}$，每一个怪的得分的最大值。
这里值域与 $n$ 同级，以下关于时间复杂度的计算，$\max\lbrace a\rbrace$ 均用 $n$ 代替。
首先，容易发现，对于一个确定的 $x$，某怪存活的回合数为 $h_i\left\lceil\frac{a_i}{x}\right\rceil$。则对于 $x\ge \lbrace a\rbrace$，答案不变，故真正可能会对答案产生影响的 $x$ 有且只有 $O(n)$ 个。
这里就足以得到一个 $O(n^2)$ 的解决方案：我们枚举 $x$，计算出相应的回合数，然后选出**最大值和次大值**进行做差，去更新回合数最大的那个数的答案。
考虑优化这一步。
有两个常用的思路：第一个是进行数论分块，得到 $O(n\sqrt n)$ 个不同的得分，然后进行比对。这个比对可以借助各种数据结构，但无论怎么搞，复杂度下界也是 $O(n\sqrt n)$。对于 $1\le t\le 10,1\le n\le 2\times 10^5$，是无论如何也跑不过的。一组估计都够呛。
第二个是倍数法。
结合调和级数的知识我们知道，$\sum_{i=1}^n\frac{n}{i}\approx n\log n$，而又由简单放缩： $1\le\frac{a}{b}\implies \left\lceil\frac{a}{b}\right\rceil\le 2\frac{a}{b}$，可以得到 $O(\sum_{i=1}^{n}\left\lceil\frac{n}{i}\right\rceil)=O(n\log n)$。
故另一个想法是枚举 $x$，将 $a_i$ 排序后分段处理。这个做法下界是 $O(n\log n)$，显然具有更多的操作空间。
我们将原来的每个怪按照 $a$ 从小到大排序。那么我们拆出每一个区间 $[l,r]$，满足 $\forall i\in[l,r],\left\lceil\frac{a_i}{x}\right\rceil$ 相同。
这样的区间最多有 $\left\lceil\frac{\max\lbrace a\rbrace}{x}\right\rceil$ 个，求和一下就是 $O(n\log n)$。
那么设我们对于单次求解一个区间 $[l,r]$ 的最大和次大得分的复杂度为 $t$，则单组数据的总时间复杂度为 $O(tn\log n)$。注意这里是非严格的最大和次大。
而注意到这个得分中，$\left\lceil\frac{a_i}{x}\right\rceil$ 是确定的。那么问题就化为在尽可能少地时间内，处理出区间 $[l,r]$ 中 $h$ 的最大值和次大值。
这个问题太简单了，线段树之类的随便做好吧。但注意到，除了 ST 表，没有一个算法可以做到 $O(1)$ 地解决问题。
这时候可能有人会说了，ST 表不是只能维护最大值，要满足区间可加性吗？仔细想想，其实是可以办到的。
对于 ST 表的每一个元素所代表区间 $[l,r]$，我们存下其最大值和次大值的下标。当我们在查询的时候，可能出现两区间重叠的情况，此时我们特判一下最大值是否取到同一个数即可。
```cpp
struct node{
int id1,id2;
node operator+(const node b){
node c;
if(h[id1]>h[b.id1])c.id1=id1;
else c.id1=b.id1;
if(id1==b.id1){
if(h[id2]>h[b.id2])c.id2=id2;
else c.id2=b.id2;
}
else {
if(c.id1==id1){
if(h[b.id1]>h[id2])c.id2=b.id1;
else c.id2=id2;
}
else {
if(h[id1]>h[b.id2])c.id2=id1;
else c.id2=b.id2;
}
}
return c;
}
}f[N][22];
```
然后，可能在实现上还有问题，如何快速地处理出每个 $[l,r]$ 呢？我的第一反应是双指针，然后没有发现双指针的复杂度已经爆表成 $O(n)$，程序时间复杂度直接退化为 $O(n^2)$。
第二个想法是二分查找，但这样的复杂度仍然会乘上一个 $\log n$。
然，我们可以预处理出每一个值 $i$，大于等于它的第一个 $a$ 值的下标，然后直接查询即可。
这个预处理系简单递推，这里不多说。但需要注意预处理需要处理到 $399998$。因为这是可以取到的最大的 $\left\lceil\frac{a_i}{x}\right\rceil x$。
最后你就切掉了这个题。嗯不对？为什么超时了？
注意到**会读入约 $4\times 10^6$ 个数，输出 $2\times 10^6$ 个数**，老老实实写快读吧。
[巨慢代码](https://codeforces.com/contest/1879/submission/225758992)
------------
[CF1882E1](https://codeforces.com/contest/1882/problem/E1)
赛时除unr无人过E2，85人过E1，过于可怕。
~~为什么我瞎猜的E1结论是对的啊，为什么我当时没有打完啊，为什么我当时打了但是打错了就觉得结论是错的啊！！！！！~~
翻译：给定排列 $a_1\sim a_n,b_1\sim b_m,1\le n,m\le 2500$。
你每次可以进行一个操作，选择正整数 $i,j$，将 $a_1\sim a_{i-1}$ 与 $a_{i+1}\sim a_n$ 整体交换，同时对 $b$ 是相同操作。
不需要保证 $i,j$ 两边不为空。
求一个在10000次内将两个排列都有序的方案。
如果无解，报告-1.
首先可以手玩一下，容易发现：
我们可以在3次操作内交换任意两个数。
那么我们就可以在 $3len$ 次操作内，将一个长为 $len$ 的排列排序。
接着以上想法不难实现，关键在于如何同时取到解。
设按照这个做法，得出解的次数为 $c_1,c_2$。
若 $(c_2-c_1)\bmod 2=0$，此时显然选择较小的那个，不断交替对 $1,len$ 进行操作即可。
若 $(c_2-c_1)\bmod 2=1$，此时注意到，对于一个有序的数组，若对第一个位置执行操作，等价于让数组做循环左移。那么连续进行 $len$ 次，也同样可以得到相同数组。
所以，若 $n,m$ 中存在奇数，可以选择连续进行 $len$ 次，然后化为上面一种情况。这时候最大方案数仍然为 $4\max(n,m)\le 10000$。
那如果不存在呢？无解吗？
**赛上没有想到如何证明无解**。但赛下可以证明了。
注意到此时根据两个长度均为偶数，$c_1,c_2$ 奇偶性不同，可以得到 $c_1+c_2$ 为奇数。
而注意到，我们每次进行一个操作，若长度为偶数，则逆序对的奇偶性会发生变化，证明可以考虑分类讨论（左边右边一奇一偶）。
对于操作位置 $i$，与它相关的逆序对变化量为 $n-1-\Delta$，$n-1$ 为奇数，故 $\Delta$ 与 $n-1-\Delta$ 奇偶性是不同的。而两边的各自逆序对从奇到奇，从偶到偶，奇偶性不变。
从而我们可以得到，**对于长度为偶数的序列，每一次操作，会引起逆序对数奇偶性的变化**。
此时我们倒着来，当二者逆序对数都减为0后，对其再次变成零必然会经过偶数次操作，这样并不能改变操作次数的奇偶性。
由上可知证毕。
------------
[CF1882E2](https://codeforces.com/contest/1882/problem/E2)
**阅读本题解前，请知晓简单版本的解决方案**。
现在来看困难版本，发现要求最小化操作次数。
这题简直是人类智慧题。
首先我们来看几个简化版本的问题：
版本一
给你一个排列 $p_1,p_2\dots p_n$，每一次可以从中选出两个数进行交换，求最小地使得 $\forall i\in[1,n],p_i=i$ 的操作次数。
这是一个经典的问题，我们连有向边 $(p_i,i)$，这样我们会得到一张有向图，**满足每个点的入度为一，出度也为一**。
那么，这一张有向图必然是**由若干个简单环组成**的。为什么？我们可以通过反证法假设存在非简单环和不存在简单环，都可以简单地得到这个结论。
然后，我们考虑每一次操作相当于什么。类似这一道人类智慧题 [CF1863G](https://codeforces.com/problemset/problem/1863/G)。显然每一次操作至少使得一个数归位，这等价于将某个点变为自环，然后这个点在环上的前后两个点合并。
那么对于一个长为 $len$ 的环，可以在 $len-1$ 次操作中归位，故总方案数是 $n-cnt$，其中 $cnt$ 是环的个数。注意自环也需要计算在内。
版本二
给你一个 $0\sim n$ 排列 $p_0,p_2\dots p_n$，每一次可以从中选出一个数与零进行交换，求最小地使得 $\forall i\in[1,n],p_i=i$ 的操作次数。满足 $p_0=0$。
类比上一个问题，我们将这个问题的图建立出来。对于每一个长为 $len$ 的环，它的操作次数如何呢？
首先，如果这个环本身已经包含了零，则经过 $len-1$ 次即可将其归位。如果不包含零，则需要先将零换过来，把整个环都变为自环之后又将这个零给换回去（其实在最初交换的时候等价于把零插到这个环里，所以最后一步可以在跳完环后自动跳回零位置），注意这里换回去等价于把最后一个数归位，所以需要用 $len+1$ 次。此时零回到自己原来的环去。当然这肯定是个自环。
版本三
给定一个环，其 $0\sim n$ 位分别为 $0,p_1,\dots p_n$，每一次可以将零与环上任何一个节点交换，求使得该环从零开始顺时针形成 $1,2\dots n$ 的最小操作次数。
注意到这个问题本质上与上一个问题等价，为了将其转化为序列，我们枚举最终的序列形态 $(0,1,\dots n),(n,0,1\dots)\dots$ 取最小值即可。
版本四
即当前我们需要解决的问题。
注意到一个绝妙的想法：
我们将序列添加一个第零号位置，值为零。将这个序列看作一个环。
我们知道，对于一个形如 $[AxB]$ 的 $x$，操作后会变成 $[BxA]$。
当我们**给开头添加零**，也即零始终位于序列的开头位置，不受操作影响，并且破环为链之后。变成了 $[0AxB]\implies [0BxA]$。
这体现到环上，相当于 $[0AxB0AxB\dots]\implies [0BxA0BxA\dots]$。观察容易发现，这其实等价于在环上给 $0,x$ 换了一个位置！
那么，若只看一个序列，则这个问题等价于版本三的问题。
进而，我们对于所得答案进行奇偶分组，每一组保留最小解，对两个序列。
然后，判断无解。
最后从奇数和偶数情况中取较优者作为答案即可。
注意特判无需操作的情况。
实现难度不大，留给读者思考。
[code](https://codeforces.com/contest/1882/submission/225577977)
------------
[SCOI2013 数数](https://www.luogu.com.cn/problem/P3281)
按照一般的套路，我们将答案转化为 $sum_r-sum_{l-1}$ 的形式。
考虑按照一般地数位DP计算答案。以下的位数从第 $0$ 位开始。
设 $f(i,j,k)$ 为前 $i$ 位，是否有最高位限制，是否有前导零的答案。
如何转移？注意到我们从 $i-1$ 推到 $i$ 需要计算第 $i$ 位的贡献。其余贡献可以直接加上。
设我们第 $i$ 位填 $k$，需要哪些信息呢？
注意到对于已经填好的 $0\sim i-1$ 位的每一个以 $i$ 位为右端点的子段，有贡献之和为 $k(1+b+b^2\dots b^{i})$，可以预处理 $p_i=b^i+p_{i-1}$，得到贡献为 $kp_i$。
然后对于以 $i$ 为右端点的子段的其他点的贡献，可以由以 $i-1$ 为右端点的子段得到。这里维护为 $w(i,j,k)$。
我们需要计算当前的数的个数 $c(i,j,k)$，以计算第 $i$ 位能产生多少个 $kp_i$。
综上，我们需要维护 $f(i,j,k),w(i,j,k),c(i,j,k)$。
而具体的转移方程，不难得出：
$$
\begin{aligned}
f(i,j,k)&=\sum_{x=0}^{up}f(i-1,q_1,q_2)+w(i-1,q_1,q_2)+c(i-1,q_1,q_2)xp_i\\
w(i,j,k)&=\sum_{x=0}^{up}w(i-1,q_1,q_2)+c(i-1,q_1,q_2)xp_i\\
c(i,j,k)&=\sum_{x=0}^{up}c(i-1,q_1,q_2)
\end{aligned}
$$
其中 $q_1,q_2$ 是计算得出的新状态。
注意当我们填 $0$ 且填的是前导零的时候，$c,w$ 不参与转移。
这时候，我们就可以得到五十分代码。
为什么会五十分呢？注意到转移的复杂度是 $O(B)$ 的。
这导致复杂度变成了 $O(B(N+M))$，会炸。
但观察转移方程，可以看出当填的 $x\neq up,x\neq 0$ 时，$q_1,q_2$ 是相同的，可以使用简单的加法原理进行合并。
注意 $up=0$ 的情况。
这样我们就成功把转移复杂度降到了 $O(1)$，成功 $O(N+M)$ 地解决了该问题。
------------
[CQOI2008传感器网络](https://www.luogu.com.cn/problem/P5786)
挺不错的问题。
一句话题意：给定一张有向无环图，要从中选出一棵有根树，树根为 $n$，使得**除树根之外**所有节点的儿子数中最大的最小。
$1\le n\le 50$。
可以看到最大的最小，显然可以二分答案。设二分值为 $k$。
问题化为在这张 DAG 里找出满足条件的一棵树。
我们运用“元认知”的思想（~~bushi~~），跳到一个高度去审视这个问题。
其实它**本质是一个匹配**，也即对于每一个节点，选出不超过 $k$ 条匹配边，使得构成一棵树。
但，相较于传统的二分图匹配，它又**没有左右部图的限制**，有且只**有父亲与儿子的关系**。
这时候，不难想到最小路径覆盖问题的解法。
注意到我们的匹配是相对独立的一个匹配，一个节点最多一个父亲，一个父亲最多 $k$ 个儿子。
那么我们就可以考虑**扩展域**的思想。将原图的点拆为儿子域与父亲域。
问题得以转化为每个点的儿子域都需要找到一个父亲域的点匹配，同时一个父亲域的点不得与超过 $k$ 个儿子域的点匹配。
这就是一个经典的网络流模型了。
我们将点拆为 $i,i+n$ 两部分，将源点与 $i$ 连边，容量为一，将 $i+n$ 与汇点连边，容量为 $k$，将原图中的 $(u,v)$ 变为 $v,u+n$，也即儿子向父亲连容量为一的边。
最后判断是否满流即可。
细节：注意到根节点不受限制，我们将其单独处理，只向汇点连容量为正无穷的边即可。
那么这一步判定答案做到了，怎么输出方案呢？
显然我们可以 $O(n^2)$ 枚举 $i,fa_i$，然后强行拆掉 $(i,fa_i)$ 这条边进行最大流判断满流。
这一步可以进行分治加速，为什么？如果我们将其所有可能可行的 $fa_i$，也即原图中点的入边全部拎出来，连边判断，是可以一次性做到判断答案是否在一个区间内的。则我们也可以使用二分 $mid$，然后按编号小到大保留前 $mid$ 个可能可行的 $fa_i$ 查找可行解。
不过没必要了，枚举的复杂度已经正确了。
[code](https://www.luogu.com.cn/paste/l1xvwm9t)
---------------------------------------------------------
[CF1788F](https://codeforces.com/problemset/problem/1788/F)
>给定一棵 $n$ 个节点的树, 编号为 $1\sim n$ , 我们需要给每条边赋一个整数值 $a_i$ , $0\leqslant a_i < 2^{30}$ .
>
>现在有 $q$ 条限制, 每条限制形如 $u,v,x$ , 表示点 $u$ 到点 $v$ 的树上最短路径权值为 $x$ , 路径权值定义为边的异或和.
>
>求是否有解, 如果有解, 需最小化 $a_1\oplus a_2 \oplus \dots \oplus a_{n-1}$ ,并输出 $a_1,a_2,\dots,a_{n-1}$ .
首先，我们将求 $a$ 转化为求 $dis$ 表示在以一为根的情况下根到该点的边的异或和。
那么限制条件 $(u,v,x)$ 本意也即 $dis_v\oplus dis_u=x$。
抽离出来，建虚图，边 $(u,v,x)$。
对于虚图的每个连通块，进行深度优先遍历。
显然如果连通块是一棵树，必然满足条件，如果不是一棵树，则必然所有的环都是零环。
故我们先假定这个连通块的起始位置 $dis$ 为零，以后判断合法性。
跑一遍，走到重复的 $v$ 就判断是否满足 $dis_u\oplus w=dis_v$，不满足直接报告无解。
否则，我们再考虑构造出最小的 $a_1\oplus\dots\oplus a_{n-1}$ 的方案。
因为 $a_i=dis_{v_i}\oplus dis_{u_i}$，故带入 $a_1\oplus\dots \oplus a_{n-1}$ 可以发现每一个 $dis_x$ 被带入了 $deg_x$ 次，得到上式实际等价于求所有度数为奇数的节点的 $dis$ 的异或和。
这好办了，把这些节点打标记，然后拆位。
对于每个连通块，我们可以借用假借起始点为0的 $dis$ 值。
然后对于每一个连通块都可以处理出二元组 $(a,b)$ 表示令起始点这一位为一或零可以得到的被标记节点的一的个数。
问题化为尽可能地从每一个二元组中选出一个数，使得数的和为偶数。
这是简单的问题。我们将所有二元组的 $a$ 求和，若和为奇数，则判断是否存在一个 $b$，使得减去对应的 $a$ 加上这个 $b$ 之后是否会变成偶数。
如果存在，将对应连通块里的 $dis$ 都异或上这一位即可。
这可以在遍历连通块的时候记录下来。
[code](https://codeforces.com/problemset/submission/1788/225772878)
-------
[CF1797F](https://codeforces.com/problemset/problem/1797/F)
学到了一个奇奇怪怪的东西，**[点权多叉重构树](https://www.luogu.com.cn/blog/507718/kruskal-zhong-gou-shu)**。CHN的题果然不一般。
>刚开始给定一个 $n$ 个点的树。
>
>对于一棵树上，如果有两个点 $u<v$ 满足下面两个条件**恰有一个成立**，那么 $(u,v)$ 就是个好对子。
>
>1. $u$ 是 $u\to v$ 路径上**编号**最小的点
>2. $v$ 是 $u\to v$ 路径上**编号**最大的点
>
>有 $m$ 个修改，给出一个数 $x<n+i$，第 $i$ 次修改加入一个编号为 $n+i$ 的点，以 $x$ 点为父亲。
>
>输出共 $m+1$ 行，输出刚开始和每次修改后好对子的个数。
意义不大的问题。
运用“元认知”的思想，跳到一个高度去审视该问题。
设满足条件一的点对集合为 $A$，满足条件二的点对集合为 $B$，则我们所求即为： $|A\cup B|-|A\cap B|$。但在这个问题中，求解 $A\cup B$ 是困难的，故由容斥原理，可以得到 $|A\cup B|=|A|+|B|-|A\cap B|$。带入即得所求为 $|A|+|B|-2|A\cap B|$。
那么，如何求出 $A,B,A\cap B$ 呢？
令 $w_i=i$，则此题出。
我们建立两颗多叉重构树。一颗大根堆，一颗小根堆。满足点 $u$ 到其子树的路径，$u$ 的点权都是最大/小的。
那么 $|A|=\sum_{u=1}^n\sum_{v\in Son_1(u)}siz_{1,u},|B|=\sum_{u=1}^n\sum_{v\in Son_2(u)}siz_{2,v}$。
而 $A\cap B$，本质上是求点对 $(u,v)$，满足在小根堆中 $v$ 是 $u$ 的祖先，在大根堆中 $u$ 是 $v$ 的祖先。
这是一个简单的问题，我们统计出第一棵树的时间戳，得到每个点的子树区间，然后就变成了二维数点，用树状数组维护即可。
[code](https://codeforces.com/contest/1797/submission/225872561)
------
[CF1806F1](https://www.luogu.com.cn/problem/CF1806F1)
人间智慧，2900*不是盖的。
>给定 $n, m$ 和一个长度为 $n$ 的序列 $\{a_i\} (a_i\leq m\le 10^6)$。
>
>定义一次对一个长度为 $m$ 的序列的操作为，选择序列中两个下标 $1\leq i < j \leq m$，删去 $a_i$ 与 $a_j$，然后在序列末端加入 $\gcd(a_i, a_j)$。
>
>给定 $k$，求对序列 $\{a_i\}$ 执行 $k$ 次操作后得到序列中的数的和的最大值。
$1\le n,m\le 10^6$，对于困难版本，$1\le m\le 9\times 10^{18}$。
此题简直比CF1882E2还要妙。
**反过来考虑**，设最终的长为 $n-k$ 的序列为 $\lbrace b_i\rbrace$，设对于每个 $b_i$，是由原序列中的某些元素组成的数字集合 $S_i$ 的 $\gcd$。
则显然有 $|S_i|\ge 1,\sum |S_i|=n$。
我们考虑对于两个 $S_1,S_2$ 满足 $|S_1|,|S_2|\ge 2$，对应数为 $b_1,b_2$，不妨设 $b_1\ge b_2$。
那么他们所用的操作次数为 $|S_1|+|S_2|-2$。
大胆猜想，是否可以通过调整，使得 $b_1+b_2$ 更大。
这是**神奇的结论**：我们取出 $S_1$ 中最大的数字 $x$，将其独立出来，然后将 $S_1,S_2$ 合并，得到新的值 $x,y$。
对于整个序列和而言，$\Delta=x+y-b_1-b_2$。
> 引理：对于 $x,y\in\mathbb{Z^+},x>y\implies \gcd(x,y)\le \frac{x}{2}$。证明是简单的，因为 $x>y$，所以 $\gcd(x,y)\le y<x$，故 $x$ 最大的约数不会超过 $\frac{x}{2}$。
进而可以得到若 $x\neq b_1$，则 $\Delta\ge 2b_1-b_1-b_2+y\ge y>0$。
由此我们可以得到，在最优策略里，有且仅有一个 $|S|>1$。
故而，可以考虑得到这个 $S$，注意到我们可以枚举 $\gcd(S)$，进而可以得到合法的 $a$ 的集合。
但此时有一个问题：多次出现的 $a$ 怎么办？
显然最优的，多次出现的 $a$ 让他先自我消除。所以我们可以记录所有出现次数大于 $1$ 次的数的集合为 $s$，然后对其排序做前缀和（显然越小越优）。
然后暴力枚举当前 $\gcd$ 下的各个数从小到大取，同时记录 $s$ 的贡献。
[Submission](https://codeforces.com/contest/1806/submission/225892682)
Hard version 超出了能力范围。
------
[Codeforces Round 901 (Div. 1) A-D](https://codeforces.com/contest/1874)
[CF1874A](https://codeforces.com/problemset/problem/1875/D)
> 给定长为 $n$ 的数组 $a$，进行 $n$ 次操作：
>
> 1. 选择存在的 $a$ 中的某个元素，并将其删去
> 2. 将答案累加上当前 $a$ 的 $mex$。
>
> 求答案的最小值。
简单问题，显然贪心地删元素，且删元素的顺序必然是递减的，相同值必然一次性删除完成。
那么设 $cnt_i$ 为 $a$ 中 $i$ 的出现次数。显然对于 $i\ge n$ 的数无需在意。
然后求出最初的 $mex$ 记作 $res$，设 $f_{i}$ 为第一个全部删完的数为 $i$ 的最小答案，显然可以得到：
$$f_{i}=\min_{j<i}\lbrace f_j-(cnt_j-1)res+cnt_j\times i\rbrace+(cnt_i-1)res$$
可以用斜率优化做到 $O(n)$。不过暴力 $n^2$ 足以。
[Submission](https://codeforces.com/contest/1875/submission/226001927)
-------
[CF1874C](https://www.luogu.com.cn/problem/CF1874C)
> 给定一张DAG，每一条边由小编号指向大编号，有两个人要一起从 $1$ 走到 $n$，每次两个人都会选一条边，如果一致，走到该边终点，否则断掉这两条边重新选。（没有边就爆掉了）
>
> 第一个人会等概率地选择下一条边，你需要最优化第二个人的选择，求出到达 $n$ 的最大概率
问题关键：**注意到**选择边的顺序**只与**该边通往的终点的概率的**相对大小有关**
问题本质：复杂的概率限制问题。在于抽离概率模型进行统计计算。
一个很显然的性质：越往后选被选到的概率必定不增。
很感性的证明：在还剩 $k$ 个点的时候一次选中概率是 $\frac{1}{k}$，而选不中再次选中的概率不会比 $\frac{1}{k-2}\times \frac{k-2}{k}=\frac{1}{k}$ 大。
那么如果知道相对一号，二号……位置的概率，则简单倒序DP即可求解。
设 $g_{i,j}$ 为有 $i$ 个点时，第 $j$ 号位被选中的概率。
边界：$g_{i,1}=\frac{1}{i}
转移：g_{i,j}=\frac{j-2}{i}g_{i-2,j-2}+\frac{i-j}{i}g_{i-2,j-1}，其含义为第一个人随机选到了比 j 优/劣的边导致的优先级变化。每一次第二个人优先选择最优的一号边。
综上，总复杂度 $O(n^2+m\log n)$。
[Submission](https://codeforces.com/contest/1874/submission/226451520)
------------
[CF1874D](https://www.luogu.com.cn/problem/CF1874D)
>通过一条路的时间为 $1$，有一条 $0\to n$ 的链，要求指定边权，使得期望时间最短，且 $\sum w\le m
当走到节点 x 时，有 \frac{w_x}{w_x+w_{x+1}} 走到 x+1，否则退回 x-1。
1\le n,m\le 3000
Submission
状压专题集训
CF1839E
交互，给出序列 a，你需要选择先手或后手，并且赢得这个游戏。
在每一步中，先手先选择 i,(a_i>0)，后手再选择 j,(a_j>0,i\neq j)，接着将二者减去 \min(a_i,a_j)。
谁不能操作时，对手就赢了。
1\le n,a_i\le 300
结论性构造问题。操作本质是删去 a_i,a_j，插入 |a_i-a_j|。
手完一下发现后手很难赢，再研究一下可以得到后手必胜条件是 a 可以分为两个和相等的集合。
证明：
只需证明两个条件：
- 若不能分为两个和相等的集合，则进行一次操作后，仍然划分成功。
- 若能分为两个和相等的集合，则后手必然有方案使得进行操作后仍然可以划分成功。
先证明前者，只需证明不存在两个集合的和 S_1,S_2（不包含 i,j），使得 |S_1|-|S_2|=|a_i-a_j|。
显然，如果存在，则将 i,j 分别加入两个不同的集合可以达到同样效果。故可知不存在这种划分方案。
再证明后者：
显然后手选取另一集合的元素是必然的。那么设两个集合 V_1,V_2，和为 S，那么 S'_1=S-a_i,S'_2=S-a_j,|S'_1-S'_2|=|a_i-a_j|，这时候将剩下的放进去即可。
所以我们可以使用 bitset 和 <set> 分别维护背包和操作，复杂度 O(\frac{NV}{w}+n\log n)
CF1730E
给定长为 n 的数组 a，求有多少个区间，满足最小值整除最大值。
1\le n\le 5\times 10^5,1\le a_i\le 10^6
*2700的题，套路中的创新。
结合区间最值统计和整除统计的常见套路，不难得出以下两个想法：
- 枚举最小值，倍数法处理倍数
- 枚举最大值，提前预处理因数
然后结合最值的常见思路：
- 最值分治
- 根号分治
- 数据结构维护合法点位
- 建立最小/大值区间树——单调栈/分治+ST
不过此题没那么套路，倒是新颖的。
考虑枚举最大值，枚举因数，这样的复杂度是 O(n\log V) 打底。然后此时我们知道的条件有：
- 当前最大值位置 pos，最大值 a_{pos}。
- 当前最小值值为 val。
考虑更多的可预处理条件。
显然，我们可以使用单调栈/ST表+二分得到 ln_x,lx_x,rx_x,rn_x。得到其最大最小影响区间。
其次，我们可以使用 vector 得到值为 x 的数每一次的出现位置。
回代条件，我们可以根据 a_{pos}，求出所有满足条件的 val 的位置。
考虑优化复杂度。
注意到只需要区间里出现至少一个 val 即可，多个 val 可以忽略。
思维难点：分别求出左右两个与 pos 最近的 val，下标记作 L,R
进而，可以直接运用 ln_L,rn_R，与求得所有 val 等效。
这种考虑同种性质元素的相似性与差异性，进而以点带面达到等效的方法是相当有效的。
根据 pos,L,R 三个位置的左右端点，可以得到合法区间的范围，简单讨论一下答案取法即可。
时间复杂度瓶颈在于求得 L,R，事实上，若我们自小到大枚举 pos，则 L,R 的位置是递增的。
只需要记录当前 val 出现过几次，则可以 O(1) 求得 L,R。
至此，我们 O(V\log V+ntR+nt) 解决了该问题。R 为最大因数个数（R\le 240）。
Submission
区间统计套路++。
跳棋
给出一张 1\times n 的棋盘，上面有一些棋子，每次操作分为两种：
-
-
i,i-1$ 上有棋子，$i-2$ 上没有棋子，可以将 $i$ 上的棋子移动到 $i-2
给定每个位置是否有棋子或者棋子可有可无。你需要求出每一种可能的初始情况可以达到的最终局面的个数。
输出它们的和。（注意不同的初始情况和相同的最终局面也是要分开算的）。
非常有意思的问题。
DP应该是没跑了，关键在于状态设计。
什么样的状态可以根据特征将其归为一类，这是设计DP的重要思考方向
这就是本题很妙的地方了：
这是有意思的，我们用后者来思考，容易发现，$0$ 一次最多跳过 $2$ 个一，则经过若干次跳跃，同样只能跳过偶数个一。
这说明了零是跳不过一段连续的，长为奇数的一的。
进而可以得到两个零之间的奇数段一的个数一定。
> 就像 $00111010011$，你会发现无论怎么搞两个零相对之间奇数段一的个数一定。
那么，**一个状态所能到达的最终局面，就等价于这个状态的每两个0之间相对奇数段一个数一定**。
这就可以刻画状态了，可以设 $f_{i,j,k,0/1}$ 表示前 $i$ 个位置，有 $j$ 个 $11$，有 $k$ 个零，且当前最后一位是否是一个奇数一段的末尾。
这个方法也是很妙的，我们**只需要每相邻两个零之间的奇数段个数一定，亦或者每个零到开头的奇数段个数一定**，就可以确定该状态了。那么这也说明了有 $i-2j-k$ 个奇数段在位置 $i$ 之前。
转移是容易的，显然有：
1. $s_i=0
f_{i,j,k,0}=f_{i-1,j,k-1,0}+f_{i-1,j,k-1,1}
-
s_i=1
f_{i,j,k,1}=f_{i-1,j,k,0}
f_{i,j,k,0}=f_{i-1,j-1,k,1}
-
s_i=?
把前面两个转移加起来即可。
实现采用刷表法应该更为轻松。
然后，我们得到了同类的状态可以达到的最终局面的个数，我们的问题变为了确定该状态有多少个。
枚举 f_{n,j,k}。
首先，奇数一的位置是被 11 确定的，我们只需要考虑 11 和 0 的位置排布即可。
不妨将 11 视作 .，将 0 视作 \#，那么问题变成了从 j+k 个位置中选出 j 个作为 . 的方案数，显然是 j+k\choose k
那么答案即为 \sum (f_{n,j,k,0}+f_{n,j,k,1}){j+k\choose k}
不管你感觉怎么样。我是感觉相当妙的。
Codeforces Round 902 Div.1 A-D，题号1876
CF1886E
公司有 n 个程序员，m 个项目，每个程序有能力 a_i，每个项目有难度 b_i。
现在你要对于每个项目选择一队程序猿进行解决。
要求如下：
- 设选择了 k 个程序员，则必须满足 a_j\ge \frac{b_i}{k}
- 每个程序员只能最多负责一个项目，可以吃空饷
求出一种可能的分配方案，可能无解。
首先，由于限制条件一本质上只与最小值相关，所以先自大到小排序。
那么在最优方案中，所有用的程序员必然是 a 的某个前缀。
如果不是，那么把后面的用前面的替换显然更优。
进一步思考，所有用的程序员应该和每一个 b_i 是一段一段对应的。
如果不是，那么把交错的调整为不交错的段答案显然不会变劣。
这启发我们处理出 g_{i,j} 表示第 i 个任务，从第 j 个程序员开始取的最近的解的位置。这显然具备单调性，g_{i,j}\le g_{i,j+1}，可以用双指针维护。
然后发现我们实际是求一种排列的顺序，使得对应的 g 排列后最后一个位置不超过 n。这里贪心地从前往后依次取显然是正确的。
如果暴力，显然 O(m!m)，不可承受。优化最优排列顺序的常用法是状压DP，考虑设 f_{S} 为当前已经处理了 S 的任务，用到的程序猿的个数最小值。也即用掉了 [1,f_S] 的程序员。
暴力枚举位置借助 g 进行转移即可，输出方案可以记录转移的前一个状态，一个个处理完统一输出。
CSP-S2023游记
FJOI2015-火星商店问题
一句话题意：
给定 a_1\sim a_n，以及 b_1\sim b_{tim},pos_1\sim pos_{tim}，保证 pos 在 [1,n] 之内且不重复，给出若干个形如 [l,r,x,d,t] 的询问，求
\max_{l\le i\le r,j\in [t-d+1,t]\and l\le pos_j\le r}\lbrace x\oplus a_i,x\oplus b_j\rbrace
保证 1\le n,a_i,b_i\le 10^5
发现对于式子的前半部分 x\oplus a_i 可以通过离线排序后双指针扫用 trie 记录树内最大 id 进行查询。复杂度 O(n\log n)。
我们考虑处理式子的右半部分。
发现这是一个对于时间轴和区间范围的二维限制问题。一般的想法是KD-Tree+Trie的暴力 O(n\sqrt n\log n)，不仅卡时间而且我不会。
那么考虑各种简化多维度的算法。
- CDQ分治？发现对于 [t-d+1,t] 这种区间很难办。
- 那么划分这种有效时间段，可以考虑使用线段树分治
将每个询问区间 [t-d+1,t] 拆为线段树上的 O(\log n) 个区间。如何处理答案？
这样我们就把问题转化为了对于 a 处理的样子。将线段树上节点存储的区间以及其管辖的时间范围的 b,pos 二者进行排序，双指针扫并且统计即可。
注意必须手动循环清空Trie树。
这样每个位置最多被插入 O(\log n) 次，每个询问最多被割为 O(\log n) 个，时间复杂度 O(n\log^2 n)。
code
CF348D
初次感受 LGV引理 。（不会线代）
有一张 n\times m 的地图，有些位置有障碍物，有两只龟从 (1,1)\to (n,m)，任意一个时刻两只龟都会走一步，每一步只能向下或者向右，求两只乌龟在途中不相遇的方案总数。1\le n\le m。
如果没有障碍物，这个问题是容易解决的。
设 a_{i,j} 表示 (i,j) 是可到达的。
按照由易到难的顺序，先考虑一只龟的情况。
- 若没有障碍物，显然为 n+m-2\choose n-1。
- 有障碍物，则可以使用动态规划解决。f_{i,j}=f_{i-1,j}[a_{i-1,j}]+f_{i,j-1}[a_{i,j-1}]
再考虑两只龟，没有重复限制的情况。
考虑带有重复限制的情况。由于交点有很多，必须带有限制性处理。
这种限制，一般可以考虑首尾限制，譬如我们只考虑最后一个交点。
注意到像之前那道跳棋一样，关注相对关系，容易得到 两只龟相遇后，哪只是哪只已经不重要了。
如果我们将路径抽象为经过棋盘中心的一条线，容易发现，不相交的一个必要条件是两线段起止位置不交，也即只能是 (1,2)\to (n-1,m),(2,1)\to (n,m-1)。
否则必然有交。我们先通过朴素DP求出这样的方案数，再考虑容斥掉非法状态。像之前说的，我们考虑每个点 (x,y) 作为路径最终交点的方案数。
那么 可以考虑将两只龟 swap 一下，则两只龟的起始点变为了 (1,2)\to (n,m-1),(2,1)\to (n-1,m)。
考虑使用朴素DP求出函数 f(sx,sy,tx,ty) 为 (sx,sy)\to(tx,ty) 的方案数。有 Ans=f(1,2,n-1,m)\times f(2,1,n,m-1)-f(1,2,n,m-1)\times f(2,1,n-1,m)。
这种将状态取反得到等效结果的思想，与蓝书上证明卡特兰数的方法类似。
CF1065F
题意：给定一颗根为 1 的树，可以选择任意一个节点作为出发点，每次进行如下操作，求可以走到的叶子节点的个数的最大值。
*2500中的弱智题。显然每次跳得越高越好，则可以思考贪心。
考虑到一个什么样的子树对于 u 而言是无效的。显然形如一条长链，满足子树 v 中的距离 u 最近的叶子节点的距离也大于了 k。
那么可以让我们想想一个自底向上的过程。考虑计算从一个叶子出发最多可以到达多少个新的叶子。容易发现这个路径呈现为一个两端性。
注意这里的路径仅仅指在跳跃过程中所到叶子节点的连线。
先往上跳，再往下跳。必然存在最优策略满足这种情况。否则可以通过调整法将一个最优策略调整为这种情况。
那么处理类似于这种路径分两段的问题，考虑枚举中间点。设 h_{u} 为路径经过 u 所能拿到的最多的叶子个数。
为了转移，能否跳到 u，可以维护 f_{u} 为子树 u 内叶子节点到 u 距离的最小值。
这时候我们考虑到向下的一半是可逆转的。这非常优秀，这意味着我们可以维护 g_u 表示只考虑向上跳可以拿到的最多叶子个数。则转移：
g_u=\sum_{v\in Son(u)}g_v[f_v<k],f_{u}=\min_{v\in Son(u)}\lbrace f_v\rbrace+1
考虑到 h 的转移实质：可以选择最多一个 v 满足 f_{v}\ge k 的 v 的 h 进行转移。
则有 h_u=g_u+\max\lbrace (h_{v}-g_{v})[f_{v}<k],h_{v}[f_{v}\ge k]\rbrace。
答案即为 \max h_i。
这揭示了树上路径处理的常见方法之一：分段法。
树上路径处理常见方法：
- 换根DP法，适用于无根树，本质上是枚举路径端点。需要维护换根的树外信息。
- 向上向下法(口胡名字)，适用于有根树（当然无根树就是类换根啦），本质上是枚举LCA，需要维护向上路径和向下路径两个信息。
ABC282G
是一眼的计数DP，很好玩的DP。
定义两个长为 n 的排列 A,B 的相似度 f(A,B)=\sum_{i=1}^{n-1}[(A_i-A_{i+1})(B_i-B_{i+1})>0]，求 \sum_{(A,B)} [f(A,B)=k]。
排列计数问题，一般考虑：
- 考虑相对关系。
- 用极值设计DP——枚举最值位置。
- 固定最后一个位置或固定开头的位置。
设 f_{i,x,y,p} 为长度为 i 的排列，a_i=x,b_i=y 且相似度为 p 的 (A,B) 对个数。
显然有：
\begin{aligned}
f_{i,x,y,p}&=\sum_{t_1<x,t_2<y}f_{i-1,t_1,t_2,p-1}\\
&+\sum_{t_1\ge x,t_2\ge y}f_{i-1,t_1,t_2,p-1}\\
&+\sum_{t_1<x,t_2\ge y}f_{i-1,t_1,t_2,p}\\
&+\sum_{t_1\ge x,t_2<y}f_{i-1,t_1,t_2,p}\\
\end{aligned}
初始：f_{1,1,1,0}=1。
用前缀和在四个方向上计算一个前缀和，即可 O(1) 转移。复杂度 O(n^3k)。
注意滚动数组。
code
ABC236Ex
给定 n,m 和长为 n 的序列 d，求满足以下条件的长为 n 的数列 a 的个数。
-
1\le a_i\le m
-
i\neq j\implies a_i\neq a_j
-
d_i|a_i
1\le n\le 16,m\le 10^{18},d_i\le m
显然容斥，可以猜出是枚举子集的复杂度。不妨设 f_{S} 表示填完 S 内的所有位置，且所有位置不同的方案数。
枚举子集，怎么枚举？考虑到可以让 S 中的某个 x 作为新加入的数，那么就可以先计算上 \lfloor\frac{m}{d_x}\rfloor f_{S-x}。然后我们考虑去掉重复的。
首先考虑枚举 S 中与 x 取到相同数的 y 进行容斥，这样又会造成新的 z 重复...不断进行这个过程，最终我们需要处理一个子集枚举的去重。
设容斥系数为 H(x)，一个集合 T 全部相同的方案数为 G(T)，由题，显然 H(x) 只与集合中元素个数有关。有：
f_{S}=\lfloor\frac{m}{d_x}\rfloor f_{S-x}+\sum_{T\subset S,|T|>1,x\in T}H(T)G(T)f_{S-T}
而 G(T)=\lfloor\frac{m}{lcm(G)}\rfloor，问题化为求 H。
下面开始手玩找规律。
当 |T|=2 的时候，容斥系数显然是 -1，当 |T|=3 的时候，容斥系数是 +2。。。
由此，当 |T|=r 时，被 r-1 大小的子集容斥了 H(r-1) ,共有 r\choose r-1 个这样的子集，但只能容斥一份，所以得消掉，故有 H(r)=-H(r-1)({r\choose r-1}-1)。结合 H(2)=-1 可以推得 H(r)=(-1)^{r-1}(r-1)!。
故可以求解。为了实现方便，这里就取最后一位作为 x。
其实对于它，还有另外的一种理解方式：最初选出一个 y，令 a_x=a_y。然后就容斥掉 f_{S-x-y} 的答案。这会造成可能有 z\in (S-x-y),a_z=a_x=a_y，我们需要再将这种情况减去。紧接着我们选出这个 z，这样 (y,z) 的被选方案变成了两种：第一次选 y，亦或者第一次选 z，第二次再选另一个。在选出一个位置的时候，S-x-y-z 就被减了 2 次。所以加回来。这又导致了选出 (y,z,t) 的情况……逐步地，选出 x 个数的时候就被 x-1 的时候每一个弄掉了 H'(x-1)，容斥系数就是 H'(x)=-xH'(x-1)。注意由于固定位置的存在，H'(r)=H(r+1)。
code