ARC154E Reverse and Inversion
要长脑子了。
首先先尝试拆一拆贡献。对原来的式子进行一定的化简，可以得到：
\[\sum\limits_{i}i(\sum\limits_{i>j}[P_j>P_i]-\sum\limits_{i<j}[P_i>P_j])\\ =\sum\limits_{i}i(i-P_i) \]因此我们只需要求出每个 \(P_i\) 被换到哪里即可。
注意到初始的时候在 \(i\) 处的 \(P_i\) 被换到 \(j\) 和 \(n-j+1\) 的位置的概率是等价的。所以，如果 \(P_i\) 被交换过了，那么其期望位置就是 \(\frac{n+1}{2}\)，否则就是其原来的位置。这两种情况的概率都是容易计算的。时间复杂度\(O(nb\log m)\)。
异或图
好像以前做过，但是忘记以前写了啥了（
考虑进行一个斥的容。枚举一个边的集合，钦定其不满足条件，也就是这条边两端点相同。那么每个连通块的值域范围都变成最小值。若连通块大小为偶数，则对最终 xor 值没有贡献，直接乘上可能的选择方案数就行。若大小为奇数，则可以看成一个数。
我们先来解决每个数互相独立有上界，并且要求 xor 为 \(C\) 的方案数。我们发现，如果从高到低考虑的过程中，发现某个数不受上界限制了，那么总是可以调整 xor 为 \(C\)。因此容易得到一个 \(O(n\log C)\) 计算单次的方法。
则我们需要求出 \(f_S\) 表示算入答案的集合为 \(S\) 的容斥系数和。我们先 dp 出 \(g_S\) 表示选择一些边联通 \(S\) 子集的容斥系数和，这只需要枚举一个包含最小标号的点的联通子集即可。然后我们初始有一个全集，每次枚举一个 \(i\)，从比 \(i\) 大的所有点中选择出和 \(i\) 在一个连通块里的，根据连通块奇偶性讨论即可，然后就做完了。
这样看上去复杂度是 \(O(n3^n)\) 的，但是实际上上面那个 DP 是形如 \(\sum 2^i3^{n-i}\) 的，所以是 \(O(3^n)\) 的。总复杂度是 \(O(3^n+2^nn\log C)\)。
AGC041F Histogram Rooks
首先考虑进行一个斥的容，枚举一些格子钦定其不能被车覆盖到，那么和这个格子同行同列的点就不能放车。
接下来我们枚举一些行和列，钦定这些行列不能放车，那么车的贡献容易计算，但是我们现在要在这些位置放上空格子，使得每行每列至少有一个空格子。
不妨进一步容斥：我们选择一些列，让这些列不能放空格子，这样我们会设出一个状态：建立笛卡尔树后设 \(dp_{i,j,h}\) 表示 \(i\) 子树内，有 \(j\) 个列是不能放车且不能放空格子的，有 \(h\) 个列是不能放车且可以任意放空格子的。
注意到转移的时候计算贡献只和 \(j+h\) 以及 \(h\) 是否有值有关，因此我们可以设 \(dp_{i,j,0/1}\) 表示 \(i\) 子树内有 \(j\) 个格子不能放车，有/无列是不能放车且可以任意放空格子的，这样转移就是 \(O(n^2)\) 的了。
一个需要注意的地方就是，每次给最下方新增一行的时候不需要快速幂，直接暴力的复杂度就是 \(O(\sum A)=O(n^2)\) 的。总复杂度是 \(O(n^2)\) 的。
P9501 「RiOI-2」likely
我们考虑设 \(b_i=\prod\limits_{j=0}^{m-1}a_{(i+j)\bmod n}\)，直接来考虑这个东西要满足什么要求。
一个容易发现的事情是，如果将 \(i\) 向 \((i+m)\bmod n\) 连边，会划分成 \(g=\gcd(n,m)\) 个置换环，每个置换环上的 \(b\) 乘积相等，因为每个置换环上的乘积都对应了全部 \(a\) 乘积的 \(\frac{m}{g}\) 次幂。
另外我们容易发现，在此基础上，所有的 \(b\) 都是可以取到的。考虑将 \(a_i\) 用于调整 \(b_i\) 到我们想要的位置，这样一定可以调整得到。
然后我们需要计算每个 \(b\) 对应多少种 \(a\)，这只需要看 \(a\) 中的自由元个数即可。如果 \(\frac{m}{g}\) 是偶数，那么 \(b\) 中有 \(g\) 个等式，每个 \(b\) 对应 \(2^g\) 种方案，否则对应 \(2^{g-1}\) 种。
这样我们就可以枚举 \(b\) 中的 \(-1\) 是奇数还是偶数，这里以偶数为例。
对于一个置换环，其中有 \(i\) 个 \(1\) 的方案数就是 \({\frac{n}{g}\choose i}\)，其中 \(i\) 要是奇数，然后要把 \(g\) 个环卷起来。
直接多项式快速幂肯定过不去，但是注意到多项式的最高幂次乘上 \(g\) 是 \(n\)，也即我们可以直接 DFT 之后快速幂然后 IDFT 回来就行。
这样已经可以过了，但是还可以进一步减小常数：
- 我们只需要求单点值，因此 IDFT 可以做到 \(O(n)\)。
- 注意到原来多项式的生成函数可以写成 \(\frac{(1+x)^{\frac{n}{g}}+(1-x)^{\frac{n}{g}}}{2}\)，则点值可以直接快速幂计算。
于是我们就可以做到小常数 \(O(n\log n)\)。
CF1909I Short Permutation Problem
考虑 \(m\) 是奇数的情况，令 \(n=\lfloor\frac{m}{2}\rfloor\)，则若我们将 \(\leq n\) 的数称为小数，\(>n\) 的数称为大树，并且按照 \(n,n-1,n+1,n-2,n+2\) 这样交替插入，那么我们插入每个小数的时候，它和旁边的点都构不成 \(p_i+p_{i+1}\geq m\)，插入每个大数的时候都能构成。
因此，我们可以写出一个 DP：设 \(dp_{i,j}\) 表示插入了 \(i\) 个数，钦定满足 \(p_i+p_{i+1}\geq m\) 的构成了 \(j\) 个连续段，最后对其施加二项式反演即可，就可以得到一个 \(O(n^3)\) 的做法。
瓶颈主要在于两个：二项式反演和 DP。优化二项式反演是简单的，NTT 即可优化到 \(O(n\log n)\) 每次。而 DP 部分则稍微复杂一点。我们将 DP 的过程拆成两部分：大小数轮流插入的部分和只插入大数的部分。前者可以一遍 \(O(n^2)\) 的 DP 求出所有的。
现在我们需要考虑，在 \(i\) 个钦定段中插入 \(k\) 个大数如何得到 \(j\) 段，其中两个钦定段之间至少要放一个大数才能放在同一段中。我们将 \(j\) 段看做插入 \(j-1\) 个空位，空位和大数具有一样的效力，但是空位也不能相邻。
考虑再对“空位不能相邻”施加二项式反演，这样这个限制就去掉了，\(i\) 到 \(j\) 的贡献也容易直接计算出来，并用 NTT 做到 \(O(n\log n)\)。
整个过程需要 \(3n\) 次长度为 \(n\) 的卷积，常数较大。另外，进行了两次仅仅是方向相反的二项式反演，有没有老哥教教怎么优化这个玩意。
标签：frac,log,格子,sum,选讲,计数,tzc,我们,DP From： https://www.cnblogs.com/275307894a/p/18017276