单位根相关一些内容？

。大概就是一些关于单位根相关的。（单位根反演？）

首先我们要计算多项式 \(\bmod (x^n-1)\) 。

那么我们对其进行类似 fft 的计算。 \[ \begin{aligned} \hat F(x)&=F(x)\bmod(x^n-1)\\ g_i=F(w_n^i),&[x^i]\hat F(x)=\frac{1}{n}\sum_{j\leq n-1}g_j\times w_{n}^{-ij} \end{aligned} \] 为什么这样做是对的呢？ \[ \begin{aligned} &&[x^k] \hat F(x)&=\sum_{i\leq n-1}w_n^{-ki}\sum_{j}f_j\times w_n^{ij}\\ &&&=\sum_{j}f_j\sum_{0\leq i<n}w_n^{(j-k)i}\\ &&&=\sum_{j}f_j[n|(j-k)] \end{aligned} \] 因为 \([n|m]=\frac{1}{n}\sum_{j<n}w_n^{jm}\)。

也就是循环卷积的形式。

---

当然模拟赛这个可以说很。。。。。。“我明明应该会的”。。。。

但是很不幸我并不会上一步。 \[ \begin{aligned} F(x)=(\prod_{0\le j<n}(1+x^j))^m\\ \hat g_i=\prod_{0\le j<n}(1+w_n^{ij}),g_i=\hat g_i^m\\ \end{aligned} \] 发现 \(ij\bmod n\) 可以拆成若干个环（整数mod n乘法群）。

设 \(\gcd(i,n)=c\)，则有如下计算式： \[ \begin{aligned} \hat g_i&=\prod_{ j|c}(1+w_n^{j})^{c}=\prod_{0\le j<n/c}(1+w_{n/c}^j)^c\\ x^n-1&=\prod_{0\le i<n}(x-w_n^i)=(-1)^n\times \prod_{0\le i<n}(w_n^i-x)\\ \hat g_{i}&=((-1)^{n/c}\times((-1)^{n/c}-1))^c \end{aligned} \] 当 \(2\mid (n/c),\hat g_i=0\),否则 \(\hat g_i=2^c\) .

实际上只需要知道 \(\gcd\) 相同的 \(g\) 相同足够了，，yhw一眼就看破了这个。。。。。。。 \[ \begin{aligned} \hat f_i=\sum_{j\le n}g_j\times w_{n}^{-ij}&=\sum_{c|n}g_c\sum_{j\le n}[\gcd(j,n)=c]\times w_n^{-ij}\\ &=\sum_{c|n}g_c\sum_{j\le n/c}[\gcd(j,n/c)=1]\times w_{n/c}^{-ij}\\ &=\sum_{c|n}g_c\sum_{j\le n/c}\sum_{t|n/c,t|j}\mu(t)\times w_{n/c}^{-ij}\\ &=\sum_{c|n}g_c\sum_{t|n/c}\mu(t)\sum_{t|j}\times w_{n/c}^{-ij}\\ &=\sum_{c|n}g_c\sum_{t|n/c}\mu(t)\sum_{j\le n/(tc)} w_{n/(tc)}^{-ij}\\ &=\sum_{T|n}\sum_{c|T}g_c\mu(T/c)\sum_{j\le n/T}w_{n/T}^{-ij}\\ &=\sum_{T|n}\sum_{c|T}g_c\mu(T/c)(n/T)[n/T|i] \end{aligned} \]