peltorator

!OR-XOR-AND Свертки

Feb 22nd, 2018
171
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <map>
  5. #include <algorithm>
  6. #include <math.h>
  7. #include <string>
  8. #include <cstring>
  9. #include <set>
  10. #include <queue>
  11. #include <unordered_set>
  12. #include <complex>
  13. #include <unordered_map>
  14.    
  15. using namespace std;
  16.    
  17. typedef long long ll;
  18. typedef long double ld;
  19.  
  20. const int L = 17;
  21. const int N = (1 << L);
  22. const ll MOD = 1e9 + 7;
  23.  
  24. /*ll fib[N];
  25. ll cnt[N];
  26. ll cntab[N];
  27. ll cntc[N];*/
  28. vector<ll> fib, cnt, cntab, cntc, cntde;
  29.  
  30. ll binpow(ll x, ll y)
  31. {
  32.     if (!y)
  33.         return 1;
  34.     if (y % 2)
  35.         return (x * binpow(x, y - 1)) % MOD;
  36.     return binpow((x * x) % MOD, y / 2);
  37. }
  38.  
  39. ll revers(ll x)
  40. {
  41.     return binpow(x % MOD, MOD - 2);
  42. }
  43.  
  44. void adamar(vector<ll> &a, int l, int r)
  45. {
  46.     if (l + 1 >= r)
  47.         return;
  48.     int mid = (r + l) / 2;
  49.     adamar(a, l, mid);
  50.     adamar(a, mid, r);
  51.     for (int i = l; i < mid; i++)
  52.     {
  53.         ll u = a[i], v = a[i + mid - l];
  54.         a[i] = (u + v) % MOD;
  55.         a[i + mid - l] = (u - v) % MOD;
  56.     }
  57. }
  58.  
  59. void andamar(vector<ll> &a, int l, int r)
  60. {
  61.     if (l + 1 >= r)
  62.         return;
  63.     int mid = (r + l) / 2;
  64.     andamar(a, l, mid);
  65.     andamar(a, mid, r);
  66.     for (int i = l; i < mid; i++)
  67.         a[i] = (a[i] + a[i + mid - l]) % MOD;
  68. }
  69.  
  70. void revandamar(vector<ll> &a, int l, int r)
  71. {
  72.     if (l + 1 >= r)
  73.         return;
  74.     int mid = (r + l) / 2;
  75.     revandamar(a, l, mid);
  76.     revandamar(a, mid, r);
  77.     for (int i = l; i < mid; i++)
  78.         a[i] = (a[i] - a[i + mid - l]) % MOD;
  79. }
  80.  
  81. void ordamar(vector<ll> &a, int l, int r)
  82. {
  83.     if (l + 1 >= r)
  84.         return;
  85.     int mid = (r + l) / 2;
  86.     ordamar(a, l, mid);
  87.     ordamar(a, mid, r);
  88.     for (int i = l; i < mid; i++)
  89.         a[i + mid - l] = (a[i] + a[i + mid - l]) % MOD;
  90. }
  91.  
  92. void revordamar(vector<ll> &a, int l, int r)
  93. {
  94.     if (l + 1 >= r)
  95.         return;
  96.     int mid = (r + l) / 2;
  97.     revordamar(a, l, mid);
  98.     revordamar(a, mid, r);
  99.     for (int i = l; i < mid; i++)
  100.         a[i + mid - l] = (-a[i] + a[i + mid - l]) % MOD;
  101. }
  102.  
  103. vector<ll> xormult(vector<ll> a, vector<ll> b)
  104. {
  105.     adamar(a, 0, a.size());
  106.     adamar(b, 0, b.size());
  107.     for (int i = 0; i < a.size(); i++)
  108.         a[i] = (a[i] * b[i]) % MOD;
  109.     adamar(a, 0, a.size());
  110.     ll revn = revers(a.size());
  111.     for (int i = 0; i < a.size(); i++)
  112.         a[i] = (a[i] * revn) % MOD;
  113.     return a;
  114. }
  115.  
  116. vector<ll> ormult(vector<ll> a, vector<ll> b)
  117. {
  118.     ordamar(a, 0, a.size());
  119.     ordamar(b, 0, b.size());
  120.     for (int i = 0; i < a.size(); i++)
  121.         a[i] = (a[i] * b[i]) % MOD;
  122.     revordamar(a, 0, a.size());
  123.     return a;
  124. }
  125.  
  126. vector<ll> andmult(vector<ll> a, vector<ll> b)
  127. {
  128.     andamar(a, 0, a.size());
  129.     andamar(b, 0, b.size());
  130.     for (int i = 0; i < a.size(); i++)
  131.         a[i] = (a[i] * b[i]) % MOD;
  132.     revandamar(a, 0, a.size());
  133.     return a;
  134. }
  135.  
  136. int main()
  137. {
  138. //    freopen("in.txt", "r", stdin);
  139.     ios::sync_with_stdio(0);
  140.     int n;
  141.     cin >> n;
  142.     fib.assign(N, 0);
  143.     cnt.assign(N, 0);
  144.     cntab.assign(N, 0);
  145.     cntc.assign(N, 0);
  146.     cntde.assign(N, 0);
  147.     for (int i = 0; i < n; ++i)
  148.     {
  149.         int x;
  150.         cin >> x;
  151.         ++cnt[x];
  152.     }
  153.     fib[0] = 0;
  154.     fib[1] = 1;
  155.     for (int i = 2; i < N; ++i)
  156.         fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  157.     for (int i = 0; i < N; i++)
  158.     {
  159.         for (int j = i; j > 0; j = ((j - 1) & i))
  160.             cntab[i] = (cntab[i] + cnt[j] * cnt[i ^ j]) % MOD;
  161.         cntab[i] = (cntab[i] + cnt[0] * cnt[i]) % MOD;
  162.         cntab[i] %= MOD;
  163.     }
  164.     cntc = cnt;
  165.     /*ordamar(cntab, 0, N);
  166.     for (int i = 0; i < N; i++)
  167.         cntab[i] = (cntab[i] * cntab[i]) % MOD;
  168.     revordamar(cntab, 0, N);
  169.     adamar(cnt, 0, N);
  170.     for (int i = 0; i < N; ++i)
  171.         cntde[i] = (cnt[i] * cnt[i]) % MOD;
  172.     adamar(cntde, 0, N);
  173.     for (int i = 0; i < N; ++i)
  174.         cntde[i] = (cntde[i] * revers(N)) % MOD;*/
  175.     cntde = xormult(cnt, cnt);
  176.  
  177.     for (int i = 0; i < N; i++)
  178.     {
  179.         cntab[i] = (cntab[i] * fib[i]) % MOD;
  180.         cntc[i] = (cntc[i] * fib[i]) % MOD;
  181.         cntde[i] = (cntde[i] * fib[i]) % MOD;
  182.     }
  183.    /* andamar(cntab, 0, N);
  184.     andamar(cntc, 0, N);
  185.     andamar(cntde, 0, N);
  186.     for (int i = 0; i < N; ++i)
  187.         cntc[i] = ((cntc[i] * cntab[i]) % MOD * cntde[i]) % MOD;
  188.     revandamar(cntc, 0, N);*/
  189.     cntc = andmult(andmult(cntab, cntc), cntde);
  190.     ll ans = 0;
  191.     for (int i = 0; i < L; ++i)
  192.         ans = (ans + cntc[(1 << i)]) % MOD;
  193.     cout << (ans % MOD + MOD) % MOD;
  194.     return 0;
  195. }
RAW Paste Data