fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. const ll N = 10000001;
  5.  
  6. ll p = 998244353;
  7.  
  8. ll factorialNumInverse[N + 1]; 
  9.  
  10. ll naturalNumInverse[N + 1]; 
  11.  
  12. ll fact[N + 1]; 
  13.  
  14. void InverseofNumber(ll p) 
  15. { 
  16. 	naturalNumInverse[0] = naturalNumInverse[1] = 1; 
  17. 	for (ll i = 2; i <= N; i++) 
  18. 		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
  19. } 
  20.  
  21. void InverseofFactorial(ll p) 
  22. { 
  23. 	factorialNumInverse[0] = factorialNumInverse[1] = 1; 
  24.  
  25. 	for (ll i = 2; i <= N; i++) 
  26. 		factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p; 
  27. } 
  28.  
  29.  
  30. void factorial(ll p) 
  31. { 
  32. 	fact[0] = 1; 
  33.  
  34. 	for (int i = 1; i <= N; i++) { 
  35. 		fact[i] = (fact[i - 1] * i) % p; 
  36. 	} 
  37. } 
  38.  
  39.  
  40. ll nCr(ll N, ll R, ll p) 
  41. { 
  42. 		ll ans = ((fact[N] * factorialNumInverse[R]) 
  43. 			% p * factorialNumInverse[N - R]) 
  44. 			% p; 
  45. 		return ans;
  46. } 
  47.  
  48. void init()
  49. {
  50. 	InverseofNumber(p); 
  51. 	InverseofFactorial(p); 
  52. 	factorial(p);
  53. }
  54.  
  55. ll go(vector<ll>&arr, ll n, ll xo) 
  56. {
  57.  
  58. 	// cout<<"9090"<<xorArr<<endl;
  59. 	if (xo == 0) 
  60. 		return 0; 
  61.  
  62. 	ll ans = 0; 
  63.  
  64. 	for (ll i = 0; i < n; i++) 
  65. 	{ 
  66.  
  67. 		ll c_left = xo ^ arr[i]; 
  68. 		// cout<<"----"<<xorArr<<" "<<arr[i]<<endl; 
  69. 		if (c_left < arr[i]) 
  70.         {
  71. 			ans+=nCr(arr[i], (arr[i] - c_left), p); 
  72.         }
  73. 	} 
  74.  
  75. 	return ans; 
  76. } 
  77.  
  78.  
  79. int main() 
  80. {
  81. 	init();
  82. 	ll t;
  83. 	cin>>t;
  84. 	while(t--)
  85. 	{
  86. 		ll n;
  87. 		ll v = 0;
  88. 		cin>>n;
  89. 		vector<ll>A(n+1, 0);
  90. 		for(ll i=1; i<=n; i++)
  91. 		{
  92. 			cin>>A[i];
  93. 		}
  94.  
  95. 		ll q;
  96. 		cin>>q;
  97. 		while(q--)
  98. 		{
  99. 			ll l, r;
  100. 			cin>>l>>r;
  101. 			// cout<<"--000-"<<l<<" "<<r<<endl;
  102. 			unordered_map<ll, ll>u_map;
  103. 			for(ll i=l; i<=r; i++)
  104. 			{
  105. 				// cout<<A[i]<<endl;
  106. 				u_map[A[i]]++;
  107. 			}
  108. 			vector<ll>sub_s;
  109. 			for(auto u:u_map)
  110. 			{
  111. 				// cout<<"---"<<u.second<<endl;
  112. 				sub_s.push_back(u.second);
  113. 			}
  114.  
  115. 			ll v =0;
  116.  
  117. 			for(ll u:sub_s)
  118. 			{
  119. 				// cout<<u<<" ";
  120. 				v = v ^ u;
  121. 			}
  122.  
  123. 			// cout<<endl<<l<<"---"<<r<<endl;
  124. 			// cout<<endl<<"-----"<<v<<endl;
  125. 			// cout<<"----"<<(r-l)+1<<endl;
  126. 			// cout<<"000"<<v<<endl;
  127. 			cout<<go(sub_s, sub_s.size(), v)<<endl;
  128. 			// cout<<v<<endl;
  129. 		}
  130. 	}
  131. 	return 0;
  132. }
Success #stdin #stdout 0.97s 237972KB
comments (?)
stdin
copy 
1
5
1 2 1 2 2
3
1 1
2 3
2 5
stdout
copy 
1
0
3
https://ideone.com/PX9ofs
language:
C++14 (gcc 8.3)
created:
4 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!