题意
给定一棵树 \(T\),每次操作在某个点下方接上 \(k\) 个儿子。
询问期望多少次排列,使得 \(a_{fa_i} < a_i\)。
保证 \(k\) 是偶数,对 \(65536\) 取模。
\(n \le 10 ^ 5, k \le 2 \times 10 ^ 9\)。
Sol
考虑假如已经确定了一棵树的形态,如何求出最终的答案?
可以发现对于每一个节点考虑,她需要满足她在排列中的位置在她所有的子节点的前面。
所以每一个点满足限制的概率是 \(\frac{1}{siz_i}\) 的。
由于独立事件,期望为概率的倒数。
所以答案就是 \(\prod siz_i\)。
考察如何动态维护一棵树的 \(siz\)。
套路地,将询问离线下来,只考虑使用过的节点,建出类似虚树的东西。
现在每次操作变为在虚树上一条根到节点的链加,最后求所有 \(siz\) 的乘积。
这很明显是没法做的。
集中注意力,思考一些厉害的东西。把每个节点拆成 \((x + siz)\) 的形式,这样将所有点乘起来会变成一个长度为 \(n\) 的 \(\texttt{Poly}\),然后链加就变成 \(a_i \times (x + k)\) 的形式,最后把所有的 \(\texttt{Poly}\) 乘起来,答案就是次数为 \(0\) 的系数。
注意到模数就是 \(2 ^ {16}\),结合 \(2 | k\),发现一个很厉害的事情,我们只需要维护次数为 \([0, 15]\) 的系数就可以了,因为 \(2 | k\),对于次数 \(\le 16\) 的点,她一定不会对次数为 \(0\) 的点产生贡献,并且,假设当前点 \(i, i \ge 16\) 对 \([1, 15]\) 的点产生了贡献 \((2 \times p) ^ {i - j}\),可以发现次数为 \(i - j\) 的这个点再贡献一步到 \(0\),显然需要 \((2 \times p) ^ {j}\) 的贡献,这和之前的乘起来刚好就是 \((2 \times p) ^ i\),所以还是不对次数为 \(0\) 的点产生贡献。
至此做法已经十分显然了,对于线段树上每个节点维护长度为 \([0, 15]\) 的 \(\texttt{Poly}\),然后线段树在合并的时候就暴力乘,加 \(k\) 就直接用二项式定理暴力拆出来。
最后加上树剖的复杂度一共是 \(\log ^ 4\) 的,很难通过。
可以考虑把树剖+线段树换成 \(\texttt{lct}\),或者注意到查询时间复杂度为 \(O(1)\),直接开 \(n\) 颗线段树维护树剖上所有的链,这样都是 \(\log ^ 3\) 的。
标签:线段,YC322A,NOIP,siz,T4,texttt,times,次数,节点 From: https://www.cnblogs.com/cxqghzj/p/18321862