fork download
  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
stdin
Standard input is empty
stdout
0