奇数\(m\)を用いて\(2^km\)と表される数は\(2^{k+1}\)を法として\(2^k\)と合同なので、\(A_j\)に対して\(A_i+A_j \ (i \leq j)\)が\(2\)でちょうど\(k\)回割り切れるものの総和は\(A_i ≡ 2^k-A_j \pmod{2^{k+1}}\)であるような\(A_i\)の総和がわかれば良いです。

公式解説と同様、\(A_i\bmod 2^k\)により\(A_i\)の総和と個数を管理することにより解けます。