标签：25 frac log 闲话 nB FFT 22.10 多项式 复杂度

闲话

今天又抱泠了（

文件：sandalphon*.in/out; lambentlight*.in/out; excalibur*.in/out
soytony：这种nb文件名直接敲错
我：这文件名显然是打不错的（

然后T2光荣地打成了lambertlight调了半个小时发现没有读入
回去一定要再看一遍刀剑

好耶生活水平大幅度提升

显摆显摆

だけど気付くだろう

豆色の空も

悪くはないななんて言うだろう

そんなものなのさ

この広い空ですら

关于多项式？

启发式合并多项式

考虑一类形如

\[f_{i,j} = \sum_{k=0}^j f_{i-1,j-k} g_k \]

的 dp 式子。我们需要求 \(f_{n,k}\)，其中 \(1\le k\le n\le 10^5\)。

比较平凡地构造 \(F_i(x) = \sum_{j=1}^{\infty} f_{i,j},G(x) = \sum_{i=1}^{\infty} g_i\)，于是在 dp 式两端关于 \(j\) 求和能得到 \(F_i(x) = F_{i-1}(x) * G(x)\)。

这个玩意可以直接多项式快速幂求 \([x^k](G(x))^n\) 得到。复杂度比较常识。

推广就得到了

\[f_{i,j} = \sum_{k=0}^j f_{i-1,j-k} g_{i-1,k} \]

然后对 \(G(x)\) 也整个下标就行了。一般而言 \(g\) 有意义的取值只有 \(O(n)\) 个，因此可以直接把 \(G_i(x)\) 乘起来，每次选两个度数最小的。启发式的复杂度不会证，当有 \(O(\sqrt n)\) 个多项式时似乎 \(O(n\log^2n)\) 的复杂度显然。其他情况不会证。没准证明能写社论（

这段其实是炒冷饭。具体看社论1009.

分治 FFT

考虑优化一下这个东西的复杂度。我们从压位 trie 那里得到灵感，试着将 FFT 的分治树拓展叉数。

考虑 \(B\) 叉的 FFT。

普通 FFT 需要让每个子树的值对后面的所有子树作贡献，因此我们需要对每个叉做 \(O(B)\) 次多项式乘法，每次是 \(\frac nB \log \frac nB\) 的复杂度，因此在每个点有 \(O(Bn\log \frac nB)\)。
递归式列出是

\[T(n) = B\times T(\frac nB) + O(Bn\log \frac nB) \]

得到 \(B=2\) 时最优。

你玩我呢？？！
先冷静，我们接着考虑。

我们真的需要对每两个子树算一次贡献吗？答案是不用。
我们可以直接把每个子树的多项式用点值方式存储，对于一个子树前面的各子树的贡献可以先存起来，最后用一次 FFT 转换就行了。由于两两贡献，我们需要统计每两个子树间的乘积，因此这部分是 \(O(B^2 \frac nB)\) 的。对于 \(G\) 的部分可以提前算出来，我们只需要做 \(O(B)\) 次多项式乘法。
总的来说需要 \(O(B\frac nB\log \frac nB + B^2 \frac nB) = O(nB + n\log \frac nB)\)

递归式列出是

\[T(n) = B\times T(\frac nB) + O(nB + n\log \frac nB) \]

得到 \(B=\log n\) 时最优，是 \(O(\frac {n \log n}{\log \log n})\) 的。

这个好（

skip2004说可以使用指令集科技，然后跑 4e6 的 exp 只需要 1.5s
我只想贺这份板子（

[实现先不放，我分治FFT没调出来]

标签：25,frac,log,闲话,nB,FFT,22.10,多项式,复杂度
From： https://www.cnblogs.com/joke3579/p/chitchat221025.html