この記事ではものを偶数個や奇数個に分割する組合せ数の数え方について説明します。
正の整数 $N$ が与えられます。$N$ を互いに異なる正の整数に分割する方法であって、分割する整数の個数が偶数・奇数個であるものはそれぞれ何通りありますか？
例えば $11$ の互いに異なる正の整数への分割であって、整数の個数が偶数個であるものには $11 = 1 + 2 + 3 + 5$ などがあります。
偶数・奇数個に分割する組み合わせ数をそれぞれ $P_0, P_1$ と書きます。$P_0 + P_1$ は $N$ を互いに異なる正の整数に分割する組み合わせ数に等しく、以下のように表せます。
$\displaystyle P_0 + P_1 = [x^N]\prod_{i = 1}^\infty (1 + x^i)$
$P_0 - P_1$ を求めることが出来れば $P_0, P_1$ をそれぞれ求めることができます。ここで、以下の式が成り立ちます。
$\displaystyle P_0 - P_1 = [x^N]\prod_{i = 1}^\infty(1 - x^i)$
なぜなら、正の整数は $x^i$ に対応しているので、これを取った回数だけ係数の $-1$ が掛けられます。そのため偶数回とったものは正に、奇数回とったものは負になるので和はその差になります。
よって、答えは以下のように表されます。
$\displaystyle P_0 = \frac{1}{2}\left\{[x^N]\prod_{i = 1}^\infty(1+x^i) + [x^N]\prod_{i = 1}^\infty(1 - x^i)\right\}$
$\displaystyle P_1 = \frac{1}{2}\left\{[x^N]\prod_{i = 1}^\infty(1+x^i) - [x^N]\prod_{i = 1}^\infty(1 - x^i)\right\}$
総積の上限は $N$ までとして問題無いので、以下のテクニックを用いて $\Theta(N\log{N})$ で求められます。
$\prod (1 \pm x^{d_i}) \pmod{x^{N + 1}}$ in $O(N\log N)$ time
以下の等式が成り立ちます。
$\displaystyle \prod_{i = 1}^\infty (1 - x^i) = \sum_{n = -\infty}^\infty (-1)^nx^{\frac{n(3n - 1)}{2}}$
組合せ数の差だけを計算したい場合は、この式を用いれば $O(1)$ で求められます。
応用は色々作れると思います、とりあえずナップザック問題の類にはこのテクが使えそう。