2024/04/07(#28)：用渗透的墨水来轻轻描绘

该卷卷了。

[CF293C] Cube Problem

Dino Bot 昨天的日推题。代码。

[Ynoi2011] ODT

Portal.

每个点维护一棵 Treap，然后只维护轻儿子的信息即可。

[CF715E] Complete the Permutations

Portal.

边可以分为四种类型，$a\rightarrow b,a\rightarrow 0,0\rightarrow b,0\rightarrow 0$。

记后三种边的数量为 $n_1,n_2,m$。$a\rightarrow 0$ 边有两种选择，融进 $0\rightarrow 0$，或者自我合并。方案数是：

$$F_1[k]=\sum\limits_{i=k}^{n_1}\dbinom{n_1}{i}\begin{bmatrix}i\\k\end{bmatrix}(n_1+m-i-1)^{\underline{n_1-i}}$$

$F_3$ 直接算第一类斯特林数，然后可以全排列 $m$。暴力卷即可。代码。

[AGC040F] Two Pieces

Portal.

代数推导天地灭。

考虑没有 $2$ 操作怎么做。为了避免重复计数，强制让 $a,b$ 距离 $\ge 1$（我们只区分操作时的位置，因此 $=0$ 的会在考虑 $2$ 操作时统计）。反射容斥做一下即可。

考虑加入操作 $2$。考虑枚举一次操作 $2$ 造成的移点贡献，也就是枚举最后一次进行操作 $2$ 时的 $k=x-y$，那么可以视作将终点拉到 $(A,B-k)$，将此视为新的格路。

将剩余的 $n-A-(B-k)-1$ 个 $3$ 操作分配到操作序列中，实际上是要给到 $k+1$ 个点（在它们身上进行 $3$ 操作），它们是直线 $y=x-d$（$d\in [0,k]$，$d>k$ 越过了之前钦定的最后一次 $3$ 操作）与新的格路的最后一个交点，只有最后一个交点是合法的，否则会有将 $y$ 坐标 +1 类的操作无法进行。分配之后，会将移动 $k$ 的贡献分摊掉。

特判 $A+B=n$ 的情况即可。代码。

L. Completely Multiplicative Function

Portal.

直接从小质数贪即可，不知道为什么是对（或者数据水）的。代码。