coding_farmer_ac的博客

原因 在进行一串多项式相乘的操作时，时间复杂度将会爆掉 fft/nttfft/nttfft/ntt的时间复杂度是O(nlogn)O(nlogn)O(nlogn) 粗略计算一下，大脑过载问的gpt，gpt说是O(n∗m∗log(n+m))O(n*m*log(n+m))O(n∗m∗log(n+m)) 经验告诉我们1e5个长度小于10的多项式相乘也会爆， 于是有人说：长度很小？多项式快速幂启动！ 你ac了本题（），大概能把一个nnn干成lognlognlogn 但是没有更好的题目，只有更糟糕的数据，Time li

最近在学多项式,想起来一个月前写的一道拉格朗日,特来水贴。

codeforces传送门 luogu传送门 线段树优化建图+拓扑排序 zkw线段树优化建图模板 struct zkwSegtree_improve_graph { /* Author : atzk */ int n , N , rf , r2 , r4 ; vector < vector < pair < int , int > > > map ; zkwSegtree_improve_graph ( int n ) {