「CNOI2019」Div2 Solution

## Solution of CNOI2019 Div2 ### A - 数学课 作为签到题，你只需要知道: $\sum_{i\le n} i^2=\frac{n(n+1)(2n+1)}{6}$ 就可以简单的推出答案为 $\frac{1}{2}*(1-\frac{3}{n*(n+2)})$ ### B - 数学作业 作为第二道签到题, 我们按位考虑一下. 假设第 $t$ 位有着 $a$ 个 $1$, $b$ 个 $0$. 这一位的贡献显然是: $2^t * 2^b *\sum_{2i+1 \le a}{{a}\choose{2i+1}}$ 根据二项式定理: $(1-1)^a=\sum_{i \le a}(-1)^i{{a}\choose{i}}=0$ 所以我们知道当 $a>0$ 时 $\sum_{2i \le a}{{a}\choose{2i}}=\sum_{2i \le a}{{a+1}\choose{2i+1}}=2^{a-1}$ 所以$t$的贡献为: $a=0$ 时 贡献为 $0$ , $a>0$ 时 贡献为 $2^{t+a+b-1}=2^{t+n-1}$ 所以最终答案为 所有数字**按位或**以后再乘上 $2^{n-1}$ 时间复杂度 $O(n)$ ### C - 青染之心 做过 HNOI2019 JOJO 的同学应该都知道把询问离线以后可以直接视作操作树上的背包( 虽然有这题idea比考 HNOI 早，但是出题人还是被鱼和JOJO送退役了 ). 然后考虑空间限制，我们把操作树重链剖分一下，先遍历轻儿子，保留每一层的背包数组，然后重儿子直接继承父亲的数组，可以证明最多只用保存 $log_2 n$ 层数组. 然后就可以做到 时间复杂度 $O(nV)$, 空间复杂度 $O(nlog_2V)$, 50000 的数据范围, 2500ms 轻松跑过. ### D - 雪松果树 显然可以使用 dfs序二分 或离线树上启发式合并做到 $O( n*log_2n )$ 但是这样是不能通过 $10^6$ 的数据的. 我们考虑询问离线，对于每个询问 在 dfs时 $O(1)$ 挂到 k-father 上，只需要记录一下自己到根节点的路径即可。 然后我们发现每个询问等价于查询一颗子树内某一个颜色的出现次数，我们可以建立dfs序然后直接差分 $O(1)$ 得到答案 总体时间复杂度 $O(n + q)$ ### E -雪松树之约 一道简单的题目. 10分显然的状压DP, 用矩阵优化可以获得 30分。 发现有效状态很少，便可以通过11的数据，即可获得50分。 然后发现循环同构的状态是等价的，于是合并起来即可 100分。