# $k$ の倍数次の係数和を求めるテク

$[x^k]f(x)$ で $f(x)$ の $k$ 次の係数を表すこととします。
多項式 $f(x)=\sum_{i=0}^n a_ix^i$ に対して $\sum_t [x^{kt}] f(x)$ を求めよ、という問題は頻繁に出題されます。

<br>

ここで、$k$ 乗してはじめて $1$ になるような複素数 $\zeta$ を取ります。このとき、重要な性質として $\sum_{i=0}^{k-1} \zeta^{ti}=\begin{cases}
k & (t \equiv 0 \bmod k) \\
0 & (\mbox{otherwise})
\end{cases}$ が分かります。これは $z^k-1$ の因数分解と等比数列の和の公式を用いればよいです。

<br>

よって $\sum_{i=0}^{k-1} f(\zeta^{i})=\sum_{i=0}^{k-1} \sum_{j=0}^n a_j\zeta^{ij}= \sum_{j=0}^n a_j\sum_{i=0}^{k-1}\zeta^{ij}=\sum_t a_{kt}\cdot k$ なので求めたいものは $\frac{\sum_{i=0}^{k-1} f(\zeta^{i})}{k}$ と変形できました。

### 例１
> 各要素が $[1,k-1]$ であるような長さ $N$ の数列で、総和が $k$ で割り切れるようなものは何通りあるか？

出典：||AGC052-C||

解法：||
総和を次数に対応づけたときの母関数は $f(x)=(\sum_{i=1}^{k-1} x^i)^N=(\frac{x^k-1}{x-1}-1)^N$ であり、$f(\zeta^i)=\begin{cases}
(k-1)^N & (i=0) \\
(-1)^N & (i \neq 0)
\end{cases}$ である。ゆえに与式は $\frac{(k-1)^N+(-1)^N \cdot (k-1)}{k}$ と分かる。
||

### 例２
> [1,2000]の整数の部分集合のうち、総和が5で割り切れる個数は？

出典：||[Youtube](https://youtu.be/bOXCLR3Wric)||

解法：||
総和を次数とする母関数は $\prod_{i=1}^{2000} (1+x^i)$ であるから、求めるものは $\frac{\sum_{j=0}^4 \prod_{i=1}^{2000} (1+\zeta^{ij})}{5}$ と書ける。
$\prod_{i=1}^{2000} (1+\zeta^{ij})$ は $j=0$ のとき $2^{2000}$ であり、$j \neq 0$ なら $\{\prod_{j=0}^4 (1+\zeta^j)\}^{400}$ と一致する。ここで恒等式 $z^5-1=\prod_{j=0}^4 (z-\zeta^j)$ に $z=-1$ を代入して整理すると $\prod_{j=0}^4 (1+\zeta^j)=2$ を得るので、答えは $\frac{2^{2000}+4\cdot 2^{400}}{5}$ 。
||

<br>

特に $k=2$ では $\zeta=-1$ なので式が簡単になり、競技プログラミング以外でも頻出の形となります。

### 例３
> 長さ $N$ の整数列 $(A_1,\ldots,A_N)$ について、要素を奇数個選ぶ方法のうち総和が $M$ となる通り数を $998244353$ で割った余りを求めよ。

出典：||ABC267-Ex||

解法：||
選んだ要素数を次数とする母関数は $f(x)=[y^M] \prod_{i=1}^N (1+xy^{A_i})$ である。求めるものは $\frac{f(1)-f(-1)}{2}$ であり、$f(x)$ に何かを代入したときの値は分割統治FFTによって高速に計算できる。
||

<br>

このテクニックは $f$ が多変数多項式でも効果を発揮します。

### 例４
> 長さ $10^6$ で要素が $13$ 以下の素数である組であって、総積が平方数となるものの個数を $\bmod 1000$ で求めよ。

出典：||OMC024-D||

解法：||
$10^6=2n$ と置くと、答えは $(a+b+c+d+e+f)^{2n}$ で各次数が偶数となる項の係数和である。各変数について順に上の変形を施すと、求めるべき値は $\frac{1}{2^6}\sum_{\{-1,1\}^6} (i+j+k+l+m+n)^{2n}=\frac{1}{64}\sum_{p=0}^6 \binom{6}{p}(2p-6)^{2n}=\frac{1}{32}(6^{2n}+6 \cdot 4^{2n}+15 \cdot 2^{2n})$ と分かる。あとはFermatの小定理・Eulerの定理などから計算できる。
||