fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. /**------------------------------------------
  4. ---------Author: PhcKhnhTapCode -------------
  5. ---------From: CHV with luv <3 --------------
  6. ---------Training To Win Voi 25 !!! --------- 
  7. ---------------------------------------------
  8. ------------------MemoryLimitExeeded<ooo>-**/
  9.  
  10. using namespace std;
  11.  
  12. #ifdef phckhnh_local
  13.    #include "D:\Users\AdminTCT\Desktop\CP\debug.h"
  14. #else
  15.    #define debug(...) 0
  16. #endif
  17.  
  18. #define ll long long
  19. #define db long double
  20. #define fi first
  21. #define se second
  22. #define ii pair<int,int>
  23.  
  24. #define vi vector<int>
  25. #define vii vector<ii>
  26. #define vvi vector<vi>
  27. #define vvvi vector<vvi>
  28. #define pub push_back
  29. #define all(v) v.begin(),v.end()
  30.  
  31. #define mid(l, r) ((l + r) >> 1LL)
  32. #define left(id)  (id << 1LL)
  33. #define right(id) ((id << 1LL) | 1LL)
  34.  
  35. #define Mask(i) (1LL << (i))
  36. #define Onbit(n, i) (n | Mask(i))
  37. #define Ofbit(n, i) (n ^ Mask(i))
  38. #define Bit(n, i) ((n >> (i)) & 1LL)
  39. #define Log2(n) (63 - __builtin_clzll(n))
  40. #define powbit(n) __builtin_popcountll(n)
  41.  
  42. #define FOR(i, a, b)  for (int i = a; i <= b; ++i) 
  43. #define FOD(i, b, a) for (int i = b; i >= a; --i)
  44. #define rep(i, n)  for (int i = 0; i < n; ++i)
  45. #define repd(i, n) for (int i = n - 1; ~i;--i)
  46. #define repv(v, H) for (auto &v: H)
  47.  
  48. template <class T> bool maximize(T &A, const T &B) {if(A < B) {return A = B, true;} return false;}
  49. template <class T> bool minimize(T &A, const T &B) {if(A > B) {return A = B, true;} return false;}
  50.  
  51. namespace std {
  52.     template <int D, typename T> struct Vec : public vector<Vec<D - 1, T>> {
  53.         static_assert(D >= 1, "Dimension must be positive");
  54.         template <typename... Args>
  55.         Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
  56.     };
  57.  
  58.     template <typename T> struct Vec<1, T> : public vector<T> {
  59.         Vec(int n = 0, T val = T()) : std::vector<T>(n, val) {}
  60.     };
  61. }
  62.  
  63. const int dx[4] = {0, +1, 0, -1};
  64. const int dy[4] = {+1, 0, -1, 0};
  65. const int inf = 1e9, BLOCK = 700, MAXN = 5e5 + 10;
  66. const long long oo = 1e18, BASE = 311, MOD = 1e9 + 7;
  67. //____________________________________________________________________ 
  68.  
  69. int n, a[75];
  70. const vector <int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};
  71. int mask[75];
  72. int dp[75][(1LL << 19) + 2];
  73. ll heso[75][2];
  74.  
  75. struct Combination{
  76.     vector <long long> fact, inv;
  77.  
  78.     ll POW(long long a, long long n) {
  79.         a %= MOD;
  80.         long long res = 1;
  81.         while(n) {
  82.             if(n & 1) res = (res * a) % MOD;
  83.             a = (a * a) % MOD;
  84.             n >>= 1;
  85.         }
  86.         return res;
  87.     }
  88.  
  89.     void build(int N) {
  90.         fact.assign(N + 3, 1);
  91.         inv.assign(N + 3, 1);
  92.         for (int i = 1; i <= N; ++i)
  93.             fact[i] = (1LL * fact[i - 1] * i) % MOD;
  94.         inv[N] = POW(fact[N], MOD - 2);
  95.         for (int i = N - 1; i >= 0; --i)
  96.             inv[i] = (1LL * inv[i + 1] * (i + 1)) % MOD;
  97.     }
  98.  
  99.     ll get(int k, int n) {
  100.         if(k < 0 || n < k) return 0;
  101.         return (fact[n] * inv[n - k]) % MOD * inv[k] % MOD;
  102.     }
  103.     //             (k, n) = 0 if k > n
  104.     //             (k, n) = n * inv_fact[k] * (k - 1, n - 1)
  105.     //       sigma (i, n) = 2 ^ n              :i = 0 -> n
  106.     //       sigma (k, i) = (k + 1, n + 1)     :i = 0 -> n
  107.     //  sigma (i, n + i)  = (m, n + m + 1)     :i = 0 -> m
  108.     // sigma {(i, n) ^ 2} = (n, 2n)            :i = 0 -> n
  109.     // sigma {k * (k, n)} = n * 2 ^ (n - 1)    :i = 1 -> n
  110.     // x[1] + x[2] + .. + x[n]  = m (x[i] >= 0) => (n - 1, m + n - 1)
  111.     // x[1] + x[2] + .. + x[n] <= m (x[i] >= 0) => (n, m + n)
  112.     // cell(u, v) -> cell(x, y) => (x - u, x + y - u - v)
  113. }C;
  114.  
  115.  
  116.  
  117. ll solve(int i, int nmask) {
  118.     if(i > 70) {
  119.         if(nmask == 0) return 1LL;
  120.         return 0;
  121.     }
  122.     if(~dp[i][nmask]) return dp[i][nmask];
  123.     ll cur = 0;
  124.     // if()
  125.     cur += (solve(i + 1, nmask) * heso[i][0]) % MOD;
  126.     cur %= MOD;
  127.     cur += (solve(i + 1, nmask ^ mask[i]) * heso[i][1]) % MOD;
  128.     cur %= MOD;
  129.     return dp[i][nmask] = cur;
  130. }
  131.  
  132. void phckhnh() {    
  133.  
  134.     for (int i = 2; i <= 70; ++i) {
  135.         int N = i;
  136.         for (int p = 0; p < 19; ++p) {  
  137.             int pow = 0;
  138.             while(N % primes[p] == 0) N /= primes[p], ++pow; 
  139.             if(pow % 2 == 1) mask[i] = mask[i] | (1 << p);
  140.         }
  141.     }
  142.     cin >> n;
  143.     for (int i = 1; i <= n; ++i) {
  144.         int val; cin >> val;
  145.         a[val]++;
  146.     }
  147.     C.build(n);
  148.     for (int i = 1; i <= 70; ++i) {
  149.         heso[i][0] = 1, heso[i][1] = 0;
  150.         for (int cnt = 1; cnt <= a[i]; ++cnt) {
  151.             heso[i][cnt & 1] += C.get(cnt, a[i]);
  152.             heso[i][cnt & 1] %= MOD;
  153.         }
  154.         // if(heso[i][0] = 0) heso[i][0] = 1;
  155.         // debug(heso[i]);
  156.     }
  157.  
  158.     memset(dp, -1, sizeof dp);
  159.     cout << (solve(1, 0) + MOD - 1) % MOD;
  160. }
  161. //____________________________________________________________________
  162.  
  163.  
  164.  
  165. main(){   
  166.     //____________________________________________________  
  167.     ios_base :: sync_with_stdio(false); 
  168.     cin.tie(nullptr); cout.tie(nullptr);
  169.     #define ooo "a"
  170.     if (fopen(ooo".inp", "r")) {
  171.         freopen(ooo".inp", "r", stdin); 
  172.         freopen(ooo".out", "w", stdout);
  173.     }
  174.     //____________________________________________________  
  175.     int Ntest = 1; 
  176.     // cin >> Ntest;
  177.     while(Ntest--) {
  178.         phckhnh(); 
  179.         cout << endl;
  180.     }
  181.     cerr <<"\nPhcKhnh's TimeRun: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s. \n";
  182. }
Success #stdin #stdout #stderr 0.13s 157336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
PhcKhnh's TimeRun: 0.129588s.
https://ideone.com/CF9dzX
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!