ARC157
A. XXYYX
观察一些性质。注意到 \(\texttt{XY}\) 和 \(\texttt{YX}\) 会产生当且仅当 \(\texttt{X}\) 和 \(\texttt{Y}\) 的连续段交错，因此 \(|b-c|=1\)。然后特判掉 \(a\neq 0,b=0,c=0,d\neq 0\) 的情况，这意味着 \(\texttt{X}\) 和 \(\texttt{Y}\) 不能衔接。
容易证明一定可以构造出方案。具体而言，先在前面用 \(\texttt{XYXYXY}\) 的结构满足 \(b,c\) 的数量，然后在 \(\texttt{Y}\) 后插入适量的 \(\texttt{Y}\)，\(\texttt{X}\) 后插入适量的 \(\texttt{X}\) 即可。
Submission #39180124 - AtCoder Regular Contest 157
B. XYYYX
考虑什么策略是比较优的。首先特判掉全串均为 \(\texttt{X}\) 的情况。注意到如果我们将一个 \(\texttt{Y}\) 填到两个相邻的 \(\texttt{Y}\) 中间答案会增加 \(2\)，填到 \(\texttt{Y}\) 旁边会增加 \(1\)，否则不改变。因此根据贪心我们要先尽量合并相邻连续段，然后再向连续段两侧填，直到填满。第一个过程可以使用堆维护，依据连续段长度排序后贪心选即可，第二次要填到连续段两侧，可以考虑队列维护，出队时向左右增广。
场上实现和上述做法略有不同，所以细节颇多。
Submission #39195896 - AtCoder Regular Contest 157
C. YY Square
比较典的题。看到和的平方首先考虑拆开维护方案数，和与平方的和，直接 dp 转移即可。
如果记录三种状态为 \(h,g,f\)，则转移如下。
其中 \(a=[s(i-1,j)=s(i,j)=\texttt{Y}],b=[s(i,j-1)=s(i,j)=\texttt{Y}]\)。
Submission #39191350 - AtCoder Regular Contest 157
D. YY Garden
注意到每个块要求恰好有两个 \(\texttt{Y}\)，不妨考虑从这一点入手。
首先记录 \(\texttt{Y}\) 的个数为 \(x\)，那么要求 \(x\) 为二的倍数。又因为设置 \(h-1\) 个横向栅栏，\(w-1\) 个纵向栅栏后，总的块数为 \(hw\)，所以 \(h\) 和 \(w\) 必定为 \(x\) 的因数。
首先判掉 \(x\) 为奇数的情况。我们枚举 \(h\)，则 \(w\) 固定且为 \(\dfrac{x}{2h}\)。考虑对于一个这种状态我们如何计算方案。再次观察，由于 \(h\) 和 \(w\) 固定，则若我们只观察横向划分，每一块里恰好要有 \(2w\) 个 \(\texttt{Y}\)。纵向划分同理。下面只讨论横向的情况。注意到此时一个栅栏的位置会被固定在一个全部由 \(\texttt{X}\) 构成的行，否则均会导致这一块中的 \(1\) 的个数不为 \(2w\)。注意到每一个栅栏被固定的范围不交，因此如果确定了 \(h\) 和 \(w\) 以后，方案数的计算可以直接通过乘法原理将每个栅栏可能存在的位置个数相乘得到方案数。然后模拟任意一种划分，二维前缀和判断是否合法。最后将所有合法的 \(h\) 取值所导出的方案数相加即可。
时间复杂度 \(O(HWd(HW))\)，其中 \(d\) 为约数个数函数。常数不大，因此可以通过。
Submission #48193657 - AtCoder Regular Contest 157
E. XXYX Binary Tree
第一个观察是没有 \(\texttt{YY}\) 的这个要求告诉我们如果我们把填 \(\texttt{Y}\) 的点看成白色，那么所有白点构成了一个独立集。但是只有这一点做不了，所以我们考虑其它限制带来的信息。
观察 \(\texttt{YX}\)。由于原树是一个满二叉树，而 \(\texttt{Y}\) 又构成独立集，所以每个填 \(\texttt{Y}\) 的节点都会贡献零个或两个 \(\texttt{YX}\)。因此 \(\texttt{YX}\) 的个数一定是偶数个。这也启示我们一件事，如果填在叶子上的 \(\texttt{Y}\) 的个数固定了，\(\texttt{Y}\) 的总个数也随之确定，即在非叶子上的 \(\texttt{Y}\) 为定值。
再考虑 \(\texttt{XY}\) 的个数带给我们的限制。我们惊讶的发现，由于 \(\texttt{Y}\) 是独立集，所以每一个不在根节点上的 \(\texttt{Y}\) 会恰好贡献一个 \(\texttt{XY}\) 结构，也就是说不在根节点上的 \(\texttt{Y}\) 的个数为定值。结合上文所述，如果我们固定了根节点填什么，我们就可以直接知道我们要在叶子上填多少个 \(\texttt{Y}\)，在非叶子上填多少个 \(\texttt{Y}\)。由于 \(A+B+C=n-1\)，此时 \(\texttt{XX}\) 的限制一定天然满足。
此时正解已经呼之欲出了。考虑一个 dp，设 \(f(i,j,0/1)\) 表示考虑到位置 \(i\)，已经在 \(j\) 个叶子上填了 \(\texttt{Y}\)，当前节点是否填 \(\texttt{Y}\) 能填的最多的 \(\texttt{Y}\) 的个数。转移是容易的，即 \(f(u,i+j,0)\leftarrow \max(f(v,i,0),f(v,i,1))+\max(f(w,j,0),f(w,j,1)),f(u,i+j,1)\leftarrow f(v,i,0)+f(w,j,0)\)。然后我们分根节点是否填 \(\texttt{Y}\) 讨论，方案合法当且仅当对应的根节点上的 dp 值不小于需要填的 \(\texttt{Y}\) 的数量。具体数量参数可以参考代码。
复杂度分析同树形背包。
Submission #48212117 - AtCoder Regular Contest 157
F. XY Ladder LCS
很漂亮的一道题目，我一点不会。
我们首先考虑一些暴力。我们从前向后扫描每一个位置，设 \(f(i,S)\) 表示考虑到位置 \(i\)，从上次匹配位置到当前位置的状态是 \(S\)，所能达到的最长公共子序列的最小字典序。转移时，分当前位置的字符是否选中参与到子序列中讨论。若选中，注意到一个很好的性质是无论我们匹配一个 \(\texttt{X}\) 还是 \(\texttt{Y}\)，我们一定会选择 \(S\) 当中最靠左的一个，因此我们的转移可以 \(O(1)\) 进行。具体而言，我们对每个 \(S\) 所代表的状态预处理出其第一个 \(\texttt{X}\) 所在的位置和 \(\texttt{Y}\) 所在的位置，转移时舍弃匹配位置以前的部分，将其加入答案，然后把剩余的那个字符拼到当前备选状态的末尾，转移到这个状态对应的位置，否则直接拼到备选状态，分到底把哪个拼上去讨论即可。时间复杂度 \(O(n2^n)\)。
接下来有一个惊为天人的结论，答案的下界是 \(\lfloor \dfrac{2n}{3}\rfloor\)。原因是，如果我们把每三个相邻字符分到一组，这一组里的能贡献出的 LCS 长度至少为 \(2\)。可以使用一些分讨或直接暴搜证明，这里不再赘述。因此我们两个匹配的位置距离至多为 \(\lceil \dfrac{n}{3} \rceil\)。所以暴力 dp 第二维的状态为 \(2^{\frac{n}{3}}\)，总时间复杂度为 \(O(n2^{\frac{n}{3}})\)，可以通过此题。
代码实现上，我们需要把字符串映射为数字，官解给了一种很巧妙的方式是把长度为 \(n\) 的字符串看做一个长度为 \(n+1\) 的二进制数，后 \(n\) 位表示把 \(\texttt{X}\) 看成 \(1\)，\(\texttt{Y}\) 看成 \(0\) 后对应的二进制数，第一位代表终止符，始终为 \(1\)，这样映射后取最大值恰好对应了题目中要求的操作，容易 dp 解决。
Submission #48213283 - AtCoder Regular Contest 157
ARC158
A. +3 +5 +7
首先我们直接把三种操作看成 \(-2,0,+2\)，很容易观察到操作不改变奇偶性，因此我们得到了第一个必要条件。同时注意到这三个操作不改变所有数的加和，所以结果一定是平均数，所以也要求平均数是整数。容易证明，在满足上述条件的情况下，我们可以通过每次选取最大值和最小值分别做 \(+2\) 和 \(-2\) 操作构造一组合法解，且这组解一定是最小解，所以做完了。
Submission #48230265 - AtCoder Regular Contest 158
B. Sum-Product Ratio
首先对原式子进行拆分，即拆成 \(\dfrac{1}{x_k}(\dfrac{1}{x_i}+\dfrac{1}{x_j})+\dfrac{1}{x_ix_j}\)，注意到 \(x_i,x_j\) 固定的时候，若存在 \(x_k\) 的三种取值 \(a,b,c\) 满足 \(a<b<c\)，则无论以最大化还是最小化为目的， \(b\) 均不会成为较优解。根据这个引理，我们可以把 \(x_i,x_j,x_k\) 调整为正负的绝对值最大最小的十二个数。因此我们只需要把这十二个数拉出来暴力枚举算出最大值和最小值即可。
Submission #48230863 - AtCoder Regular Contest 158
C. All Pair Digit Sums
很典的一道题。注意到 \(f(a+b)=f(a)+f(b)-9c\)，其中 \(c\) 代表十进制下加法的进位次数。前面的 \(f(a)\) 和 \(f(b)\) 在所有数对里的贡献是容易维护的。所以我们维护一个数和其它数相加的进位总次数即可。再把发生在每一位上的进位拆开考虑，\(a+b\) 在位置 \(k\) 上发生进位的充要条件是 \(a\bmod 10^k+b\bmod 10^k\ge 10^k\)，所以对于每一个数位 \(k\)，我们保留每个数模 \(10^k\) 后的结果后排序双指针即可计算出总的进位次数。时间复杂度 \(O(n\log V)\)，其中 \(V=\max\limits_{i=1}^n A_i\)。
Submission #48233406 - AtCoder Regular Contest 158
D. Equation
最有脑子的一集。
注意到等式两侧次数相差恰好 \(1\) 且均为齐次式。记录左式为 \(F(x,y,z)\)，右为 \(G(x,y,z)\)，则如果我们能够构造出一组 \(x,y,z\) 满足 \(F(x,y,z)=kG(x,y,z)\)，则 \(F(\dfrac{x}{k},\dfrac{y}{k},\dfrac{z}{k})=G(\dfrac{x}{k},\dfrac{y}{k},\dfrac{z}{k})\)。因此随机构造即可。唯一的问题是 \(k\) 不存在实数域的取值或取 \(0\)，即 \(F(x,y,z)=0\) 或 \(G(x,y,z)=0\) 的这种情况。但是官方题解经过一些分讨证明了出现这种情况的概率不大于 \(\dfrac{1}{4}\)，所以复杂度有保证。由于我没看懂证明，所以这里不写了，感兴趣可以自行研究官方题解。
Submission #42839334 - AtCoder Regular Contest 158
E. All Pair Shortest Paths
我草我咋不会这个题。
注意到从一个格子走到另一个横坐标单调变化，因为一但回头就会把拐弯处的两个格子填满导致回不去。也就是说，对于横坐标分别为 \(L\) 和 \(R\) 的两个格子，其最短路必定经过且仅经过横坐标在 \([L,R]\) 中的格子。因此我们有了暴力，枚举两个格子，设 \(f(i,0/1)\) 表示考虑到位置 \(i\)，当前在上方还是下方格子的最短路，转移是容易的。
对于这种问题，一个很自然的解决技巧是分治，假设当前分治中心是 \(mid\)，我们现在要计算所有跨过 \(mid\) 的格子所带来的贡献。根据上述结论，我们容易发现每条这种路径一定会经过 \(mid\)，因此不妨考虑在 \(mid\) 处将路径拼接起来。记 \(disL(i,0/1,0/1)\) 表示从格子 \(i\) 的上半或下半部分，走到 \(mid\) 的上半或下半部分的最短路，要求 \(i\) 在 \(mid\) 的左侧。同理设 \(disR(i,0/1,0/1)\)。考虑一对格子 \((i,j)\)，不妨令 \(i\) 在 \(mid\) 的左边，其对答案的贡献是 \(\min(disL(i,0)+disR(j,0),disL(i,1)+disR(j,1))\)。
考虑拆开最小值讨论，取前者当且仅当 \(disL(i,0)+disR(j,0)<disL(i,1)+disR(j,1)\)，移项有 \(disL(i,0)-disL(i,1)<disR(j,1)-disR(j,0)\)。两侧对 \(i,j\) 独立。因此按照 \(disL(i,0)-disL(i,1)\) 的顺序降序排左部点，\(disR(i,0)-disR(i,1)\) 的顺序升序排右部点，枚举左部点，用前缀和配合双指针即可简单算出该点和所有右部点对答案的贡献。
时间复杂度 \(O(n\log^2 n)\)，瓶颈是排序。
Submission #48241737 - AtCoder Regular Contest 158
F. Random Radix Sort
第一个观察是，如果存在一种合法方案，我们可以确定每一个 \(B_i\) 究竟由哪个 \(A_i\) 转移过来。原因是排序是稳定排序，所以对于相同的数字，其相对顺序不会改变。我们记 \(B_i\) 由 \(A_{pos_i}\) 转移而来。
继续观察性质，注意到如果我们记录操作序列的选择为 \(p_1,p_2,\ldots,p_m\)，则整个操作可以描述为按照 \(p_m\) 为第一关键字，\(p_{m-1}\) 为第二关键字，以此类推进行排序。因而我们发现对于每种操作只有最后一种有用。
接下来考虑 \(B\) 序列对操作序列的限制。我们注意到如果 \(B_i\neq B_{i+1}\)，将所有不等的位划分为 \(S,T\) 两个集合，\(S\) 表示 \(B_i\) 的这一位大于 \(B_{i+1}\) 的，\(T\) 相反。那么这个位置相当于限制如果填了 \(T\) 中的一个数字，则后面必须填一个 \(S\) 中的。且如果原序列中顺序不一样也要至少排一次 \(S\) 中的。我们定义这种限制关系为 \(lim(x,S)\)，表示在填 \(x\) 之前 \(S\) 集合必须被填上一个数字。
然后可以开始状压。令 \(f(S)\) 表示在只考虑最后一次出现的情况下，填完了 \(S\) 中的数的方案数。从后向前考察序列，转移的时候枚举一个数字 \(x\)，检查是否存在一个限制 \(lim(x,T)\) 使得 \(T\cap S=\varnothing\)。因此对每一个 \(x\)，对 \(lim(x,T)\) 做高维前缀和，然后检查是否有 \(lim(x,\complement_U S)\) 即可。
结束了吗？还没有。我们还需要计算对于一个集合 \(S\) 剩下空位的填法。相当于是让我们把 \(m\) 个位置划分为无序的若干组，每组填上同一个数。这显然是第二类斯特林数，因此方案为 \(\begin{Bmatrix}m\\\mathrm{popcount}(S)\end{Bmatrix}\)。所以处理第二类斯特林数后做 dp 即可。时间复杂度 \(O(n\log n+nk+k2^k)\)，原因是高位前缀和那里可以状压省掉一个 \(k\)。
Submission #48248921 - AtCoder Regular Contest 158
ARC159
A. Copy and Paste Graph
不妨猜结论，从 \(u\) 到 \(v\) 的最短路相当于从 \((u-1)\bmod n+1\) 到 \((v-1)\bmod n+1\) 的最短路。
证明考虑反证。假设最短路不是 \((u-1)\bmod n+1\) 到 \((v-1)\bmod n+1\) 的最短路，那么我们将路径上所有的点 \(x\) 映射为 \((x-1)\bmod n+1\)，则得到一条从 \((u-1)\bmod n+1\) 到 \((v-1)\bmod n+1\) 更短的路径，和假设不符，所以原命题成立。
Submission #48268533 - AtCoder Regular Contest 159
B. GCD Subtraction
注意到将 \(x,y\) 同时变为 \(x-\gcd(x,y),y-\gcd(x,y)\) 不会使得 \(\gcd(x',y')\) 变小，更确切的说，\(\gcd(x,y)\mid \gcd(x',y')\)。这意味着本质不同的 \(\gcd(x,y)\) 个数只有 \(O(\log V)\) 个，意味着如果我们能快速找到减多少次能够使得 \(\gcd(x,y)\) 变化，复杂度是可接受的。而这个事情也是容易做到的。不妨每次先令 \(x'=\dfrac{x}{\gcd(x,y)},y'=\dfrac{y}{\gcd(x,y)}\)，显然这不影响减法次数。注意到如果 \(\gcd(x,y)\) 变化，它增加的倍数至少应该同时是 \(a\) 和 \(b\) 的因数。所以我们直接枚举 \(a-b\) 的因数，然后计算次数后返回所有因数为达到目标所做的减法次数的最小值即可。
Submission #48268912 - AtCoder Regular Contest 159
C. Permutation Addition
首先试图发掘充要条件。考虑 \(n\) 为奇数的情况，每次加法不会改变 \(\sum\limits_{i=1}^n a_i\bmod n\) 的值，因此如果让所有数相等，要求 \(\sum\limits_{i=1}^n a_i\equiv 0\pmod n\)。注意到我们可以通过钦定一个排列 \(p=\underbrace{\overbrace{p_1,p_2,\ldots,1}^i,p_{i+1},\ldots,2}_j\ldots p_n\)，然后再依据 \(p\) 钦定一个排列 \(q=\underbrace{\overbrace{n-p_1+1,n-p_2+2,\ldots,n-1}^i,n-p_{i+1}+1,\ldots,n}_j\ldots n-p_n+1\)。注意到我们对原序列操作 \(p\) 和 \(q\) 即可使得 \(i\) 位置相对减一，\(j\) 位置相对加一的效果。依此每次操作最小值和最大值直到最小值和最大值相等即可得出合法方案。
接下来可以考虑 \(n\) 为偶数。我们现在只能确定其不会改变 \(\sum\limits_{i=1}^n a_i\bmod \dfrac{n}{2}\) 的值，那么首先要求 \(\sum\limits_{i=1}^n a_i\equiv 0\lor \sum\limits_{i=1}^n a_i\equiv \dfrac{n}{2}\pmod {n}\)，分类讨论一下，如果 \(\sum\limits_{i=1}^n a_i\equiv 0\pmod {\dfrac{n}{2}}\)，则直接按照奇数做，否则随机操作一次改变奇偶性即可。
Submission #48269603 - AtCoder Regular Contest 159
D. LIS 2
怎么 ARC 的 D 这么唐。
考虑 \(f(i)\) 表示强制选到位置 \(i\) 的右端点的最长上升子序列数。考虑转移，\(f(i)=\max(\max\limits_{r_j<l_i} f(j)-l_i,\max\limits_{r_j\ge l_i} f(j)-r_j)+r_i\)。分别建立以值域为下标，支持单点修改，维护 \(f(j)\) 和 \(f(j)-r_j\) 的区间最值的线段树即可。
Submission #48273091 - AtCoder Regular Contest 159
E. Difference Sum Query
牛逼题。
注意到题目中的操作实际上就是加权二分的次数。考虑建出来二叉搜索树，每一层的根节点为当前确定区间为 \([l,r]\) 后计算出的 \(mid\)。然后儿子为 \([l,mid-1]\) 和 \([mid+1,r]\)。那么深度即为该点的值。由于二叉搜索树的中序遍历为 \(1,2,\ldots,n\)，所以 \(x_i\) 和 \(x_{i+1}\) 在二叉搜索树上必有祖先后代关系，所以 \(|x_i-x_{i+1}|\) 相当于是这两个点在二叉搜索树上的距离。而题目中 \(\max(\dfrac{a_i}{b_i},\dfrac{b_i}{a_i})\leq 2\) 的限制保证了二分次数不超过 \(O(\log n)\) 次，因此我们可以直接暴力计算这些点集的距离和。具体而言，我们直接在二叉搜索树上递归区间，如果询问区间 \([ql,qr]\) 完全包含当前区间 \([l,r]\)，答案为 \(2(r-l+1)\)，否则向两侧递归，并将答案加二。最后减去 \(dep_l\) 和 \(dep_r\) 带来的额外贡献即可。
复杂度 \(O(q\log n)\)。
Submission #48326930 - AtCoder Regular Contest 159
F. Good Division
考虑满足题意的区间长啥样。首先不存在绝对众数，然后长度为偶数。
原因是有绝对众数一定删不干净，否则每次任意找到当前出现次数最多的数和旁边一个不相同的位置，删掉两者继续做，由于这个数不是绝对众数，因此每次一定有这样的位置。
因此有了 \(O(n^2)\) 的暴力，\(f(i)\) 表示到位置 \(i\) 的方案数，然后从 \(i\) 向前，维护绝对众数转移即可。
然后考虑 CDQ 分治维护 dp。注意到绝对众数有很好的性质，即如果 \(x\) 在 \([l,r]\) 中为绝对众数，则其在 \([l,mid],[mid+1,r]\) 中的至少一个为绝对众数。因此我们向左算出 dp 值，考虑向右计算答案。注意到左侧的绝对众数改变次数为 \(O(\log n)\) 级别，因为每多一个改变需要的数字个数翻倍。先做一步容斥，变成减去左侧的若干 dp 值。维护出左侧的 \(O(\log n)\) 个绝对众数，枚举每一个众数，记为 \(x\)，做 dp 值的后缀和，然后顺序扫描右侧，每次判断是否以 \(x\) 为绝对众数，若不存在跳过，否则减去使得该区间绝对众数恰为 \(x\) 对应位置的后缀和即可。
精细实现复杂度可以做到 \(O(n\log^2 n)\)。
Submission #48337173 - AtCoder Regular Contest 159
ARC160
A. Reverse and Count
我日，差点被打爆了/xk。
暴力排序是 \(O(n^3)\) 的，我们考虑优化这一过程。
注意到我们每次按位比较。注意到会影响到这一位的翻转区间只有 \(O(n)\) 个，我们把这些区间拉出来，记为 \(seg_1,seg_2,\ldots,seg_k\)，设剩下的区间集合为 \(S\)，那么我们一定能确定 \(seg_{i_1},seg_{i_2}\leq\ldots\leq S\leq \ldots\leq seg_{i_k}\)。递归处理 \(S\)。这样就完成在 \(O(n)\) 的时间复杂度内对 \(n\) 个操作序列确定位置，所以总复杂度 \(O(n^2)\)。
Submission #48707910 - AtCoder Regular Contest 160
B. Triple Pair
板子题。钦定 \(x>y>z\)。直接考虑对 \(x\) 根号分治。\(x\leq \lfloor\sqrt{n}\rfloor\) 的时候答案直接是 \(\lfloor\sqrt n\rfloor^3\)。否则要求 \(y,z\leq \lfloor\dfrac{n}{x}\rfloor\)。对 \(x\) 做整除分块即可。根号分治的目的是保证讨论的一直是最大值。
Submission #48708124 - AtCoder Regular Contest 160
C. Power Up
也是简单题。考虑 \(f(i,j)\) 表示到数字 \(i\) 剩下 \(j\) 个的方案数，单次转移是 \(O(1)\) 的。乍一看状态数不对，但考虑每一个数字 \(i\)，其数字个数对第二维大小的贡献应该是 \(\sum\limits_{j=0} \dfrac{cnt_i}{2^j}\leq 2cnt_i\)，即考虑其对 \(f(i),f(i+1)\) 的贡献之和。而 \(\sum\limits_{i=1}^n cnt_i=n\)。所以第二维的大小总和即总状态数是 \(O(n)\) 的，然后就做完了。
Submission #48708772 - AtCoder Regular Contest 160
D. Mahjong
从这里开始上了强度。
奇怪数数题先找点充要条件，一个什么样的序列是合法的？
首先注意到两个操作都不会改变模 \(k\) 意义下的余数，所以显然上来要求 \(m\equiv 0\pmod k\)。
然后注意到对同一个位置操作 \(k\) 次 \(2\) 操作等价于对这 \(k\) 个位置分别做 \(1\) 操作，那么我们可以强行钦定每个位置上的 \(2\) 操作数量不超过 \(k-1\)。
注意到对一个位置做 \(1\) 操作不会改变其在模 \(k\) 意义下的余数。因此位置 \(i\) 必须恰好被 \(a_i\bmod k\) 次 \(2\) 操作覆盖。这意味着对于一个合法的序列，如果我们钦定每个位置的 \(2\) 操作数量不超过 \(k-1\)，则操作方案应当可以唯一确定。即在第一个位置上做 \(a_1\bmod k\) 次 \(2\) 操作，第二个位置做 \(a_1\bmod k+(a_2-a_1)\bmod k\) 次，以此类推。
但是有一个问题，我们如果做 \(2\) 操作把 \(a_i\) 变成了负数将会非常麻烦。怎么办？考虑把整个过程倒过来，把操作变成单点加和区间加。注意到我们钦定了 \(1\) 操作和 \(2\) 操作数量且 \(2\) 操作数量小于 \(k\) ，操作序列和最终合法的序列仍然满足双射关系。
现在问题变成了对操作计数。令 \(f(i,j)\) 表示考虑到位置 \(i\)，前面的操作次数为 \(j\) 的方案数。转移分别枚举做哪种操作，具体转移式写在下面。
这样我们就有了一个 \(O(nm^2)\) 做法，但是复杂度疑似有点高。
然后我死在这了/cf。
然后开始魔法。记 \(F(i)\) 为 \(f(i,*)\) 的 OGF。拿生成函数刻画转移。
酷！这样答案就是 \([x^{\frac{m}{K}}] (\dfrac{1}{1-x})^{2n-K+1}(1-x^K)^{n-K+1}\)。
对前后进行一个二项式定理，然后暴力卷积状物暴力算组合数出系数。注意到你只需要算一项所以卷积的枚举量是 \(O(n)\) 的，然后带上组合数是 \(O(n^2)\)。
式子放在下面。
酷！
Submission #48709472 - AtCoder Regular Contest 160
E. Make Biconnected
强度下去了/hanx。这个题评铜牌是不是有点高了。
首先进行一些观察，定义 \(leaf\) 是所有度数为 \(1\) 的点构成的集合，那么答案的下界一定是 \(\sum\limits_{u\in leaf} W_u\)。原因是每个叶子至少连出去一条边，否则删去叶子唯一连边的另一端点即可让叶子和剩余部分不连通。
下面我们考虑能否达到这个下界。
若 \(|leaf|\equiv 0\pmod 2\)，我们可以说明这个下界总是可以取到。设 \(dfn(u)\) 表示 \(u\) 号点的 dfs 序，我们将叶子按照 \(dfn(u)\) 排序，记排序后第 \(i\) 个点为 \(leaf_i\)，同时记 \(mid=\dfrac{|leaf|}{2}\)。我们进行如下操作，将 \(leaf_i\) 向 \(leaf_{i+mid}\) 连边。其中 \(i\in[1,mid]\)。证明考虑把树拍到欧拉序上，然后考虑每个叶子所在的分组，结合 \(d\leq 3\) 容易证明（另：我记得这个性质对于所有树成立，不知道对不对）。
然后考虑 \(|leaf|\equiv 1\pmod 2\)。考虑把剩下的叶子和某个点连边，不难想到我们希望一定是和 \(W_x\) 最小的那个 \(x\) 连接。唯一的问题是 \(x\) 存在于 \(u\) 到其上方第一个度数不小于 \(1\) 的点的路径的中间，这种时候我们只需要换一个叶子即可。唯一的 corner case 是一个点挂三条链，这个时候我们再判一下次小值即可。
Submission #48711805 - AtCoder Regular Contest 160
F. Count Sorted Arrays
恐怖题。
我们定义一次交换操作是有用的，当且仅当其至少让所有排列当中的一种排列发生改变。
考虑有效交换的次数。假设一次交换操作是 \((u,v)\) 是有效的，首先它会使 \((u,v)\) 变成无效。同时它可能会使一些 \((k,u),(v,k)\) 从无效变为有效，我们很难直接断言有效交换的数量的变化情况，但显然其不会影响 \((i,j),i,j\not\in \{u,v\}\) 的有效情况，因此考虑进行一些分类讨论。
- \((k,u)\) 变为有效。
此时 \(a_u>a_k>a_v\)。注意到原来 \((k,v)\) 现在由有效变为无效，抵消掉了 \((k,u)\) 带来的贡献，所以总有效操作数量减一。
- \((v,k)\) 变为有效。
此时 \(a_u>a_k>a_v\)。注意到原来 \((u,k)\) 现在由有效变为无效，抵消掉了 \((v,k)\) 带来的贡献，所以总有效操作数量减一。
因此我们说明了有效操作的数量单调递减。这意味着有效操作只有 \(O(n^2)\) 个。如果我们能快速判断一个操作是否有效，同时可以快速维护有效操作带来的变化，这个题就做完了。
我们考虑对排列进行一些世界级映射。注意到每个排列恰好对应了 \(n\) 维平面上从 \((0,0,\ldots,0)\) 走到 \((1,1,\ldots,1)\) 的一条路径，每次可以让任意一维坐标加 \(1\)，在第 \(i\) 步在 \(p\) 位置加 \(1\) 意味着 \(a_p=i\)。此时路径上的第 \(i\) 点的第 \(p\) 个二进制位为 \(1\) 意味着在排列中第 \(p\) 个位置上的数字不大于 \(i\)。
我们重写一下排列的判定条件。一个排列可以在若干次操作后排好序，当且仅当把路径上的每一个点看做 \(01\) 序列后顺次执行交换操作其变为有序。我们成这样的点为好点、这意味着合法排列的数量相当于从 \((0,0,\ldots,0)\) 仅经过好点走到 \((1,1,\ldots,1)\) 的路径数量。容易 \(O(2^n n)\) 解决。
同时，我们可以暴力模拟每个点看做序列顺次执行交换操作后当前的序列是什么样子的，因此我们可以简单以的 \(O(2^n n)\) 的复杂度在每次操作结束后判定一个点是否是好的。
最后我们需要判定操作是否有效。结合上面的结论，我们在每次执行有效操作后暴力重构所有 \((k,u),(v,k)\) 操作的合法性。这个复杂度也是 \(O(2^n n)\) 的。
总有效操作次数为 \(O(n^2)\)，所以总复杂度为 \(O(2^nn^3+m)\)。
Submission #48715812 - AtCoder Regular Contest 160
ARC161
A. Make M
比较简单的题。首先考虑是非严格大于的做法，那么我们把序列排序后劈成两半然后做类归并状物即可。
然后现在我们要相邻的不相等，那么我们把大的部分和小的部分全部从大到小排以后拼到一起即可，感性理解的话，让较大的和较大的匹配一定能使得相邻两个数的差尽可能大。
Submission #48347711 - AtCoder Regular Contest 161
B. Exactly Three Bits
注意到答案一定从低到高是抹掉 \(n\) 的若干数位，直到 \(\mathrm{popcount}(n)\) 恰好 \(3\)。现在唯一的问题是 \(n\) 的数位不足 \(3\)，那么我们只需要每次把 \(n\) 减一直到 \(\mathrm{popcount}(n)\) 不小于 \(3\) 为止。容易证明这个操作次数不会超过 \(4\) 次。
Submission #48356115 - AtCoder Regular Contest 161
C. Dyed by Majority (Odd Tree)
考虑给每个点钦定颜色，分为颜色不定，为白色和黑色考虑。从下到上 dfs 整棵树，把当前该节点的所有儿子中颜色不定的设为当前的颜色，设度数为 \(deg\)，然后如果儿子中和其颜色相同的数量小于 \(\lfloor\dfrac{deg}{2}\rfloor\) 则一定无解，若为 \(\lfloor\dfrac{deg}{2}\rfloor\) 则去钦定其父亲的颜色，否则该点父亲颜色不定，一直做到根。最后把依据此方案构造出的颜色设为答案，特别的，若根节点颜色不定，则在上面随便填一个颜色。
Submission #48426001 - AtCoder Regular Contest 161
D. Everywhere is Sparser than Whole (Construction)
若至题/bobo。
如果 \(nd>\dfrac{n\times (n-1)}{2}\) 则无解，否则直接构造 \(E=\{i\in[1,n],j\in[1,d]\vert (i,(i+d-1)\bmod n+1)\}\)。图的简单性可以证明，然后考虑证明稀疏性。对于任意一个子图 \(G\)，令 \(G_k\) 表示 \(G\) 中仅由 \((i,(i+d-1)\bmod n+1)\) 的边和点构成的子图。容易发现对于任意 \(G_k\) 每个点的度数不超过 \(2\)，即 \(G_k\) 密度不大于 \(1\)。所以总的密度不超过 \(d\)。
E. Not Dyed by Majority (Cubic Graph)
牛逼题/pz。
注意到合法的解不会很多（我去哥们你咋注意到的），所以我们可以随机一个解，然后判定这个解是否合法。考虑判定一个颜色序列是否可以被构造。对于每一个点，如果其颜色为黑，则其周围点至少有两个黑点。令周围三个点为 \(u,v,w\)，\(col(u)\) 代表 \(u\) 号点的颜色，其中 \(0\) 为白色，则要求 \((col(u)\lor col(v))\land (col(v)\lor col(w)) \land (col(u)\lor col(w))\)。这个限制可以直接 2-SAT 描述，最后判定 2-SAT 是否有解即可。
关于合法的解占比的数量级，官方给出的估算是对于较大的 \(n\) 答案为 \(0.293\)，较小的为 \(0.48\)，感兴趣的可以阅读 Editorial 和 Supplementary 获取更多信息。
Submission #48447738 - AtCoder Regular Contest 161
F. Everywhere is Sparser than Whole (Judge)
完全没看证明，所以写的东西比较意识流。
先判掉图不连通的情况。首先有最大密度子图转最小割的做法。记最小割为 \(f\)。然后我们可以根据 \(nm-f\) 的正负性判断答案存在大于 \(D\) 的子图。然后考虑判等于 \(D\) 的情况。注意到那个最小割做法是把度数和边拆开算，这个限制条件相当于有边满流。所以我们现在直接把原图中的边的容量设成 \(1-eps\)，此时的判定为 \(nm-f'>0\)。然后这个东西可以和前面的合起来做。