容斥原理

初来乍到，4h20min的题我打了2h，成功垫底，恭喜我自己 $\text{score：20 + 0 + 0 = 20 rk：26/27}$ Problen A题目描述 题解看他们都会写。。这种比较复杂的容斥我几乎都没写过。。 前置知识：高维前缀和举个例子，对比如现在要求解 $\sum\limits_{s = 0}^{2^n - 1}\sum\limits_{j \in s} a_j$（此处 $\in$ 是二进制表示下的意义），直接枚举子集是 $O (3^n)$ 的，那么高维前缀和可以优化到 $O (n2^n)$ 考虑低位前缀和，比如三位，我们是不是可以这么写 123456789101112for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) for (int k = 1; k <= n; k ++) a[i][j][k] += a[i - 1][j][k]for (int i = 1; i <= n; i ++) for (int j = 1; ...

Solution Ⅰ一道有点有趣的树形 $dp$ + 容斥，反正绕了我半天，这么神仙我也不可能写出来 首先考虑基本思路，直接求解恰好 $k$ 个较难，故考虑先求解大于等于 $k$ 的相似度的方案数，然后再容斥 考虑选定了必选的若干条边后计算方案数。显然此时整个图被分成了若干连通块，假设有 $k$ 个连通块，将连通块缩点，考虑它们可以组成的树的方案数，本来应该是 $k^{k - 2}$，然而对于每个连通块的缩点，它可以向其它连通块中包含的任意一点连接，也就是说，在 purfer 序列中，应当考虑连通块内的点编号在序列中的出现情况，而不是仅仅考虑连通块编号出现在序列中，故 prufer 序列中的每个位置可以填 $n$ 个数，即 $n^{k - 2}$，然而考虑了父亲，还需要考虑儿子，作为叶子节点的缩点后的连通块，同样的里面也是任意点向外连边，故还需乘上 $\prod size_i$，其中，$size_i$ 为连通块 $i$ 的大小，那么综上，对于一个存在 $k$ 个连通块的图，其构造的生成树的方案数为 $n^{k - 2} \times \prod size_i$ 那么现在考虑求解 $\p ...