AGC040C Neither AB nor BA

很难发现其实删除不会改变元素位置的奇偶性，所以只需要把奇数位置的 $\texttt{A}$ 和 $\texttt{B}$ 互换就行了。

那么现在就是 $\texttt{AA}$ 和 $\texttt{BB}$ 不能删除，所以只需要 $\texttt{A}$ 和 $\texttt{B}$ 的数量都不超过 $\lfloor\frac{n}{2}\rfloor$ 就行了。

正难则反，得到：

$Ans=3^n-2\times \sum\limits_{i=\lfloor\frac{n}{2}\rfloor+1}^n {n\choose i}\times 2^{n-i}$

显然，所有的方案数是 $3^n$ 因为每一个位置都有 $2$ 种方案。

然后枚举 $\texttt{A}$ 或者 $\texttt{B}$ 的数量，从 $\lfloor\frac{n}{2}\rfloor+1$ 开始枚举所以方案一定是无法消去的。

选择 $i$ 个位置填 $\texttt{A}$ 或者 $\texttt{B}$，其它的位置乱填就行了。

需要注意，并不需要考虑重复的情况，因为数量大于 $\lfloor\frac{n}{2}\rfloor+1$ 的元素肯定只有一种。

通过合理的实现，可以做到 $O(n)$。

AGC023C Painting Machines

这么好的 $2500$ 的题目为什么不评紫。

考虑枚举排列 $P$ 的得分 $i$，但是想要快速计算比比较困难。

所以考虑设 $f_i$ 表示操作了前 $i$ 个之后全部染黑的方案数，需要注意并不是恰好 $i$ 次。

对于一个第 $i$ 次操作之后就全部被染黑的方案 $P$，从 $[1,i]$ 的顺序是不重要的，影响答案的只有在 $i$ 之前选择了哪些。

那么我们将 $P_1$ 到 $P_i$ 从小到大排序排序，容易理解 $P_1=1,P_i=n-1$。

在满足上面要求的同时，还需要满足 $\forall k\in[1,i-1]\cap\mathbb{Z}$ 都有 $p_{k+1}-p_k\le 2$。

我们记 $x_k=p_{k+1}-p_k-1$，那么显然所有 $x_k\in\{0,1\}$。

而他们之间有满足等式：

$\sum\limits_{k=1}^{i-1}x_k=(\sum\limits_{k=1}^{i-1} p_{i+1}-p_i)-(i-1)$

同时：

$\sum\limits_{k=1}^{i-1} p_{i+1}-p_i=p_i-p_1=n-2$

所以就有：

$x_k\in\{0,1\}\wedge\sum\limits_{k=1}^{i-1} x_k=n-i-1$

那么显然 $x$ 的方案数就是 $i-1\choose n-i-1$，再乘上排列 $P$ 带来的贡献，得到：

$f_i={i-1\choose n-i-1}\times i!\times (n-i-1)!$

所以得分为 $i$ 的数量就是 $f_i-f_{i-1}$，那么就有：

$Ans=\sum\limits_{i=\lceil\frac{n}{2}\rceil}^{n-1} i\times (f_{i}-f_{i-1})$

时间复杂度为 $O(n)$。

ARC093E Bichrome Spanning Tree

设 $f_i$ 表示强制选第 $i$ 条边的最小生成树的权值，设 $g_i=\sum\limits_{j=1}^n [f_j=i]$。

如果不存在 $i\le X$ 存在 $g_i\ne 0$，那么显然是没有解的，因为进行的操作只能增大生成树的值。

如果 $g_{X}\ne 0$ 且 $\forall i<X$ 都有 $g_i=0$，那么显然这个图的最小生成树就是答案需要的，那么只要这 $g_X$ 条边存在一个颜色不一样就可以了，所以方案数为：

$(2^{g_X}-2)\times2^{m-g_X}$

如果存在 $i<X$ 且 $g_i=0$，那么：

• 如果 $f_i<X$，显然需要全部染成一个颜色。
• 如果 $f_i>X$，因为反正都不会影响答案所以可以随便填。
• 如果 $f_i=X$，那么只需要不是全部都与 $f_i<X$ 的颜色一样就行了。

设上面的情况分别有 $a,b,c$ 条边满足，那么方案数就是 $2\times 2^b\times(2^c-1)$。

时间复杂度为 $O(m^2\log n)$，但是并查集的 $\log$ 能叫 $\log$ 吗？

ARC144D AND OR Equation

设 $x< 2^i$，那么由题可以得到：

$f(x)+f(2^{i})=f(0)+f(2^{i}+x)$

进而可以得到：

$f(2^{i}+x)=f(x)+f(2^{i})-f(0)$

设 $y=2^{i}+x$，那么有：

$f(y)=f(y-2^{i})+f(2^{i})-f(0)$

容易发现 $y$ 的最高位是第 $i$ 位的时候满足上式。

那么容易理解，只需要 $f(0)$ 和所有的 $f(2^x)$ 确定下来，那么 $f$ 就整个确定了。

设 $g(i)=f(2^i)-f(0)$，那么：

$f(x)=f(0)+\sum\limits_{2^i\&x\ne 0} g(i)$

假设 $g$ 已经确定，考虑合法的 $f(0)$ 的数量。

假设 $s1=\sum\limits_{i=0}^{n-1}\max(g(i),0)$，$s2=\sum\limits_{i=0}^{n-1}\min(g(i),0)$。

因为 $0\le f(x)\le k$，所以必然有：

$\left\{\begin{matrix}f(0)+s1\le k \\f(0)+s2\ge 0\end{matrix}\right.$

所以解的个数为 $k-s1+s2+1$。

然而因为 $s1-s2=\sum\limits_{i=0}^{n-1} \lvert g(i)\rvert$，所以方案数为：

$k+1-\sum\limits_{i=0}^{n-1} \lvert g(i)\rvert$

设 $x=\sum\limits_{i=0}^{n-1} \lvert g(i)\rvert$，$s(x)$ 表示 $x=\sum\limits_{i=0}^{n-1} \lvert g(i)\rvert$ 时 $g$ 的方案数。

那么有：

$s(x)=[x=0]+\sum\limits_{i=1}^n 2^i\times{x-1\choose i-1}\times {n\choose i}$

枚举 $0$ 的个数，符号可以乱填，最后把 $x$ 的和分配到 $i$ 个数上要求非空。

所以答案就是：

$\sum\limits_{x=0}^k(k+1-x)\times s(x)$

化简：

$\sum\limits_{x=0}^k s(x)=1+\sum\limits_{i=1}^n 2^i\times{n\choose i}(\sum\limits_{j=i-1}^{k-1}{j-1\choose i-1})$

后面似乎是 朱世杰恒等式 ，所以得到：

$1+\sum\limits_{i=1}^n 2^i\times{n\choose i}\times {k\choose i}$

另外一个式子：

$\sum\limits_{x=0}^k x\times s(x)=\sum\limits_{x=0}^k\sum\limits_{i=1}^{n}2^i\times{n\choose i}\times{x\choose i}\times i$

那么同样的可以得到：

$\sum\limits_{i=1}^n2^i\times{n\choose i}\times i\times {k+1\choose i+1}$

所以：

$Ans=(k+1)\times (1+\sum\limits_{i=1}^n 2^i\times{n\choose i}\times {k\choose i})-\sum\limits_{i=1}^n2^i\times{n\choose i}\times i\times {k+1\choose i+1}$

时间复杂度为 $O(n\log n)$。

ARC115E LEQ and NEQ

让我很有启发的数据结构题。

考虑 DP，设 $f_{i,j}$ 表示填了前 $i$ 个位置第 $i$ 个位置为 $j$ 的方案数，那么显然有暴力的转移方程：

$f_{i,j}=-f_{i-1,j}+\sum\limits_{k=1}^{A_{i-1}}f_{i-1,k}$

那么考虑滚动数组，那么转移方式如下：

首先 $f_j\gets -f_j$，记 $S=\sum f_j$ 然后把 $f_j\gets f_j+S$，最后把大于 $A_i$ 的 $f$ 清理掉。

那么对于这个操作，容易想到可以使用线段树进行维护，时间复杂度为 $O(V+n\log V)$ 而空间复杂度是 $O(V)$ 的无法接受。

对于整数 $x,y$ 不存在 $i$ 使得 $x\le A_i\le y$，那么显然最后 $f_x$ 和 $f_y$ 的答案是一样的，那么我们考虑把这些一样的给塞到一起。

令 $Find(A_i)$ 为比 $A_i$ 大的最小的元素，那么考虑对以上的操作有什么影响：

显然把所有的数全部取反和计算所有 $f$ 的和 $S$ 是没有影响的，唯一影响的就是区间加 $S$ 操作。

对于区间加操作，原本的加 $S$ 就应该改成 $(Find(A_i)-i)\times S$。

考虑怎么初始化，显然应该有 $f_i=Find(A_i)-i$，时间复杂度为 $O(n\log n)$。

ARC074E RGB Sequence

完全没有见过的一种 DP 设法，设 $f_{i,j,k}$ 表示当前考虑到了第 $i$ 个位置，最靠近第 $i$ 个位置的颜色不一样的位置是 $j$，与 $a_i$ 和 $a_j$ 都不一样的最靠后的元素为位置为 $k$ 的方案数。

先不考虑限制，容易理解转移分别就是枚举三种情况：

• 选择与 $a_i$ 一样的颜色，那么有 $f_{i+1,j,k}\gets f_{i+1,j,k}+f_{i,j,k}$。
• 选择与 $a_j$ 一样的颜色，那么有 $f_{i+1,i,k}\gets f_{i+1,i,k}+f_{i,j,k}$。
• 选择与 $a_k$ 一样的颜色，那么有 $f_{i+1,i,j}\gets f_{i+1,i,j}+f_{i,j,k}$。

考虑把限制挂在右端点，那么对于一个要求 $(l,i,x)$ 就相当于对一些下标有一些要求：

• 如果 $x=1$，那么要求 $j,k<l$。
• 如果 $x=2$，那么要求 $j>l$，$k<l$。
• 如果 $x=3$，那么要求 $j,k>l$。

时间复杂度为 $O(n^3)$。