大视野在线测评-欢迎您

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]