fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e6 + 5; 
  12. const int MOD = 1e9 + 7;  
  13.  
  14. void add(int& a, int b) {
  15. 	a += b; 
  16. 	if (a >= MOD) a -= MOD;  
  17. 	if (a < 0) a += MOD; 
  18. }
  19.  
  20. int n, k, L, R;  
  21. int a[N];
  22.  
  23. int fact[N], inv_fact[N]; 
  24.  
  25. int binpow(int a, int b) {
  26. 	int ans = 1; 
  27. 	for (; b > 0; b >>= 1) {
  28. 		if (b & 1) ans = 1ll * ans * a % MOD; 
  29. 		a = 1ll * a * a % MOD; 
  30. 	}
  31. 	return ans;
  32. }
  33.  
  34. void precompute() {
  35. 	fact[0] = 1;  
  36. 	for (int i = 1; i <= n; i++) fact[i] = 1ll * fact[i - 1] * i % MOD; 
  37. 	inv_fact[n] = binpow(fact[n], MOD - 2);
  38. 	for (int i = n - 1; i >= 0; i--) inv_fact[i] = 1ll * inv_fact[i + 1] * (i + 1) % MOD; 
  39. }
  40.  
  41. int nCk(int n, int k) {
  42. 	if (n < k) return 0;   
  43. 	return 1ll * fact[n] * inv_fact[n - k] % MOD * inv_fact[k] % MOD; 
  44. }  
  45.  
  46. int sos[1 << 20]; 
  47.  
  48. int sign(int mask) {
  49. 	return (__builtin_parity(mask) ? 1 : -1);
  50. }
  51.  
  52. int main() {
  53. 	ios::sync_with_stdio(false); 
  54. 	cin.tie(nullptr); 	
  55. 	cin >> n >> k >> L >> R;  
  56. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  57.  
  58. 	precompute();   
  59.  
  60. 	for (int i = 1; i <= n; i++) ++sos[a[i]];  
  61.  
  62. 	for (int i = 0; i < 20; i++) {
  63. 		for (int mask = 0; mask < (1 << 20); mask++) {
  64. 			if (mask & (1 << i)) sos[mask] += sos[mask ^ (1 << i)];
  65. 		}
  66. 	}
  67.  
  68. 	for (int mask = 0; mask < (1 << 20); mask++) sos[mask] = sign(mask) * nCk(sos[mask], k);
  69.  
  70. 	for (int i = 0; i < 20; i++) {
  71. 		for (int mask = 0; mask < (1 << 20); mask++) {
  72. 			if (mask & (1 << i)) add(sos[mask], sos[mask ^ (1 << i)]);
  73. 		}
  74. 	}
  75.  
  76. 	for (int mask = 0; mask < (1 << 20); mask++) {
  77. 		sos[mask] = sign(mask) * sos[mask];
  78. 		if (sos[mask] < 0) sos[mask] += MOD;
  79. 	}
  80.  
  81. 	int ans = 0;   
  82. 	for (int v = L; v <= R; v++) {
  83. 		if (v % 3 == 0) add(ans, sos[v]);
  84. 	}
  85.  
  86. 	cout << ans << '\n';
  87. }
Success #stdin #stdout 0.07s 12316KB
comments (?)
stdin 
5 2 1 7
1 2 5 6 4
stdout 
4
https://ideone.com/OgoKqY
language:
C++14 (gcc 8.3)
created:
12 days 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!