自动搬运

查看原文

来自洛谷，原作者为

	飞雨烟雁 尽管我们走不了最短路，但图仍是连通图，TLE之前，没有一个节点叫失败。

搬运于2025-08-24 23:14:09，当前版本为作者最后更新于2025-04-20 21:17:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

之前考虑系数提取时就想过用 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]$。