重要な観察として、以下の事実が成り立ちます。

\(\rm{ord_2}\) \((x)\) は、以下の条件を満たす正整数 \(k\) の個数に等しい。

• \(x \equiv 0 \mod 2^k\)

例えば、 \(40\) について \(1 \le k \le 3\) で条件が成り立ち、 \(\rm{ord_2}\) \((40)=3\) です。

これを利用して式変形をしてみましょう。

\(f(x,k)\) を次の通り定義します。

• \(f(x,k) = 1\) if \(x \equiv 0 \mod 2^k\)
• \(f(x,k) = 0\) otherwise

\(\displaystyle \sum_{i=1}^{N} \sum_{j=i+1}^{N} \rm{ord_2}\)\((A_i+A_j)\) \(=\) \(\displaystyle \sum_{i=1}^{N} \sum_{j=i+1}^{N} \sum_{k=1}^{\infty} f(A_i+A_j,k) = \sum_{k=1}^{\infty} \sum_{i=1}^{N} \sum_{j=i+1}^{N} f(A_i+A_j,k)\)

つまり、全ての正整数 \(k\) に対して \(A_i+A_j \equiv 0 \mod 2^k\) を満たす \((i,j) (i < j)\) の個数が求められればその和がこの問題の正解になります。(*)
また、 \(2 \le A_i+A_j \le 2 \times 10^9\) なので、 \(k \ge 31\) について \(\displaystyle \sum_{i=1}^{N} \sum_{j=i+1}^{N} f(A_i+A_j,k) = 0\) となります。

よって、 \(1 \le k \le 30\) について (*) が解ければよく、これは例えば連想配列 ( C++ においての map ) を利用して \(A_i \mod 2^k\) の値でバケットソートしながら求めることができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(auto &nx : a){
    cin >> nx;
  }
  long long res=0;
  for(int k=1;k<=30;k++){
    int md=(1<<k);
    map<int,int> mp;
    for(auto &nx : a){
      res+=mp[(md-(nx%md))%md];
      mp[nx%md]++;
    }
  }
  cout << res << "\n";
  return 0;
}