fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb(a) push_back(a)
  4. #define mp(a,b) make_pair(a,b)
  5. #define ll long long
  6. #define pii pair<int,int>
  7. #define pll pair<ll,ll>
  8. #define forr(a,b,c) for(int a=b;a<c;a++)
  9. #define forrev(a,b,c) for(int a=b;a>c;a--)
  10. #define all(v) v.begin(),v.end()
  11. #define revall(v) v.rbegin(),v.rend()
  12. #define allk(v,k) v.begin()+k,v.end()
  13. #define revallk(v,k) v.rbegin()+k,v.rend()
  14. #define allkj(v,k,j) v.begin()+k,v.end()-j
  15. #define revallkj(v,k,j) v.rbegin()+j,v.rend()-k
  16. #define ff first
  17. #define ss second
  18. #define init inity
  19. ////////////////////////// non-modifiable /////////////////////////////////
  20.  
  21. #define mod 1000000007
  22. #define eps 1e-9
  23. #define inf INT_MAX
  24. #define infl LONG_LONG_MAX
  25. ll power(ll a,ll n)
  26. {
  27. 	if(a==0)return 0;
  28. 	if(a==1 || n==0)return 1;
  29. 	if(n==1)return a%mod;//can remove mod?
  30. 	ll t=power(a,n/2);
  31. 	t=t*t%mod;
  32. 	if(n&1)return t*a%mod;
  33. 	return t;
  34. }
  35. #define P (int)(2e2)+9
  36. #define FACTORIZE 1
  37. #define DETERMINE 2
  38. int primes[P];
  39. void sieve(int prime=2)//2->detects prime, 1->max prime in factorization
  40. {
  41. 	forr(i,2,P-3)
  42. 	{
  43. 		if(!primes[i])
  44. 		for(int j=prime*i;j<P-3;j+=i)primes[j]=i;
  45. 	}
  46. 	//forr(i,1,21)cout<<primes[i]<<" ";cout<<endl;
  47. 	if(prime==2)
  48. 	{
  49. 		forr(i,1,P-3)
  50. 		{
  51. 			primes[i] = ( primes[i] == 0 );
  52. 		}
  53. 	}
  54. 	else
  55. 		primes[1] = 1;
  56. }
  57. int popcount(ll a)
  58. {
  59. 	int c=0;
  60. 	while(a)
  61. 	{
  62. 		c++;
  63. 		a-=a&-a;
  64. 	}
  65. 	return c;
  66. }
  67. void factorize(int a)
  68. {
  69.  
  70. }
  71. void update(int tree[],int idx,int val,int maxval)
  72. {
  73. 	for(;idx<=maxval;idx+=idx&-idx)
  74. 	{
  75. 		tree[idx]+=val;
  76. 		//tree[idx]%=mod;
  77. 	}
  78. }
  79. int read(int tree[],int idx)
  80. {
  81. 	ll sum=0;
  82. 	for(;idx>0;idx-=idx&-idx)
  83. 	{
  84. 		sum+=tree[idx];
  85. 		//sum%=mod;
  86. 	}
  87. 	return sum;
  88. }
  89. ////////////////////////// MODIFIABLE /////////////////////////////////////
  90.  
  91. struct node2
  92. {
  93. 	int id,val;
  94. 	node2()
  95. 	{
  96. 		static int ctx=0;
  97. 		id=ctx++;
  98. 	};
  99. 	node2(int a,int b=0,int c=0,int d=0,int e=0,int f=0)
  100. 	{
  101. 		val=a;
  102. 	}
  103. };
  104. struct comp2
  105. {
  106. 	bool operator()(int a,int b)
  107. 	{
  108. 		//return a<b;
  109. 		return b<a;	//min heap	
  110. 	}
  111. };
  112. bool cmp2(int a,int b)
  113. {
  114. 	//return a<b;
  115. 	return b<a;
  116. }
  117.  
  118. struct node
  119. {
  120. 	int id,val;
  121. 	node()
  122. 	{
  123. 		static int ctx=0;
  124. 		id=ctx++;
  125. 	};
  126. 	node(int a,int b=0,int c=0,int d=0,int e=0,int f=0)
  127. 	{
  128. 		val=a;
  129. 	}
  130. };
  131. struct comp
  132. {
  133. 	bool operator()(int a,int b)
  134. 	{
  135. 		//return a<b;
  136. 		return b<a;	//min heap	
  137. 	}
  138. };
  139. bool cmp(int a,int b)
  140. {
  141. 	//return a<b;
  142. 	return b<a;
  143. }
  144.  
  145. ////////////////////////// custom-defined /////////////////////////////////
  146. #define N 100009
  147. #define L ( (1 << 21) + 9 )
  148. ll n,m,a[109],b,c,d,edge,k,h,w,x,y,p,q,t,ans,res,ma,mi,T,act=0,pas=1,cur,flag,now;
  149. ll dp[2][L], dp2, cnt, square[109], conv[109], f[N];
  150. char s[1];
  151. //vector<string> s;
  152. double e,z;
  153. vector<int> v, vec;
  154. set<int> sett;
  155. typedef map<int,int> Mapp;
  156. Mapp mapp;
  157. ////////////////////////// variable declarations //////////////////////////
  158.  
  159. void print()//for detailed output of [a data structure]
  160. {
  161.  
  162. }
  163. void print2()//for detailed output of [a data structure]
  164. {
  165.  
  166. }
  167. void input()
  168. {
  169. 	ios_base::sync_with_stdio(false);cin.tie(NULL);
  170. 	cin >> n;
  171.  
  172. 	forr(i,0,n)
  173. 	{
  174. 		cin >> x;
  175. 		a[x]++;
  176. 	}
  177. }
  178. void init()
  179. {
  180. 	sieve();
  181.  
  182. 	forr(i,1,71)
  183. 		if( primes[i] == 1 )
  184. 			conv[i] = k++;
  185.  
  186. 	//forr(i,1,71) cout << conv[i] << " "; cout << endl;
  187.  
  188. 	memset(primes,0,sizeof(primes));
  189. 	sieve(1);
  190.  
  191. 	//forr(i,1,71) cout << primes[i] << " "; cout << endl;
  192.  
  193. 	forr(i,1,10)
  194. 		square[i*i] = true;
  195.  
  196. 	//forr(i,1,71) cout << square[i] << " "; cout << endl;
  197.  
  198. 	f[0] = 1;
  199.  
  200. 	forr(i,1,N-4)
  201. 		f[i] = f[i-1] * 2ll % mod;
  202.  
  203. 	//forr(i,1,10) cout << f[i] << " "; cout << endl;
  204. }
  205.  
  206. inline int chooseEven(int n)
  207. {
  208. 	if( n == 1 ) return 0;
  209. 	return ( f[n-1] - 1 + mod ) % mod;
  210. }
  211.  
  212. inline int chooseOdd(int n)
  213. {
  214. 	return f[n-1];
  215. }
  216.  
  217. inline int getMask(int num)
  218. {
  219. 	int mask = 0;
  220.  
  221. 	p = num;
  222.  
  223. 	//cout << "num=" << num << endl;
  224.  
  225. 	while( p > 1 )
  226. 	{
  227. 		//cout << "primes=" << primes[p] << endl;
  228. 		mask ^= ( 1 << conv[ primes[p] ] );
  229.  
  230. 		p /= primes[p];
  231. 	}
  232.  
  233. 	return mask;
  234. }
  235.  
  236. void solve()
  237. {
  238. 	init();
  239.  
  240. 	b = 12 * 7;
  241.  
  242. 	//cout << "mask=" << getMask(b) << endl;
  243.  
  244. 	int lim = 1 << 21;
  245.  
  246. 	// handle 1s separately
  247.  
  248. 	forr(num,1,71)
  249. 	{
  250. 		if( a[num] > 0 )
  251. 		{
  252. 			if( square[ num ] == true )
  253. 				dp[act][0] = ( f[ a[num] ] - 1 + mod ) % mod;
  254. 			else
  255. 			{
  256. 				dp[act][0] = chooseEven( a[num] );
  257.  
  258. 				int mask = getMask(num);
  259.  
  260. 				dp[act][mask] = chooseOdd( a[num] );
  261. 			}
  262.  
  263. 			p = num;
  264. 			break;
  265. 		}
  266. 	}
  267.  
  268. 	forr(num,p+1,71)
  269. 	{
  270. 		if( a[num] == 0 ) continue;
  271.  
  272. 		act = 1 - ( pas = act );
  273.  
  274. 		memset(dp[act],0,sizeof(dp[act]));
  275.  
  276. 		int maskPrime = getMask(num);
  277.  
  278. 		forr(mask,0,lim)
  279. 		{
  280. 			dp[act][mask] += dp[pas][maskPrime];
  281. 			dp[act][mask] %= mod;
  282.  
  283. 			if( maskPrime == 0 )
  284. 			{
  285. 				dp[act][mask] += 1ll * dp[pas][mask] * ( f[ a[num] ] - 1 + mod ) % mod;
  286. 				dp[act][mask] %= mod;
  287. 				dp[act][mask] += ( f[ a[num] ] - 1 + mod ) % mod;
  288. 				dp[act][mask] %= mod;
  289. 				continue;
  290. 			}
  291.  
  292. 			dp[act][mask ^ maskPrime] += 1ll * dp[pas][mask] * chooseOdd(a[num]) % mod;
  293. 			dp[act][mask ^ maskPrime] %= mod;
  294.  
  295. 			dp[act][mask] += 1ll * dp[pas][mask] * ( 1 + chooseEven(a[num]) ) % mod;
  296. 			dp[act][mask] %= mod;
  297. 			dp[act][mask] += chooseEven(a[num]);
  298. 			dp[act][mask] %= mod;
  299. 		}
  300. 	}
  301. }
  302. void output()
  303. {
  304. 	cout << dp[act][0];
  305. }
  306. ///////////////////////////// my functions ////////////////////////////////
  307.  
  308. int main() 
  309. {
  310. 	input();
  311. 	solve();
  312. 	output();
  313. 	return 0;
  314. }
  315. //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN ////
Success #stdin #stdout 0s 48792KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/BP05Of
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!