CF1704H1 Game of AI (easy version)
考虑一种合法方案中的 $b$，他一定形成了若干条链：$p_1\rightarrow p_2\dots p_k$，其中 $p_1$ 占领了 $p_1$ 和 $p_2$，$\forall 1<i<k$，$p_i$ 占领了 $p_{i+1}$，$p_k$ 没有占领任何点。这可以通过从后向前操作得到。
对于一个大于等于 $2$ 的链，$a_1\dots a_{k-1}$ 都已经确定。而 $a_k$ 根据上述操作是可以任意连的（除了自己），而长度为 $1$ 的则是不能连到所有链的链头。
设 $f_{i,j}$ 表示用了 $i$ 条长度大于等于 $2$ 的链，用了 $j$ 个点的方案数，其实就是是模拟一个 exp：
\[f_{i,j}\overset + \leftarrow f_{i-1,j-k}\times \binom{i-1}{k-1} k!(n-1)\]拆一下发现这个是可以前缀和优化的。最后也只需要枚举有几个长度为 $1$ 的链就行了，复杂度 $\mathcal O(n^2)$。
AT_agc028_d [AGC028D] Chords
根据欧拉平面图公式：$V+F-E=C+1$。$F$ 是面数，$V$ 是点数，$E$ 是边数，$C$ 是联通块数。
考虑如果初始加上了所有 $(i,i\bmod{2n}+1)$ 这些边，则 $C=1$。如果删去了所有边，则左侧会增大 $2n$ 减（靠边的面数）。
| 所以答案就是 $2n$ 减去靠边的面数加一。需要算靠边的面的数量。考虑钦定一些边，他们属于同一个面，容斥系数是 $(-1)^{ | S | }$，这样一个面的贡献次数就掐还是 $-1$。 |
所以可以对钦定一些边这个过程做区间 DP，钦定的相邻两个边之间的系数就是一个双阶乘，每次找到区间内除了左右端点第一个被钦定的边即可。复杂度 $\mathcal O(n^3)$。
CF1774G Segment Covering
首先考虑单组询问。取出所有区间，考虑区间 $[l_i,r_i]$，如果存在一个区间 $[l_j,r_j]\subseteq [l_i,r_i]$，那如果选择了 $i$，$j$ 有选与不选两种选择方式，那贡献一定为 $0$，所以可以删掉 $i$。这样就得到了左右端点都递增的区间集合。
然后考虑做覆盖：把区间从左到右排序，首先一定选择 $l_i=L$ 的区间 $i$。然后考虑 $i+1$，要求 $l_{i+1}\leq r_i$。
接下来可以发现对于所有 $k>i+1,l_k\leq r_i+1$ 的区间，选了他之后贡献一定为 $0$ 了，因为 $i+1$ 选或者不选都可行。所以需要加入 $l_k>r_i$ 的最小的 $k$ 的区间。
如何快速做上述过程：可以维护 $nex_i$ 表示第一个 $l_j>r_i$ 的区间，并求出其倍增数组。每次从第一个区间和第二个区间往后跳。如果最后跳到了同一个区间则不合法，因为这说明中间的过程出现了空位。还有一些小的 corner case。最后只需要判断跳的步数的奇偶性来输出 $1$ 或者 $998244352$。
CF1804H Code Lock
环非常的讨厌！考虑做一个旋转扫描线，维护一根线，把环劈成两半，这样统计代价是简单的。
记录当前半边的集合以及扫过的集合，复杂度是 $\mathcal O(2^{k/2}\binom{k}{k/2}\text{poly}(k))$。
P11746 Dynamic Color Problem
考虑暴力容斥：
\[\begin{aligned} &\sum_{i=0}^n\sum_{j=0}^m[(i+j)\bmod 2=0]\sum_{x\geq i}\sum_{y\geq j}(-1)^{x-i+y-j}\binom x i\binom y j\binom n x \binom m y 2^{(n-x)(m-y)}f(x,y)\\ &f(x,y)=\begin{cases} 2&& x,y\not=0\\ 2^{x+y}&& \text{oth}. \end{cases} \end{aligned}\]首先对于 $x=0$ 或者 $y=0$（以 $x=0$ 举例），有：
\[\begin{aligned} &\sum_{j=0}^m[j\bmod 2=0]\sum_{y\geq j}(-1)^{y-j}\binom y j\binom m y 2^{n(m-y)+y}\\ =&\sum_{y=0}^m\sum_{j=0}^y[j\bmod 2=0](-1)^{y-j}\binom y j\binom m y 2^{n(m-y)+1}\\ =&2^{nm+1}+\sum_{y=1}^m (-1)^y2^{y-1}\binom m y 2^{n(m-y)+1}\\ \end{aligned}\]可以进一步化简，也可以 $\mathcal O(n)$ 计算了。对于 $x,y\not=0$：
\[\begin{aligned} &\sum_{i=0}^n\sum_{j=0}^m[(i+j)\bmod 2=0]\sum_{x\geq i}\sum_{y\geq j}(-1)^{x-i+y-j}\binom x i\binom y j\binom n x \binom m y 2^{(n-x)(m-y)+1}\\ =&\sum_{x=0}^n\sum_{y=0}^m(-1)^{x+y}\sum_{i=0}^x\sum_{j=0}^y[(i+j)\bmod 2=0]\binom x i\binom y j\binom n x \binom m y 2^{(n-x)(m-y)+1}\\ \end{aligned}\]这里考虑一步组合意义，可以看成是 $x+y$ 个物品里面选任意偶数个。
\[\begin{aligned} =&\sum_{x=0}^n\sum_{y=0}^m(-1)^{x+y}2^{x+y-1}\binom n x \binom m y 2^{(n-x)(m-y)+1}\\ =&\sum_{x=0}^n\binom{n}{x}(-2)^x\sum_{y=0}^m(-2)^{y}\binom m y 2^{(n-x)(m-y)}\\ =&\sum_{x=0}^n\binom{n}{x}(-2)^x2^{m(n-x)}\sum_{y=0}^m\binom m y (-2^{1-(n-x)})^{y}\\ =&\sum_{x=0}^n\binom{n}{x}(-2)^x2^{m(n-x)}(1-2^{1-(n-x)})^m \end{aligned}\]可以快速幂暴力计算，复杂度 $\mathcal O(n\log n)$。
CF1375H Set Merging
考虑在值域上分个块，先预处理出 $f_{i,j,k}$，表示第 $i$ 个块中，取出了编号在 $[j,k]$ 中的点的范围的集合。这样查询可以做到 $\frac{nq}{B}$ 次。
对于预处理，暴力过不去，再考虑分治！每次向两边分治，复杂度是 $T(n)=\frac{n^2}{2}+2T(\frac{n}{2})=n^2$。这样预处理复杂度是 $nB$。
CF1553I Stairs
简单的，钦定连续段容斥，分治 NTT 优化。
[ARC140F] ABS Permutation (Count ver.)
我是唐的。
首先考虑他的逆排列，然后可以发现每个 $\bmod m$ 不同的位置都独立了。所以只需要考虑 $m=1$ 的情况。
设 $F$ 为一个连续段的生成函数，则 $F=x+2x^2+3x^3\dots=\frac{x+x^2}{1-x}$。设 $f_k$ 表示钦定 $k$ 个位置为 f_i