XSY4363

有生成函数 $$f(x,y)=\prod_{0\le i<n}(1+x^iy)$$ $$\begin{aligned} \text{Ans}=&[y^m]\sum_{i\bmod n = k}[x^i]f(x,y) &\\ =&[y^m]\frac{1}{n}\sum_{0\le i<n}f(\omega_n^i,y)\omega_n^{-ik} &\text{单位根反演}\\ =&[y^m]\frac{1}{n}\sum_{0\le i<n}\left(\prod_{0\le j<n}1+y\times\omega_n^{ij}\right)\omega_n^{-ik} & \end{aligned}$$

定理1：$\omega_n^i=\omega_{\frac{n}{(n, i)}}$

[object Promise]

推论：$\omega_{nk}^{ik}=\omega_{\frac{kn}{k(n,i)}}=\omega_{\frac{n}{(n,i)}}=\omega_n^i$

$$\begin{aligned} \text{Ans}=&[y^m]\frac{1}{n}\sum_{0\le i<n}\left(\prod_{0\le j<n}1+y\times\omega_{\frac{n}{(n,i)}}^j\right)\omega_n^{-ik} &\text{定理1}\\ =&[y^m]\frac{1}{n}\sum_{0\le i<n}\left(\prod_{0\le j<\frac{n}{(n,i)}}1+y\times\omega_{\frac{n}{(n,i)}}^j\right)^{(n,i)}\omega_n^{-ik} &\\ =&[y^m]\frac{1}{n}\sum_{d\mid n}\left(\prod_{0\le j<\frac{n}{d}}1+y\times\omega_{\frac{n}{d}}^j\right)^{d}\sum_{\begin{aligned}0\le i<n\\(n,i)=d\end{aligned}}\omega_n^{-ik} &\\ \end{aligned}$$

定理2：$\prod\limits_{0\le i<n}x+y\times\omega_n^i=x^n-(-y)^n$

[object Promise]

$$\begin{aligned} \text{Ans}=&[y^m]\frac{1}{n}\sum_{d\mid n}\left(1-(-y)^{\frac{n}{d}}\right)^{d}\sum_{\begin{aligned}0\le i<n\\(n,i)=d\end{aligned}}\omega_n^{-ik} &\text{定理2}\\ =&[y^m]\frac{1}{n}\sum_{d\mid n}\left(1-(-y)^d\right)^{\frac{n}{d}}\sum_{\begin{aligned}0\le i<n\\(n,i)=\frac{n}{d}\end{aligned}}\omega_n^{-ik} &\\ =&\frac{1}{n}\sum_{d\mid (n,m)}(-1)^{\frac{m}{d}}\begin{pmatrix}\frac{m}{d}\\\frac{n}{d}\end{pmatrix}\sum_{\begin{aligned}0\le i<n\\(n,i)=\frac{n}{d}\end{aligned}}\omega_n^{-ik} &\text{二项式定理}\\ =&\frac{1}{n}\sum_{d\mid (n,m)}(-1)^{\frac{m}{d}}\begin{pmatrix}\frac{m}{d}\\\frac{n}{d}\end{pmatrix}\sum_{\begin{aligned}0\le i<d\\(d,i)=1\end{aligned}}\omega_d^{-ik} &\text{推论} \end{aligned}$$

$$\begin{aligned} \sum_{0\le i<d\\(d,i)=1}\omega_d^{-ik}=& \sum_{0\le i<d}\omega_d^{-ik}\sum_{x\mid (d,i)}\mu(x) &\\ =&\sum_{x\mid d}\mu(x)\sum_{0\le i<\frac{d}{x}}\omega_d^{-ixk} &\\ =&\sum_{x\mid d}\mu(x)\sum_{0\le i<\frac{d}{x}}\omega_{\frac{d}{x}}^{-ik} &\text{推论}\\ =&\sum_{x\mid d}\mu(x)\times \frac{d}{x}[\frac{d}{x}\mid k] &\\ =&\sum_{x\mid (d,k)}\mu(\frac{d}{x})\times x &\\ \end{aligned}$$

$$\text{Ans}=\frac{1}{n}\sum_{d\mid (n,m)}(-1)^{\frac{m}{d}}\begin{pmatrix}\frac{m}{d}\\\frac{n}{d}\end{pmatrix}\sum_{x\mid (d,k)}\mu(\frac{d}{x})\times x$$

如果不考虑大组合数的话可以做到 $\mathcal{O}(\sigma_0(n))$ 组合数分块打阶乘表即可