【题解】wc2019 简要题解

数树
题意：
U 为所有 $n$个点的树的集合
对于给定的两棵树 $S, T$, 定义 $F(S, T) = y^{公共的边数}$
Question1：给定 $n, S$，求 $\sum_{T\in U}F(S, T)$
Question2：给定 $n$, 求 $\sum_{S \in U, T\in U}F(S, T)$
做法:
我们可以把 $y^k$贡献拆掉，$y^k = (y-1+1) ^ k = \sum_{i=0}^{k} \binom{k}{i} (y-1)^i$
就转换成了选择一些边同时属于两棵树，贡献是 $y^{边数}$
对于 Question1，如果这些边把 S 划分成了 $m$个联通块，每个联通块大小是 $a_i$，利用 prufer 定理可以得到这个划分的数量是 $n^{m-2}\prod_{i=1}^{m} a_i$，考虑一下组合意义，相当于找到树上若干个联通块，然后每一个联通块选一个根，这部分写一个树形 dp 就好了
对于 Question2 也是类似的想法，也是先枚举一下边集，计算两棵树都包含这个边集的方案数
$$
\begin{split}
ans &= \sum_{m=0}^{n-1}y^{n-m}\sum_{\sum_{i=1}^{m}a_i=n}\frac{n!\prod_{i=1}^{m}\frac{a_i^{a_i-2}}{a_i!}}{m!}\times (n^{m-2}\prod_{i=1}^{m}a_i)^2 \\
&= n! \frac{y^n}{n^4} [x^n]\sum_{m=0}^{n-1} \frac {\left(\frac{n^2}{y} \sum_{j=1}^{n}\frac{j^j}{j!}x_j \right) ^m} {m!}
\end{split}
$$
写一个 exp 就好了（细节省略掉啦）

远古计算机
subtask1 题意理解点
subtask2 打表用 jmp 代替 if
subtask3 bfs 一下
subtask4 把图建出来网络流啊
subtask5 人类智慧易得他是一张网格图，所以构造一下就好了

I 君的商店
题意：
交互题
给定长度为 $n$的 0/1 序列 ${a}$，至少有一个 1，已知 1 个数的奇偶性， 定义一个集合 $S$的 value 为 $\sum_{i \in S} a_i$ ，每次可以问交互库两个集合，交互库会返回 value 大小关系，如果两个集合 value 相等，那么交互库就会自己返回一个数，目标为确定整个序列。
做法:
先介绍一个 7N 的做法。
2N 确定最大值 a，然后每一次找两个还没有确定的 x，y，询问 x+y 和 a 的关系，然后再询问 x 和 y，代价为 5N 确定 x，y 中的一个数。
前面的 2N 并不是必要的，subtask3 告诉我们，可以二分确定一条递增的链。
优化一下之前7N的做法，先随便找一个a，然后找两个还没有确定的x，y，询问x+y和a以及x和y，假设 $x \leq y$，如果 $x+y \leq a$，那么 $x = 0$，否则 $y \geq a$，这样 $y->a$就是找到的一条链。最后在这条链沿用 subtask3 的做法就好了。