fork(14) download
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <fstream>
  4. #include <string>
  5. #include <iomanip>
  6. #include <iterator>
  7. #include <bitset>
  8. #include <vector>
  9. #include <math.h>
  10. #include <queue>
  11. #include <map>
  12. #include <set>
  13. #include <list>
  14. #include <time.h>
  15. #include <algorithm>
  16. #define mkp make_pair
  17. #define inf 1000000000
  18. #define MOD 1000000007
  19. #define eps 1e-7
  20.  
  21. using namespace std;
  22. typedef long long ll;
  23.  
  24. int n;
  25. int mask[72];
  26. ll f[2][72];
  27. ll dp[2][1 << 20];
  28.  
  29. bool prime(int x)
  30. {
  31. for (int i = 2; i*i <= x; i++)
  32. if (x%i == 0)
  33. return 0;
  34. return 1;
  35. }
  36.  
  37. void init()
  38. {
  39. for (int i = 0; i < 72; i++)
  40. f[0][i] = 1;
  41. int cnt = 0;
  42. for (int i = 2; i < 72; i++)
  43. {
  44. if (!prime(i))
  45. continue;
  46. for (int j = 1; j < 72; j++)
  47. {
  48. int x = j;
  49. while (x%i == 0)
  50. {
  51. x /= i;
  52. mask[j] ^= (1 << cnt);
  53. }
  54. }
  55. cnt++;
  56. }
  57. }
  58.  
  59. int main()
  60. {
  61. ios_base::sync_with_stdio(0);
  62. init();
  63. cin >> n;
  64. for (int i = 0; i < n; i++)
  65. {
  66. int x;
  67. cin >> x;
  68. f[0][x] = f[1][x] = (f[0][x] + f[1][x]) % MOD;
  69. }
  70. dp[0][0] = 1;
  71. for (int i = 0; i <= 70; i++)
  72. {
  73. int nxt = (i + 1) % 2;
  74. int cur = i % 2;
  75. for (int msk = 0; msk < (1<<20); msk++)
  76. {
  77. dp[nxt][msk^mask[i]] = dp[nxt][msk^mask[i]] + dp[cur][msk] * f[1][i];
  78. dp[nxt][msk] = dp[nxt][msk] + dp[cur][msk] * f[0][i];
  79. if (dp[nxt][msk^mask[i]] >= MOD)
  80. dp[nxt][msk^mask[i]] %= MOD;
  81. if (dp[nxt][msk] >= MOD)
  82. dp[nxt][msk] %= MOD;
  83. }
  84. for (int msk = 0; msk < (1<<20); msk++)
  85. dp[cur][msk] = 0;
  86. }
  87. cout << (dp[1][0] - 1 + MOD)%MOD << endl;
  88. }
Success #stdin #stdout 0.2s 32448KB
stdin
Standard input is empty
stdout
0