快速阶乘。这个都不会我怕不是废了。

首先看阶乘的形式可以变成一堆形如

的多项式的点值乘积。于是 \(v=\lfloor\sqrt n\rfloor\)，那么我们就要

的值。

考虑倍增处理问题。设 \(g_d=\prod_{i=1}^d(x+i)\)，那么我们最终需要的就是 \(g_v\) 的 前 \(v\) 项点值。我们知道 \(g_d\) 是个 \(d\) 次多项式，可以用 \(d+1\) 个点值表示。那么我们维护这些点值。

考虑如何倍增。我们发现

那么我们每次倍增使用一次连续点值平移求出 \(g_d(x)\) 的 \(2d+1\) 个点值，再使用一次连续点值平移求出 \(g_d(x+d)\) 的 \(2d+1\) 个点值，乘一下就行了。

不想写任意模数，于是去了 loj 交的。然而跑的贼慢。