『STA - R9』真空介电常数

考虑到 $\begin{aligned}res&=\sum_{k=1}^{n-1}\sin^{-2m}(\frac{ks}{n}\pi)\\&=\sum_{k=1}^{n-1}(\frac{e^{\frac{ks}{n}\pi i}-e^{\frac{-ks}{n}\pi i}}{2i})^{-2m}\\&=(-4)^m\sum_{k=1}^{n-1}(e^{\frac{ks i}{n}2\pi}+e^{\frac{-ks i}{n}2\pi}-2)^{-m}\\&=(-4)^m\sum_{k=1}^{n-1}(w_n^{ks}+w_n^{-ks}-2)^{-m}\end{aligned}$

由于 $\gcd(m,s)=1$, 有

不难发现其就是一个单位根反演的形式，然而 $k=0$ 的部分没有被定义。

于是可以考虑将分母加上某个函数，使得其在 $k=0$ 时取到一个非 $0$ 值，在 $k\in [1,n-1]$ 时都取 $0$，可以发现 $\frac{\sum_{i=1}^{n-1}w_{n}^{ki}}{n}$ 恰好满足这个条件。

于是可以将原式变为

，考虑到

由于对于所有 $x=w_n^k$, $(x+x^{-1}-2+\frac{\sum_{i=0}^{n-1}x^i}{n})^{-1}$ 均存在，所以 $(x+x^{-1}-2+\frac{\sum_{i=0}^{n-1}x^i}{n})^{-1}$ 在 $\bmod x^n-1$ 下是良定义的，由于多项式形式较为简单，可以直接转化为线性方程组线性消元做到 $O(n)$。

然后采用多项式快速幂即可计算 $(x+x^{-1}-2+\frac{\sum_{i=0}^{n-1}x^i}{n})^{-m}$ 在 $\bmod x^n-1$ 的取值，做到 $O(n\log n\log m)$ 的复杂度。