Advertisement
Guest User

Vida de Corno Mole da Desgraça

a guest
Mar 22nd, 2019
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAX 1 << 17
  3. #define LOGN 17
  4. #define MOD 1000000007
  5.  
  6. using namespace std;
  7. typedef long long ll;
  8.  
  9. vector<ll> ORANDO(vector<ll> &a) {
  10.     vector<ll> ans(MAX, 0LL);
  11.     for (int i = 0; i < MAX; i++){
  12.         for (int j = i; j >= 0; j = (j-1)&i){
  13.             ll mult = (a[i^j]*a[j])%MOD;
  14.             ans[i] = (ans[i] + mult)%MOD;
  15.             if(j == 0) break;
  16.         }
  17.     }
  18.  
  19.     return ans;
  20. }
  21.  
  22. int T[3][2][2][2] = {
  23.     { { {1,  1}, {1, -1} }, { {1,  1}, {1, -1} } }, /// xor
  24.     { { {0,  1}, {1,  1} }, { {-1, 1}, {1,  0} } }, /// and
  25.     { { {1,  1}, {1,  0} }, { {0,  1}, {1, -1} } }  /// or
  26. };
  27.  
  28. void FFT(vector<ll> &a, int op, bool inverse = false) {
  29.     ll u1 = T[op][inverse][0][0], v1 = T[op][inverse][0][1];
  30.     ll u2 = T[op][inverse][1][0], v2 = T[op][inverse][1][1];
  31.  
  32.     for(int b = 0; b < LOGN; b++)
  33.         for(int i = 0; i < MAX; i++)
  34.             if((i & (1 << b)) == 0) {
  35.                 ll u = a[i], v   = a[i + (1 << b)];
  36.                 a[i] = (u*u1) + (v*v1);
  37.                 if(a[i] < 0) a[i] += MOD;
  38.                 if(a[i] >= MOD) a[i] -= MOD;
  39.  
  40.                 a[i + (1 << b)] = (u*u2) + (v*v2);
  41.                 if(a[i + (1 << b)] < 0) a[i + (1 << b)] += MOD;
  42.                 if(a[i + (1 << b)] >= MOD) a[i + (1 << b)] -= MOD;
  43.             }
  44.  
  45.     if (op == 0 && inverse)
  46.         for (int i=0; i<a.size(); i++)
  47.             a[i] >>= LOGN;
  48. }
  49.  
  50. /// op is 0 for XOR, 1 for AND, 2 for OR
  51. vector<ll> convolution(vector<ll> a, vector<ll> b, int op) {
  52.     FFT(a, op, false);
  53.     FFT(b, op, false);
  54.     for(int i=0; i<a.size(); i++)
  55.         a[i] = (a[i] * b[i])%MOD;
  56.     FFT(a, op, true);
  57.     return a;
  58. }
  59.  
  60. ll fibo[MAX];
  61. void build(){
  62.     fibo[1] = 1LL;
  63.     for(ll i = 2LL; i < MAX; i++) fibo[i] = (fibo[i-1]+fibo[i-2])%MOD;
  64. }
  65.  
  66. void print(vector<ll> &a, int sz){
  67.     for(int i = 0; i < sz; i++) cout << a[i] << " ";
  68.     cout << endl;
  69. }
  70. int main(){
  71.     int n; scanf("%d", &n);
  72.     vector<ll> arr(MAX, 0LL);
  73.     for(int i = 0; i < n; i++){
  74.         ll x;scanf("%lld", &x);
  75.         arr[x] += 1LL;
  76.     }
  77.  
  78.     build();
  79.     vector<ll> oris = ORANDO(arr);
  80.     vector<ll> xoris = convolution(arr, arr, 0); // RIP XORIS
  81.    
  82.     for(int i = 0; i < oris.size(); i++) oris[i] = (fibo[i]*oris[i])%MOD;
  83.     for(int i = 0; i < xoris.size(); i++) xoris[i] = (xoris[i]*fibo[i])%MOD;
  84.     for(int i = 0; i < arr.size(); i++) arr[i] = (fibo[i]*arr[i])%MOD;
  85.  
  86.     vector<ll> andis = convolution(oris, arr, 1);
  87.     vector<ll> ans = convolution(andis, xoris, 1);
  88.  
  89.     ll resp = 0LL;
  90.     for(ll i = 1LL; i < (1 << 17); i *= 2LL) {
  91.         if(ans[i] != 0) resp = (resp+ans[i])%MOD;
  92.     }
  93.     printf("%lld\n", resp);
  94.     return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement