[HeackerEarth] SPECIAL PAIRS

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : SPECIAL PAIRS 
Source            : HeackerEarth
Category          : Linear Algebra
Algorithm         : Fast Walsh-Hadamard transform 
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
typedef long long ll;  
  
static const int maxn = 1e5 + 5;  
static const int N    = 1 << 20;  
  
template <typename T> struct FWT  
{  
      void fwt(T io[], int n)  
      {  
            for (int d = 1; d < n; d <<= 1)  
            {  
                  for (int i = 0, m = d<<1; i < n; i += m)  
                  {  
                        for (int j = 0; j < d; j++)  
                        {  
                              T x = io[i+j], y = io[i+j+d];  
                              io[i+j] = x+y;  
                        }  
                  }  
            }  
      }  
      void ufwt(T io[], int n)  
      {  
            for (int d = 1; d < n; d <<= 1)  
            {  
                  for (int i = 0, m = d<<1; i < n; i += m)  
                  {  
                        for (int j = 0; j < d; j++)  
                        {  
                              T x = io[i+j], y = io[i+j+d];  
                              io[i+j] = x-y;  
                        }  
                  }  
            }  
      }  
      void self_convolution(T a[], int n)  
      {  
            fwt(a, n);  
            for (int i = 0; i < n; i++) a[i] = a[i] * a[i];  
            ufwt(a, n);  
      }  
};  
  
FWT <ll> fwt;  
ll ret[N+5], cnt[maxn];  
ll arr[maxn];  
  
int main()  
{  
      //freopen("in.txt", "r", stdin);  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            int n;  
            cin >> n;  
            for (int i = 0; i < n; i++)  
            {  
                  int x;  
                  cin >> x;  
                  ret[x]++;  
                  cnt[x]++;  
            }  
            fwt.self_convolution(ret, N);  
            ll ans = ret[0];  
            cout << ans << endl;  
            fill(begin(ret), end(ret), 0);  
            fill(begin(cnt), end(cnt), 0);  
      }  
}