fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_N = 75;
  5. const int MAX_NN = 1e5 + 5;
  6. const int MAX_P = 20;
  7. const int MODVAL = 1e9 + 7;
  8.  
  9. int N, cnt[MAX_N], prfac[MAX_N];
  10. long long pow2[MAX_NN], dp[MAX_N][1 << MAX_P];
  11.  
  12. void pre() {
  13.     int prcnt = 0;
  14.     for(int i=2; i<MAX_N; i++) {
  15.         int prime = 1;
  16.         for(int j=2; j*j<=i; j++) if(i%j == 0) {
  17.             prime = 0;
  18.             break;
  19.         }
  20.         if(!prime) continue;
  21.  
  22.         for(int j=i; j<MAX_N; j+=i) {
  23.             int k = j, c = 0;
  24.             while(k%i == 0) k /= i, c++;
  25.             if(c&1) prfac[j] |= 1 << prcnt;
  26.         }
  27.         prcnt++;
  28.     }
  29.     pow2[0] = 1;
  30.     for(int i=1; i<MAX_NN; i++)
  31.         pow2[i] = (pow2[i-1] << 1) % MODVAL;
  32.     memset(dp, -1, sizeof dp);
  33. }
  34.  
  35. long long recur(int i, int mask) {
  36.     if(i == 0)
  37.         return mask == 0 ? 1 : 0;
  38.  
  39.     if(dp[i][mask] == -1) {
  40.         if(cnt[i] == 0)
  41.             dp[i][mask] = recur(i-1, mask);
  42.         else
  43.             dp[i][mask] = (recur(i-1, mask) + recur(i-1, mask ^ prfac[i])) * pow2[cnt[i]-1] % MODVAL;
  44.     }
  45.     return dp[i][mask];
  46. }
  47.  
  48. int main() {
  49.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  50.  
  51.     pre();
  52.     cin >> N;
  53.     for(int i=0; i<N; i++) {
  54.         int x;
  55.         cin >> x;
  56.         cnt[x]++;
  57.     }
  58.  
  59.     cout << (recur(70, 0) + MODVAL - 1) % MODVAL << "\n";
  60.  
  61.     return 0;
  62. }
Success #stdin #stdout 0.2s 618332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WAiiUb
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!