P12265 题解 / Chebyshev 多项式

· · 题解

之前考虑系数提取时就想过用 Bostan-Mori 算法提取 \log P(x) 的远端系数，赛时看到了相同的 idea，就做了一下，结果拿下了唯一一杀。

首先因为 \gcd(s,n)=1，ks 必然遍历 1,2,\cdots,n-1，可以不管，即不妨设 s=1。

记 s_k=\sin(k\pi /n)^2，则

\sum_{k=1}^{n-1}s_k^{-m}=[x^{m-1}]\left(\sum_{k=1}^{n-1}\frac{1/s_k}{1-x/s_k}\right).

记 F(x)=\prod_{k=1}^{n-1}(1-x/s_k)，做通分后有

\sum_{k=1}^{n-1}s_k^{-m}=[x^{m-1}]\frac{-F'(x)}{F(x)}.

那么，只要我们求出了 F(x)，就能用 Bostan-Mori 算法在 \Theta(n\log n\log m) 的时间内求出答案。

不同于官方题解，我们这里从 Chebyshev 多项式的角度出发，推导 F(x) 的表达式。

记 G(x)=\prod_{k=1}^n(x-s_k)（注意连乘上限为 n），则 F(x)=G(x)/[G'(0)x]，下求 G(x)。

采用二倍角公式，有

\begin{aligned}G(x)&=\prod_{k=1}^n\left(x-\sin^2\frac{k\pi }n\right)\\&=\prod_{k=1}^n\left(x-\frac 12+\frac 12\cos\frac{2k\pi}{n}\right).\end{aligned}

这表明若定义 H(x)=\prod_{k=1}^n(x-\cos\frac{2k\pi}{n})，则

G(x)=\left(-\frac 12\right)^nH(1-2x).

而 H(x) 是存在通项的，可以写为

H(x)=-2^{1-n}+n\sum_{t=0}^{n/2}\dfrac{(n-t-1)!}{t!(n-2t)!}\left(-\frac {1}4\right)^{t}x^{n-2t}.

证明请见 数学杂记【101 - 115】第 113 条，或见下文附录。

这样我们只需预处理组合数，然后做一次多项式平移就可以求出 F(x) 了。

此题比较卡常，实现 Bostan-Mori 算法时可以采用 这篇 Blog 的优化。或者考虑递归到 m<n 时，令 n=\min\{n,m\}，这样做的时间复杂度为 \Theta(n\log n\log (m/n))，常数大约可减少 25\% 左右。

附录：

记 \omega_n=\exp(2\pi i/n)，熟知 x^n-1=\prod_{k=1}^n(x-\omega_n^k)。我们凑出共轭形式：

\begin{aligned}(x^n-1)^2&=\prod_{k=1}^n(x-\omega_n^k)\prod_{k=1}^n(x-\omega_n^{-k})\\&=\prod_{k=1}^n\left(x^2+1-2\cos \frac{2\pi k}n{x}\right)\\&=(2x)^n\prod_{k=1}^n\left(\dfrac{x^2+1}{2x}-\cos \frac{2\pi k}n\right).\end{aligned}

于是有：

\begin{aligned}\prod_{k=1}^n\left(x-\cos\frac{2k\pi}{n}\right)&=2^{-n}(x^n+x^{-n}-2)\circ \left(\frac{x^2+1}{2x}\right)^{\!\left<-1\right>}\\&=2^{-n}(x^n+x^{-n}-2)\circ (x+\sqrt {x^2-1}).\end{aligned}

我们可以继续做推导，得到它各项系数的表达式：

\begin{aligned}\prod_{k=1}^n\left(x-\cos\frac{2k\pi}{n}\right)&=2^{1-n}\left[-1+\sum_{k}\binom{n}{2k}x^{n-2k}(x^2-1)^k\right]\\&=2^{1-n}\left[-1+\sum_{k,t}\binom{n}{2k}\binom{k}{t}x^{n-2k+2t}(-1)^{k-t}\right]\\&=2^{1-n}\left[-1+\sum_{t}x^{n-2t}(-1)^{t}\sum_k\binom{n}{2k}\binom{k}{t}\right].\end{aligned}

后面这个和式在这个问题中也出现过，我们的做法是生成函数 + 转回和式。

\begin{aligned}\sum_k\binom n{2k}\binom kt&=[x^n](1+x)^n\frac{x^{2t}}{(1-x^2)^{t+1}}\\&=[x^{n-2t}]\frac{(1+x)^{n-t-1}}{(1-x)^{t+1}}\\&=\sum_{k}\binom{k+t}{k}\binom{n-t-1}{n-2t-k}\\&=\dfrac{(n-t-1)!}{t!(n-2t)!}\sum_{k}(k+t)\binom{n-2t}{k}\\&=\dfrac{(n-t-1)!}{t!(n-2t)!}n2^{n-2t-1}.\end{aligned}

代入上式即可。这个多项式也可以用 Chebyshev 多项式表示，即 \prod_{k=1}^n(x-\cos\frac{2k\pi}{n})=2^{1-n}[T_n(x)-1]。