WC 2019 补题记录

WC 2019 补题记录。游记见此

提答题不想搞。

咕咕咕。。。

数树

LOJ/luogu

$\text{op} = 0$ 略。每个方案的贡献相当求红边蓝边均存在边意义下，$y ^ {连通块个数}$。

第一个结论

稍微有点经验的人可能会尝试类似枚举连通块的方式。然后无论如何都会遇到一个问题（我比赛时因为不知道这个问题直接打完暴力走人）：已经保证某些连通块连通，将这些块连接形成一棵树的方案数。

设每个连通块的大小为 $a_i$，数量为 $m$，总和 $\sum a_i = n$，则方案数为 $(\prod a_i) n^{m - 2}$。

可以感性证明：将每个连通块缩成点，然后类似于 prufer 序列，每次删去一个叶子连通块，并记录和这个连通块相连的点，这样可以形成长度为 $m - 2$ 的序列，每个位置可以任填，所以是 $n^{m - 2}$。删去一个连通块时，需要确定删去的边和哪个点连边，最后剩下的两个连通块之间的边也需要确定和哪个点连边，所以是 $\prod a_i$。

容斥？

搞定这个结论之后，看起来(?)道路光明很多。然后我们就可以通过一些方式搞出 $x$ 个连通块的方案，然后乘上贡献……但是显然存在将连通块连接时红蓝边重合的方案，还需要容斥。。。

但是注意到容斥的式子（令 $f_i$ 为 $i$ 个连通块相连的方案，$g_i$ 为连接后恰好有 $i$ 个连通块方案）：

$$g_i = \sum_{j \le i} f_j (-1)^{i - j} \binom{n - j}{n - i}$$

（特别注意一下组合数，因为我们在容斥的时候需要考虑的是边集的超集，而不是考虑连通块的子集。。。然后根据连通块个数和边的数量的关系搞一下）

那么答案是

\begin{align} &\quad \sum_{i = 1}^n g_i y^i \\ &= \sum_{i = 1}^n y^i \sum_{j \le i} f_j (-1) ^ {i - j} \binom{n - j}{n - i} \\ &= \sum_{j = 1}^n f_j (-1) ^{-j} \sum_{i \ge j} y^i (-1)^i \binom{n - j}{n - i} \\ &= \sum_{j = 1}^n f_j (-1) ^{-j} \sum_{i' = n - i, i \ge j} y^{n - i'} (-1)^{n - i'} \binom{n - j}{i'} \\ &= (-1)^n y^n \sum_{j = 1}^n f_j (-1) ^{-j} \sum_{0 \le i' \le n - j} y^{-i'} (-1)^{-i'} \binom{n - j}{i'} \\ &= (-1)^n y^n \sum_{j = 1}^n f_j (-1) ^{-j} \sum_{0 \le i' \le n - j} (-y^{-1})^{i'} \binom{n - j}{i'} \\ &= y^n \sum_{j = 1}^n f_j (-1) ^{n -j} (1 + (-y)^{-1})^{n - j} \\ &= y^n \sum_{j = 1}^n f_j (y^{-1} - 1)^{n - j} \\ &= y^n (y^{-1} - 1)^n \sum_{j = 1}^n f_j ((y^{-1} - 1)^{-1})^{j} \\ \end{align}

其实这给我们带来的启示是：有些容斥题，可以通过重定义贡献来避免容斥，比如说在这里贡献是一个和下标有关的幂次，就可以如此操作（其实题解中想表达的也是这个意思，只是直接通过二项式定理展开来构造）。

组合意义！- $\text{op} = 1$

当 $\text{op} = 1$ 时，$f_j = \sum_{\sum a_i = n, |a| = j} (\prod a_i) n^{j - 2}$。

答案就是

\begin{align} &\quad y^n (y^{-1} - 1)^n \sum_{j = 1}^n \sum_{\sum a_i = n, |a| = j} (\prod a_i) n^{j - 2} ((y^{-1} - 1)^{-1})^{j} \\ &= y^n (y^{-1} - 1)^n n^{-2} \sum_{j = 1}^n \sum_{\sum a_i = n, |a| = j} (\prod a_i) n^{j} ((y^{-1} - 1)^{-1})^{j} \\ &= y^n (y^{-1} - 1)^n n^{-2} \sum_{j = 1}^n \sum_{\sum a_i = n, |a| = j} \prod (a_i n (y^{-1} - 1)^{-1}) \\ &= y^n (y^{-1} - 1)^n n^{-2} \sum_{\sum a_i = n} \prod (a_i n (y^{-1} - 1)^{-1}) \\ \end{align}

相当于一个连通块的贡献是 $a_i n (y^{-1} - 1)^{-1}$。

显然有一个 $O(n^2)$ 的 DP：$f_{i, j}$ 表示 $i$ 子树内，$i$ 所在连通块大小为 $j$ 的贡献和。

利用 $\prod a_i$ 的组合意义（在每个连通块内选一个点！），可以变成 $O(n)$: $f_{i, 0/1}$ 表示 $i$ 子树内，是否选了一个点的贡献和。

多项式板子题 - $\text{op} = 2$

当 $\text{op} = 2$ 时，$f_j = \sum_{\sum a_i = n, |a| = j} (\prod a_i^{a_i - 2}) ((\prod a_i) n^{j - 2})^2 = \sum_{\sum a_i = n, |a| = j} (\prod a_i^{a_i}) n^{2j - 4}$。

答案就是

\begin{align} &\quad y^n (y^{-1} - 1)^n \sum_{j = 1}^n \sum_{\sum a_i = n, |a| = j} (\prod a_i^{a_i}) n^{2j - 4} ((y^{-1} - 1)^{-1})^{j} \\ &= y^n (y^{-1} - 1)^n n^{-4} \sum_{j = 1}^n \sum_{\sum a_i = n, |a| = j} (\prod a_i^{a_i}) n^{2j} ((y^{-1} - 1)^{-1})^{j} \\ &= y^n (y^{-1} - 1)^n n^{-4} \sum_{j = 1}^n \sum_{\sum a_i = n, |a| = j} \prod (a_i^{a_i} n^2 (y^{-1} - 1)^{-1}) \\ &= y^n (y^{-1} - 1)^n n^{-4} \sum_{\sum a_i = n} \prod (a_i^{a_i} n^2 (y^{-1} - 1)^{-1}) \\ \end{align}

相当于一个连通块的贡献是 $a_i^{a_i} n^2 (y^{-1} - 1)^{-1}$。

定义多项式 $F = \sum (i^i n^2 (y^{-1} - 1)^{-1}) \frac{x^i}{i!}$（带标号，EGF）。

答案就是 $[x^n]e^F n! y^n (y^{-1} - 1)^n n^{-4}$。

但是为什么我的多项式板子这么慢呢？code

远古计算机

LOJ/luogu

请用心感悟题解（逃）

I 君的商店

LOJ/luogu

感觉有许多询问的 pattern 想不到这道题就凉了（确实区分度很大）。
题目中每个条件都是有用的！

1. 全零方案不合法 $\rightarrow$ 最大值为 1。
2. 1 数量奇偶性 $\rightarrow$ 在小范围内特判。

Subtask 3 - 有序数组

根据条件 1，最大值为 1，那一定在数组的两端。

显然这个点是二分。我们试图找到一个单调的东西。（经过尝试）最后发现 $[f_i + f_{i + 1} > 1]$ 这个东西是单调的，而且不会受到等号的影响。

然后我们就得到了 $O(n \log n)$ 的做法：先排序，然后调用 Subtask 3。

(非集已经有 $31 + 21 + 13 + 9 = 74$ 分了！)

Subtask 5 - $7n + O(1)$

先 $2n$ 找最大值 1。

然后对于两个位置 $a, b$ 询问 $\{a, b\}, \{1\}$ 和 $\{a\}, \{b\}$。然后画一下表就发现对于 4 种 return 都已经能确定一个值了。

Subtask 6 - $5n + O(\log n)$

对于三个位置 $a, b, c$，询问 $\{a, b\}, \{c\}$ 和 $\{a\}, \{b\}$，发现当第一个返回 小于等于 的时候，已经能够确定 $a, b$ 其中一个的值了。

但是对于 大于等于 的情况，看似没有结论，但是却可以发现 $c$ 和 $a, b$ 其中一个的偏序关系。

然后我们会发现一条偏序关系链，调用 Subtask 3 即可。注意最后会有两个数无法确定，需要分讨。code