AGC 计数专题

1. AT_agc002_f [AGC002F] Leftmost Ball

序列问题，无大小关系，因此从左往右考虑。

由于同色球没有本质区别，所以每次可以往序列里加一个无色球或者直接把一种颜色的所有球丢到后面去。

为了不重复，钦定选定颜色的球的第二个（除去无色球的第一个）一定要放在当前序列的第一个空位。

即设 $f_{i,j}$ 表示放 $i$ 个无色球和 $j$ 种颜色。

$$f_{i,j}\leftarrow f_{i-1,j}+f_{i,j-1}\times (N-j+1){\mathrm{C}}_{NK-i-(j-1)(K-1)-1}^{K-2}$$

时空复杂度 $O(NK)$。

2. AT_agc012_d [AGC012D] Colorful Balls

有关两个球的，考虑寻找三个的性质，可以发现如果 $a,b,c$ 满足 $w_a+w_b\le X\wedge w_a+w_c\le X$，则 $a,b,c$ 可以任意交换，暴力连边会炸，容易想到都往最小的连边，时空复杂度 $O(n)$。

接着考虑异色球，一开始我只考虑每种颜色 $w$ 最小的，但是很有可能存在 $w_i+w_{min}>X$ 但是 $w_i+w_j\le Y$，本质问题是 $X,Y$ 是不相关的，所以不能用这种方法。

那么同同色考虑找一个“中转站”，显然可以找全局 $w$ 最小的作为中转站，但是这将导致最小的这种颜色不能转出去，因此还要找一个颜色与其不同的全局最小作为另一个中转站。

至此可以简单在对数时空内维护出所有连通块的信息，使用多重集排列即可。

3. AT_agc013_d [AGC013D] Piling Up

设 $f_{i,j}$ 表示考虑前 $i$ 次操作完成，目前箱子里还有 $j$ 个 R 的方案数，按照题意模拟转移即可，初始时 $f_{0,j}=1$。

但是由于不同的初始 $j$ 可能会导出相同的移出结果。由题目性质，对于每个时刻，箱子内剩的 R 个数（注意此值不是简单的 $j$）大于等于 $0$，若能取到 $0$，由转移方式可知这是相同的方案中 $j$ 最小的一个。所以考虑只保留这个方案，即 DP 时额外记一个 $0/1$ 状态标识有没有取到过 $0$，时空复杂度 $O(NM)$。

4. AT_agc022_e [AGC022E] Median Replace

对于连续段消除问题，考虑从左往右栈操作。

由于最后要保留 $1$，所以要尽可能的消去 $0$，考虑目前入栈的数。

• 若入栈的是 $0$。
  • 如果目前栈顶有两个 $0$，则可以三合一变为一个 $0$。
  • 如果目前栈顶只有一个 $0$，入栈等待下一个进来的再消，显然不会劣于带着栈内的 $1$ 一起删掉的情况。
  • 如果目前栈顶没有 $0$，也是等待不劣于带着栈顶的 $1$ 消去，因此直接入栈，变为栈顶为 $0$ 的情况。
• 若入栈的是 $1$。
  • 如果栈顶是 $0$，则这两个数直接消去，因为中位数只和接下来入栈的数有关。
  • 如果栈顶是 $1$，则保留。

经过分析，可以发现栈内只会是栈底一段连续的 $1$ 加上栈顶一段连续的 $0$，并且入栈的 $1$ 不会被消去，栈内同时最多存在 $2$ 个 $0$。考虑到若最终 $1$ 的个数 $\ge$ $0$ 的个数则合法，故只需用 DP 状态表示栈内 $0/1$ 的个数（$\in [0,2]$），统计方案数即可。

5. AT_agc023_e [AGC023E] Inversions

前置知识：有上限排列计数。

设共有 $S$ 个满足条件的排列，由于是满足条件的所有排列的所有逆序对，所以可以从排列的对称性入手。

若 $A_i\le A_j$，逆序对满足 $P_j<P_i\le A_i<A_j$，即要求将 $A_j$ 修改为 $A_i$ 后的 $\frac{1}{2}{S}^{\prime }$。

若 $A_i>A_j$，逆序对不好考虑，不逆序对满足 $P_i<P_j\le A_j<A_i$，即将 $A_i$ 修改为 $A_j$ 后的 $S-\frac{1}{2}{S}^{\prime }$。

已知 $S$ 接着考虑修改一个位置的 $S^{\prime }$ 怎么求，如将 $A_L$ 修改为 $A_R$（$A_L<A_R$）。设 $A_i$ 在 $A$ 中从小到大的排名为 $\mathrm{rk}(i)$，由有上限排列计数得每个位置的贡献只和 $\mathrm{rk}(i)$ 和 $A_i$ 有关，故修改相当于 $\mathrm{rk}(R)\to \mathrm{rk}(L)+1,A_R\to A_L$。接着 $\mathrm{\forall }\mathrm{rk}(i)\in (\mathrm{rk}(L),\mathrm{rk}(R))$ 的排名全部后移了一位，因此，可以将修改系数表述为

$$\begin{gathered} Q_{L,R}=(A_L-\mathrm{rk}(L))(\frac{1}{A_R-\mathrm{rk}(R)+1})\prod _{i=L+1}^{R-1}\frac{A_i-\mathrm{rk}(i)}{A_i-\mathrm{rk}(i)+1} \\ {S}^{\prime }=S{Q}_{L,R} \end{gathered}$$

$Q_{i,\ast }$ 可以用线段树维护，答案为：

$$\begin{array}{rl}S(\sum _{i<j,A_i\le A_j}\frac{1}{2}{Q}_{i,j}+\sum _{i<j,A_i>A_j}(1-\frac{1}{2}{Q}_{i,j}))& =S(\sum _{i<j}\frac{1}{2}{Q}_{i,j}+\sum _{i<j,A_i>A_j}1)\end{array}$$

后面的和号相当于 $A$ 的逆序对个数，使用 BIT 维护，前面的使用线段树扫描线。

6. AT_agc055_d [AGC055D] ABC Ultimatum

难以处理的 DP，考虑寻找其充要条件，充要条件可以从必要性入手，即考虑什么样的方案不合法。

从左往右考虑这个序列，可以发现在 CAB 和 BCA 中，C 总是在 A 前面，因此对于任意一个前缀，A 的数量 $x_A$ 减去 C 的数量 $x_C$ 不会超过 ABC 的数量 $x_{ABC}$，同理考虑剩下两个子串，又由在任意时刻 $x_A,x_B,x_C\le N$，$x_{ABC}+x_{BCA}+x_{CAB}\le N$，因此可以得到题意的一个必要条件。

通过题解区可以证明这个结论还具有充分性，所以可以开始 DP 设 $f_{i,a,b,c,ac,ba,cb}$ 表示上述值，其中 $c=i-a-b$ 一维可以优化掉，$ac,ba,cb$ 均为历史最大值，因为随着 $a,b,c$ 的变化之前存下的 ABC 可能丢失。