2024/01/23(#12)：前往末日的旅行

又怎能得知。

最后剩下我 我什么都没有
末日的飞船 载着我的骨头

将自由和占有，摧毁得片甲不留。

[ARC106E] Medals

Portal.

直接将每个人拆成 $k$ 个点，向右部的二分出的答案天进行匹配，过不去。

发现我们要求完美匹配，所以直接 Hall 定理判断是否存在即可。代码。

[ARC106F] Figures

Portal.

枚举每个点的度数 $r_i$，可以计数：

$$\begin{aligned} Ans&=\sum_{\sum r_i=2n-2}\dfrac{(n-2)!}{\prod(r_i-1)!}\times \prod A_{d_i}^{r_i}\\ &=\sum_{\sum r_i=2n-2}(n-2)!\times \prod \frac{A_{d_i}^{r_i}}{(r_i-1)!} \end{aligned}$$

把后面那个东西写成 EGF，也就是说：

$$\begin{aligned} F_i(x) &= \sum_{k=0}^{\infty} \frac{A_{d_i}^k}{(k - 1)!}x^k \\ & = \sum_{k=0}^{\infty} \binom{d_i} k k \ x^k \\ & = d_i \sum_{k=1}^{\infty} \binom{d_i - 1} {k - 1}\ x^k \\ & = d_i x \sum_{k=0}^{\infty} \binom{d_i - 1} {k} \ x^k \\ & = d_i x (1 + x)^{d_i - 1} \end{aligned}$$

记 $S=\sum d_i$，那么：

$$\begin{aligned} Ans&= (n - 2)!\times [x^{2(n-1)}] \prod_{i=1}^nF_i(x)\\ &= (n - 2)!\times [x^{2(n-1)}] \prod_{i=1}^n d_i x (1 + x)^{d_i - 1}\\ &= (n - 2)!\times\prod_{i=1}^n d_i \times [x^{n - 2}] \prod_{i=1}^n (1 + x)^{d_i - 1} \\ &= (n - 2)!\times\prod_{i=1}^n d_i \times [x^{n - 2}] (1 + x)^{S - n} \\ &= (n - 2)!\times\prod_{i=1}^n d_i \times \binom{S - n}{n-2} \end{aligned}$$

[QOJ 4800] Oscar’s Round Must Have a Constructive Problem

Portal.

倒着构造，有不合法的直接 swap 一组即可。

[QOJ 4803] Candies

Portal.

令 $a_i>x/2$ 的变成 $x-a_i$，deque 模拟匹配即可。

[Ynoi E2024] TEST_133

Portal.

分块，每个块内正常维护历史最大 tag，然后再维护一下排序后的结果，每次查询的时候暴力二分一下，散块直接 pushdown 整块的标记。注意查询的整块没有重构，需要计算二分出的位置的历史最值。代码。

[QOJ 4807] Melborp Lacissalc

Portal.

先解决判定问题。做一遍模 $k$ 意义下的前缀和，然后组合数随便算一下即可。

因此可以直接对着前缀和数组进行 DP。设 $f_{i,j,k}$ 表示考虑前 $i$ 种数，放进了 $j$ 个位置，当前贡献为 $k$，直接跑即可。代码。