A. coin

容易发现每种假钞的期望贡献是独立的。

对于每种假钞，做一个 $n^2$的 dp 求出来选择 $i$张假钞的贡献。

然后对这个贡献做一个背包就完事了。

考虑一个东西，就是对于每种假钞，只能选择一个数目加入背包的贡献中。

所以可以考虑对于每种假钞一张张加入贡献。

然后发现发现随着某种假钞的数量增加，期望增加量是不断减少的。

所以不断取最优策略进行更新就好了。

B. B

容易发现问题就是与给定树重合边数 $\geq n-1-k$ 的树的个数。

似乎是显然的变元矩阵树定理，然后搞个拉格朗日插值就完事了。

但是蒟蒻太菜了，所以思路比较清奇，发现这个玩意就是个二项式反演。

钦定一个边集，然后问题就转化为若干个连通块的生成树计数。

设有 $m$个连通块，然后每个连通块大小分别为 $size_i$，然后这个生成树个数有个结论就是 $n^{m-2} \prod \limits_{i=1}^m size_i$。

然后发现这个玩意的瓶颈就是如何钦定 $k$条边，考虑搞一个 dp。

显然对于那个 $n^{m-2}$ 可以把 $n$ 摊在每个连通块里乘上一个 $n$。

然后可以写一个简单的子树归并，$dp_{i,j,k}$ 表示 $i$ 子树中，钦定了 $j$ 条边，最后一个连通块有 $k$ 个点的总贡献。

转移的时候分钦定连在一起，不钦定那么给权值乘上一个 $n*k$ 就完事了。

分析一下复杂度，是 $O(n^4)$ 的。

然后考虑一下实际含义，这个乘 $size_i$ 其实就是对于每个连通块选择其中一个定为特殊点。

然后可以改一下 dp定义，$dp_{i,j,0/1}$ 表示 $i$ 子树中，钦定了 $j$ 条边，最后一个连通块是否选择了特殊点。

直接子树归并，复杂度就是 $O(n^2)$ 的了。

C. battery

考虑如果一个炮台能打到别的炮台，那么这个方向就结束了。

然后每个炮台有两个方向，要求就是 $a\ xor\ b=1$。

如果有 $k$ 个炮台钦定方向之后就能打到一个空地，那么要求就是 $x_1\ or x_2 \or x_3 \or x_{,,}=1$。

然后发现这个玩意就不会做了。

然而实际上并不存在 $k>2$ 个炮台都能打到一个空地的情况。

因为炮台不能相互打到的限制，每个空地的横向和纵向显然只能有一道射线能射过来。

然后问题就转化为了简单的 2-SAT 问题，写个 tarjan 就完事了。