公式解説 には以下の記述があります。

もとの問題の答えを \(f(S)\)，数列の要素を \(0,1\) に制限したときの問題の答えを \(g(S)\) とすると，二進数表記の桁ごとに考えれば \(f(1), \dots ,f(M)\) は \(g(1),\dots ,g(M)\) から計算量 \(O(M\log M)\) などで求められます．

これが自分には非自明に感じられたので、記述をします。

\(x\) に関する多項式 \(F, G, H\) を以下が成り立つように定義します。

• \([x^{a}]F(x) = f(a)\)
• \([x^{a}]G(x) = g(a)\)
• \([x^{a}]H(x) = \binom{N}{a}\)

このとき、以下の関係式が成り立ちます。

\[F(x) = [y^{1}]\prod_{i = 0}^{\infty}\left(H(x^{2^{i}} ) + 2^{i}yG(x^{2^{i}})\right)\]

これは、\([x^{a}]H(x)\) が、和が \(a\) になるように \(01\) を \(N\) 個選ぶ方法になっていることから成り立ちます。

上記の掛け算を \(i\) の昇順に行い、 \(2^{i}\) が \(M\) より大きくなったタイミングで打ち切ることで、 \(O(M\log(M)^{2})\) になります。

整数 \(b\) を \(2^{b}\leq M\) が成り立つ整数のうち最大のものとし、\(i = b, b - 1, \dots 0\) の順に掛け算を行うことを考えます。\(i = k\) のタイミングでの積のうち、\(M\) 次以下の項で、係数が非ゼロな項は非負整数 \(c\) を用いて \(c2^{k}\) 次と表せる項のみです。 よって、そのような項を圧縮して持つことで、考えるべき多項式の長さが \(O(\frac{M}{2^{k}})\) になります。

よって、 \(i\) の降順に計算することで、考えるべき多項式の長さの総和のオーダーが \(O(M)\) になるため、このパートの計算量は \(O(M\log{M})\) になります。