fork(14) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/VfEMOp
language:
C++14 (gcc 8.3)
created:
7 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!