各 \(k\) に対する

\[ c_k = \sum_{i+j = k} s_i \oplus t_j\ (s_i, t_j \in \{0, 1\}) \]

の計算に帰着するまでは他の解説と同様です。

公式解説のように \(s_i \oplus t_j = s_i(1 - t_j) + t_j(1-s_i)\) と変形することで畳み込み \(2\) 回で求めることができますが、畳み込み \(1\) 回で求めることもできます。

具体的には、\(s_i \oplus t_j = s_i + t_j - 2s_it_j\) と変形します。つまり、

\[ c_k = \sum_{i+j = k} (s_i + t_j - 2s_it_j) = \sum_{i+j = k} (s_i + t_j) - 2\times \sum_{i+j = k} s_it_j\]

と変形します。

右辺第 \(1\) 項は累積和を求めておくことで高速に計算でき、右辺第 \(2\) 項は畳み込みを用いることで計算できます。