风格有点像 NOI2017,有送分题,但是并不很好写(不过似乎比去年 day2 游戏好写?)
今天发挥还不错,争取把分数稳定下来。
Tree
对于操作 1 ,用一个变量记录。
对于操作 2 ,对两点在原树上 $\text{lca}$ 的位置进行讨论。不妨设之为 $\text{lca_0}$ 。
分为以下情况:
- $\text{lca}$ 在新根 $\text{rt}$ 与 $1$ 的路径上
- $\text{lca}$ 在新根的子树里
- $\text{lca}$ 在除了上述之外的地方
对于 $1$ 我们可以用 $\textbf{lca(rt, lca}_0 \textbf{)= lca_o}$ 加以判定 ;
对于 $2$ 可以直接用 $\text{dfs}$ 序判断。
注意:
- 初始根为 $1$
- 注意特判 $\text{rt, lca}_0$ 是否重合
Or
有一个显然的DP就是,如果设状态 $dp[i][j]$ 表示考虑长度为 $i$ 的序列 $B_i$ 含有 $j$ 个 $1$ ,那么就有:
而由 $\sum_{i=1}^n \binom{n}{i} = 2^n$ 这个结论可以立刻知道: 考场写的暴力 NTT 是 $O(nk\lg k)$ 的,可以获得 $59$ 分。
考虑使用指数生成函数: 这可以用类似普通快速幂的倍增方法求出。即: 对于 $n$ 为奇数的情况暴力算一次就好了。
这样递归为什么就可以解决问题呢?$e^{2^i x}-1$ 到哪儿去了?在递归边界 $n = 1$ 里!
时间复杂度为 $O(k \lg n \lg k)$,可以通过。