F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
MainBoard >> http://codeforces.com/contest/1010/problem/F
save_code @ 2018-07-27 20:48:18
[ Quote ] [ Edit ] [ Delete ] 1#
这道题 可以树链剖分+FFT

一个重链上的多项式 可以分解成 所有轻链多项式的卷积 记录这些多项式,他们的度数和不超过N*LG(N)

当一个点从重链变成轻链的时候 合并这些多项式 变成一个然后 添加到他的兄弟节点(肯定是重链节点) 多项式中

当然合并的话用到了分治+FFT 优先选择 SIZE最小的两个多项式合并
这个复杂度貌似也是N*LG(N)^3
save_code @ 2018-07-27 21:31:16
[ Quote ] [ Edit ] [ Delete ] 2#
好像可以推广到一般的树上
nzhtl1477 @ 2018-07-28 13:06:27
[ Quote ] [ Edit ] [ Delete ] 3#
这题怕是我一个同学出的原题。。
save_code @ 2018-07-28 14:58:41
[ Quote ] [ Edit ] [ Delete ] 4#
CF 照搬原题??管它反正卧没有做过
nzhtl1477 @ 2018-07-28 17:32:56
[ Quote ] [ Edit ] [ Delete ] 5#
orz save_code
[Top] [Previous Page] [Next Page]

HOME Back