358 P5897 [IOI2013]wombats
线段树维护矩阵乘法，注意到有决策单调性，复杂度 \(O(nC^2\log n)\)，但是空间过大，我们递归到一个较小的区间时暴力计算即可，若阈值为 \(k\)，空间会整体除 \(k\)。
359 P8275 [USACO22OPEN] 262144 Revisited P
先考虑一个序列的问题：
答案显然不超过最大值 \(X\) 加 \(\lceil\log n\rceil\)，我们不妨先进行 \(<X\) 所有数的操作，进行完后能得到一个相邻两个至少一个 \(X\) 的序列（假设长为 \(l\)），答案即 \(X+\lceil\log l\rceil\)。
不会，有没有人来教育我一下！
咕咕咕。
360 P6277 [USACO20OPEN]Circus P
注意到一定能将状态变换为所有奶牛都在 \(1,2,\cdots,k\)，因此可以用一个 \(k\) 排列刻画状态，只需考虑这些排列之间的等价关系。
等价关系一定是每次换一对奶牛，而换奶牛不会受编号影响，我们只需求出位置的等价类，答案即 \(\frac{k!}{\prod s_i!}\)（\(s_i\) 为第 \(i\) 个等价类大小）。
考虑如何判断两头奶牛 \(p,q\) 在同一等价类，我们提取出 \(p\) 到 \(q\) 的一条路径，若路径上能空出一个分叉来等待，我们一定能交换这两头奶牛。
我们只需考虑中间全为二度点的链，注意到两端能交换等价于链长小于 \(n-k\)，于是两个点能交换等价于中间不存在长度大于等于 \(n-k\) 的全为二度点的链。
从大到小枚举 \(k\)，于是只需处理连通块的合并，我们动态地维护所有极长不合法链，对于每个 \(k\) 暴力枚举每个不合法链讨论其贡献即可，这里是均摊线性的。
复杂度 \(O(n\log n)\)。
361 CF1832F Zombies
场上猜的是每次要么取 \(l\) 最小的一些，要么取 \(r\) 最大的一些，发现优化不了。
结论：所有门按照中点下标排序，选择同一个电网的一定是一段区间（证明可以考察函数图像）。
于是 wqs 二分，可能作为电网的区间只有 \(O(n)\) 个，每次 \(O(n^2)\) dp 一下即可。
362 CF1808E3 Minibuses on Venus (hard version)
场上只会 E2，十分抽象，可能是嫌麻烦吧。
枚举 \(s\)，答案是所有存在一个 \(2v\equiv s\pmod k\) 的 \(v\) 的长为 \(n\)，和为 \(m\)（模 \(k\)）序列数量。
当 \(k\) 为奇数时，合法 \(v\) 恰好一个：
\[(\sum_{i=1}^{n-1}{n\choose i}(-1)^{i-1}k^{n-i-1})+(-1)^{n-1}[nv\equiv s\pmod k] \\=(-\frac1k\sum_{i=0}^n{n\choose i}(-1)^ik^{n-i})+k^{n-1}-\frac{(-1)^{n-1}}{k}+(-1)^{n-1}[nv\equiv 2v\pmod k] \\=-\frac{(k-1)^n+(-1)^{n-1}}{k}+k^{n-1}+(-1)^{n-1}[nv\equiv 2v\pmod k]\]对 \(v\) 求和：
\[=k^n-(k-1)^n-(-1)^{n-1}+(-1)^{n-1}\sum_v[nv\equiv 2v\pmod k]\\=k^n-(k-1)^n+(-1)^n(1-\gcd(n-2,k)) \]当 \(k\) 为偶数时，合法 \(v\) 有两个，差为 \(\frac k2\)，类似地列出式子：
\[\sum_{1\leqslant i+j\leqslant n}(-1)^{i+j-1}{n\choose i,j,n-i-j}k^{n-i-j-1}-\frac{\sum_{i+j=n}(-1)^{n-1}{n\choose i}}k+(-1)^{n-1}(\sum_{2\mid i}{n\choose i}[nv\equiv 2v\pmod k]+\sum_{2\not\mid i}{n\choose i}[nv+\frac k2\equiv 2v\pmod k])\\=k^{n-1}-(\sum_{0\leqslant c\leqslant n}{n\choose c}2^c(-1)^ck^{n-c-1}-\frac{2^n(-1)^n}{k})+C \\=k^{n-1}-\frac{(k-2)^n-(-2)^n}{k}+C\]把 \(C\) 拿出来推一下：
\[(-1)^{n-1}(\sum_{2\mid i}{n\choose i}[nv\equiv 2v\pmod k]+\sum_{2\not\mid i}{n\choose i}[nv+\frac k2\equiv 2v\pmod k]) \\=(-2)^{n-1}([nv\equiv 2v\pmod k]+[nv+\frac k2\equiv 2v\pmod k])\]注意到两条只能成立一条，因此可以写成 \([nv\equiv 2v\pmod{\frac k2}]\)。
求和有：
\[\frac{k^n-(k-2)^n+(-2)^n}{2}+(-2)^{n-1}\sum_{v=0}^{\frac k2-1}([nv\equiv 2v\pmod{\frac k2}]]) \\=\frac{k^n-(k-2)^n+(-2)^n}{2}+(-2)^{n-1}\gcd(n-2,\frac k2)\]复杂度 \(O(T+\log n)\)。
363 ARC160F Count Sorted Arrays
为啥都会？？？？我觉得很难啊。
根据排序网络经典结论，只需对所有 01 序列分别考察排序后的结果。我们将排列双射成一个 01 序列组，每一项都是后一项的子集，其为 \(n\) 阶 hypercube 从 \((0,0,\cdots,0)\) 到 \((1,1,\cdots,1)\) 的一条路径。
一个排列能被还原当且仅当其路径上所有 01 序列都能被还原，我们动态维护还不能被还原的 01 序列，每次加入操作时检查并更新答案。更新答案需要维护 hypercube 每个位置到 \((0,0,\cdots,0)\) 与 \((1,1,\cdots,1)\) 的路径数量，容易在 \(O(n3^n)\) 内计算。
364 loj#3607. 「PA 2021」Wystawa
这能做？？？？？？？？？？？？？然而 hzr 的确是会做的，脚盆队长实力强劲，欢迎大家加入粉丝群 706094232。
做点讨论将题意转化为 \(a_i\geqslant b_i\)，\(a\) 中不超过 \(k\) 个数变为 \(b\)，具体地：
- 若 \(a_i\geqslant b_i\) 的数不少于 \(k\)，我们每次一定操作这种数，只需将其余 \(b_i\) 赋值为 \(a_i\)；
- 否则，我们一定把这些数操作完，然后 swap(a,b) 变为类似的问题。
二分答案，直接列出 dp，\(f_{i,j}\) 表示前 \(i\) 个位置，\(j\) 次操作的答案，容易发现其有凸性，于是考虑 slope trick，将转移写出来：
\[f_{i,j}=\max(\min(f_{i-1,j}+a_i,f_{i-1,j-1}+b_i),0) \\=\max(\min(f_{i-1,j},f_{i-1,j-1}+b_i-a_i)+a_i,0)\]每次转移完成后将 \(f\geqslant mid\) 的 dp 值删掉并更新答案。
差分数组不降，其等价于差分数组插入 \(b_i-a_i\)，整体平移容易维护，对 \(0\) chkmax 只需 popback，使用 set 维护即可，复杂度 \(O(n\log n)\)。
365 ARC159E Difference Sum Query
将问题结构建立出来，其事实上是在一个二叉搜索树上找一个点，每个结点恰好对应一个值。注意到答案就是虚树大小，我们类似线段树定位一下区间就能算出来了。
复杂度 \(O(Q\log n)\)。
366 ARC138E Decreasing Subsequence
挺不错的题，zyf 之前搬到模拟赛过。
我们考察所有 \(a_i\) 不为零的 \(i\rightarrow a_i-1\) 构成的一张图，那么图由编号递减的链组成。
我们考察上升序列 \(i_1,i_2,\cdots,i_k\)，注意到 \(a_{i_1}\leqslant i_1\)，于是有 \(a_{i_k}-1<a_{i_{k-1}}-1<\cdots<a_{i_1}-1<i_1<i_2<\cdots<i_k\)，且序列对称部分有边，因此这些边一定分布在 \(k\) 条不同的链上。
于是就能做了，枚举链上左侧点数 \(A\)，右侧点数 \(B\)，分配方案数为第二类斯特林数，非这些链上的点任意分配成链方案数为贝尔数，答案即：
\[\sum_A\sum_B{n+1\choose A+B}{A\brace k}{B\brace k}B_{n+1-A-B} \]卷积即可做到 \(O(n\log n)\)，平方也可通过。
367 Yuhao Du Contest 11 M Minimum Element Problem
ZR 考过，补一下，还是挺有意思的。
类似 CF104008J Permutation Puzzle，注意到只需关心填数的上下界，内部的数一定能取到，差分后问题变为统计 \(\operatorname{dep}_x,\operatorname{size}_x\) 的分布（分别对应下界与上界）。
\(\operatorname{size}_x\) 较简单，注意到在一颗二叉树上，插入一个排名固定的结点方案始终唯一，因此子树外的方案数始终为大小为 \(n-\operatorname{size}_x\) 的二叉树数量，而子树内部并不完全一致，因为左子树大小不能超过 \(X-1\)，右子树大小不能超过 \(n-X\)，因此要分别算出方案做卷积。
\(\operatorname{dep}_x\) 的计算需要发现一个关键性质——\(X\) 左右侧的计数是独立的，我们只有对其子树大小的限制，求出两侧答案后卷积即可得到答案。以左侧为例，此时问题变为计数点数为 \(X-1\)，根的连续右儿子数量为 \(k\) 的二叉树数量，这个东西叫卡特兰数的 \(k\) 次卷积，做法大概是：
使用兄弟儿子表示法与括号序刻画结构，再写出格路，注意我们只要求这个序列有 \(i\) 个连续括号作为结尾，使用折线法 \(O(1)\) 计算即可。
复杂度 \(O(n\log n)\)。
标签：2v,frac,21,55,sum,星河,pmod,nv,equiv From： https://www.cnblogs.com/xiaoziyao/p/17398219.html