多项式倍增
让你用lg的时间复杂度求下面这东西(n<1e18)
$$ \[\begin{aligned} &\prod_{i=1...n}{(2i-1)} \%2^{64}\\& suppose\quad that\quad f(x,n)=(2x+1)(2x+3)(2x+5)...(2x+2n-1)\%2^{64}\\& then \quad the \quad 0th \quad item \quad of \quad f(x,n) \quad is \quad answer\\& we \quad can \quad try \quad to\quad calculate \quad f(x,n) \quad by \quad f(x,\left \lfloor \frac{n}{2} \right \rfloor) \\& let \quad y=x+n\\& then \quad f(y,n)=(2y+1)(2y+3)(2y+5)...(2y+2n-1)\%2^{64}\\& so \quad f(x+n,n)=(2x+2n+1)(2x+2n+3)(2x+2n+5)...(2y+4n-1)\%2^{64}\\& Surprisedly \quad we \quad find \quad that \quad f(x,2n)=f(x,n)*f(x+n,n)\\& which \quad means \quad we \quad can \quad calculate\quad f(x,2n)\quad by\quad f(x,n) \quad easy\\& \\& becase \quad we \quad can \quad calculate \quad f(x+n,n)\quad by \quad f(x,n) \\& but \quad we \quad can't \quad calculate \quad it \quad faster \quad because\quad of\quad the\quad huge\quad numbers \quad of \quad item\\& considering \quad that \quad we \quad need \quad mod \quad 2^{64} , we\quad can \quad reserve \quad the \quad items \quad with \quad index \quad less\quad than\quad 64\\& because \quad the \quad useful \quad information \quad is \quad the \quad 0th \quad item \\& and \quad in \quad f(x,n)\quad when \quad the\quad index\quad of\quad x \quad is \quad larger \quad than\quad 63 ,the \quad coefficient \quad of \quad it \quad must\quad divisible\quad 2^{64}\\& it \quad has \quad no \quad contribution \quad to \quad answer \quad and \quad f(x+n,n)\\& so \quad we \quad can \quad solve \quad it \quad by \quad this \quad way \\& for \quad every \quad polynomial \quad we \quad reserve\quad the \quad first \quad 64\quad items \quad of\quad x \\& and \quad then \quad calculate \quad f(x,n) \quad by \left\{\begin{matrix} \quad f(x,\left \lfloor \frac{n}{2} \right \rfloor)*f(x+\left \lfloor \frac{n}{2} \right \rfloor,\left \lfloor \frac{n}{2} \right \rfloor)\quad if \quad n\%2=0\\& \quad f(x,\left \lfloor \frac{n}{2} \right \rfloor)*f(x+\left \lfloor \frac{n}{2} \right \rfloor,\left \lfloor \frac{n}{2} \right \rfloor)*(2x+2n-1) \quad if \quad n\%2=1 \end{matrix}\right. \\& and \quad we \quad can \quad get \quad the \quad answer \quad no \quad more \quad than \quad lg \quad times \quad recursion\\& because \quad of \quad the \quad 64 \quad items \quad only \quad and \quad we \quad don't\quad care \quad the \quad higher \quad items ,\\& it \quad is \quad very \quad fast \quad to \quad get \quad f(x,n)\quad by \quad f(x+n,n) \\& so\quad the\quad total\quad time\quad complexity \quad is \quad O(lgn) \end{aligned}\]$$
假设f(x,n)=(2x+1)(2x+3)(2x+5)...(2x+2n-1)%64
然后这东西的0次项系数就是答案
我们尝试通过f(x,n/2)来求f(x,n)
令y=x+n
则f(y,n)=(2y+1)(2y+3)(2y+5)...(2y+2n-1)%64
所以f(x+n,n)=(2x+2n+1)(2x+2n+3)(2x+2n+5)...(2x+4n-1)%64
我们惊讶地发现了f(x,2n)=f(x,n)*(fx+n,n)
这意味着我们可以通过f(x,n)来求f(x,2n)因为我们可以通过f(x,n)求出f(x+n,n)
很遗憾的是这些东西项数太多了
考虑到我们要的是模上2^64的答案，我们可以只保留前64项
因为有用的只有0次项，但是在f(x,n)转移到f(x+n,n)的时候也只有前64项有效，因为大于指数64的项，他们前面的系数一定整除2^64次方，
于是我们就有了做法了
我们保留前64项
...
时间复杂度为lg级别