[Codechef] Pairwise AND sum

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Pairwise AND sum 
Source            : Codechef 
Category          : Linear Algebra
Algorithm         : Fast Walsh-Hadamard transform 
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define ll        long long  
6.  
7. static const int MAXN = 1e5 + 5;  
8. static const int N    = 1<<20;  
9.   
10. template <typename T> struct FWT  
11. {  
12.       void fwt(T io[], int n)  
13.       {  
14.             for (int d = 1; d < n; d <<= 1)  
15.             {  
16.                   for (int i = 0, m = d<<1; i < n; i += m)  
17.                   {  
18.                         for (int j = 0; j < d; j++)  
19.                         {  
20.                               T x = io[i+j], y = io[i+j+d];  
21.                               io[i+j] = x+y;  
22.                         }  
23.                   }  
24.             }  
25.       }  
26.       void ufwt(T io[], int n)  
27.       {  
28.             for (int d = 1; d < n; d <<= 1)  
29.             {  
30.                   for (int i = 0, m = d<<1; i < n; i += m)  
31.                   {  
32.                         for (int j = 0; j < d; j++)  
33.                         {  
34.                               T x = io[i+j], y = io[i+j+d];  
35.                               io[i+j] = x-y;  
36.                         }  
37.                   }  
38.             }  
39.       }  
40.       void self_convolution(T a[], int n)  
41.       {  
42.             fwt(a, n);  
43.             for (int i = 0; i < n; i++) a[i] = a[i] * a[i];  
44.             ufwt(a, n);  
45.       }  
46. };  
47.   
48.   
49. ll bruteforce(ll a[], int n)  
50. {  
51.       ll sum = 0;  
52.       for (int i = 0; i < n; i++)  
53.       {  
54.             for (int j = i+1; j < n; j++)  
55.             {  
56.                   sum += a[i] & a[j];  
57.             }  
58.       }  
59.       return sum;  
60. }  
61.   
62. FWT <ll> fwt;  
63. ll ret[N+5], cnt[N+5];  
64. ll arr[MAXN];  
65.   
66. int main()  
67. {  
68.       //freopen("in.txt", "r", stdin);  
69.   
70.       int n;  
71.       scanf("%d", &n);  
72.       for (int i = 0; i < n; i++)  
73.       {  
74.             scanf("%lld", &arr[i]);  
75.       }  
76.       if (n <= 1000)  
77.       {  
78.             printf("%lld\n", bruteforce(arr, n));  
79.             return 0;  
80.       }  
81.       for (int i = 0; i < n; i++)  
82.             ret[ arr[i] ]++, cnt[ arr[i] ]++;  
83.   
84.       fwt.self_convolution(ret, N);  
85.       ll sum = 0;  
86.       for (int i = 1; i < N; i++)  
87.             sum += ((ret[i] - cnt[i])>>1)*i;  
88.       printf("%lld\n", sum);  
89. }