『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, 有

\sum_{k=1}^{n-1}(w_n^{ks}+w_n^{-ks}-2)^{-m}=\sum_{k=1}^{n-1}(w_n^k+w_n^{-k}-2)^{-m}

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

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

于是可以将原式变为

(-4)^m\sum_{k=0}^{n-1}(w_n^k+w_n^{-k}-2+\frac{\sum_{i=1}^{n}w_n^{ki}}{n})^{-m}-1

，考虑到

\begin{aligned}&\sum_{k=0}^{n-1}(w_n^k+w_n^{-k}-2+\frac{\sum_{i=1}^{n}w_n^{ki}}{n})^{-m}=n[x^0](x+x^{-1}-2+\frac{\sum_{i=0}^{n-1}x^i}{n})^{-m}(\bmod x^n-1)\end{aligned}

由于对于所有 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) 的复杂度。