AtCoder Regular Contest 116 D - I Wanna Win The Game FPS解法

AtCoder Regular Contest 116 D - I Wanna Win The Game

https://atcoder.jp/contests/arc116/tasks/arc116_d

問題概要

長さ $N$ の整数列 $A$ であり、以下の条件を満たすものの個数は？

- $0 \le A_i (i=1, 2, \dots , N)$

- $\sum_{i=1}^N A_i=M$

- $A_1 xor A_2 xor \cdots xor A_N = 0$

FPSを使った解法

3つ目のxorの条件より、 $A_1$ ~ $A_N$ の第 $b$ ビット $(b=0,1,\dots)$ の $N$ 個のうち、 $1$ であるものは偶数個。また、第 $b$ ビットの和への寄与は $2^b$ である。

次数が和、係数がその個数となる多項式を考える。第 $b$ ビットに関する多項式 $f_b(x)$ は、 $1$ が $2i$ 個の時に対応する項が ${}_N C_{2i} x^{2i*2^b}$ なので、
$f_b(x) = \sum_i {}_N C_{2i} x^{2i*2^b}$
である。
よって、全ビット合わせた多項式は
$f(x)=\prod_b f_b(x)$
と表せる。 $[x^M]f(x)$ が答。