fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int mod = 1e9 + 7;
  5. signed main(){
  6. 	ios_base::sync_with_stdio(false);
  7.     cin.tie(NULL);
  8. 	// freopen("Submask.inp", "r", stdin);
  9. 	// freopen("Submask.out", "w", stdout);
  10.     int n, x, k, l, r; cin >> n >> k >> l >> r;
  11.  
  12.     vector<int> inv(2000006), c(2000006);
  13.     inv[1] = 1;
  14.     for(int i = 2; i <= 2000000; i++) inv[i] = (mod - (mod/i) * inv[mod % i] % mod) % mod;
  15.     for(int i = 0; i < k; i++) c[i] = 0;
  16.     c[k] = 1;
  17.     for(int i = k+1; i <= 2000000; i++){
  18.         c[i] = c[i-1] * i % mod;
  19.         c[i] = c[i] * inv[i-k] % mod;
  20.     }
  21.     int sz = 1<<20;
  22.     int freq[sz], dp[sz], a[n];
  23.     memset(dp, 0, sizeof dp);
  24.     memset(freq, 0, sizeof freq);
  25.     for(int i = 0; i < n; i++){
  26.     	cin >> a[i];
  27.     	freq[a[i]]++;
  28.     }
  29.     for(int i = 0; i < n; i++){
  30.     	dp[a[i]] = freq[a[i]];
  31.     }
  32.     for(int i = 0; i < 20; i++){
  33.     	for(int j = 1; j < sz; j++){
  34.     		if((j >> i) & 1){
  35.     			dp[j] += dp[j ^ (1 << i)];
  36.     		}
  37.     	}
  38.     }
  39.     for(int i = 0; i < sz; i++){
  40.     	if(dp[i] < k) dp[i] = 0;
  41.     	else dp[i] = c[dp[i]];
  42.     }
  43. 	for(int i = 0; i < 20; i++){
  44. 	    for(int j = 1; j < sz; j++){
  45. 	    	if((j >> i) & 1){
  46. 	    		dp[j] = (dp[j] - dp[j ^ (1 << i)] + mod) % mod;
  47. 	    	}
  48. 	    }
  49. 	}
  50. 	int res = 0;
  51. 	for(int i = (l / 3 + (l % 3 != 0)) * 3; i < r; i += 3){
  52. 		res = (res + dp[i]) % mod ;
  53. 	}
  54.     cout << res;
  55.  
  56. }
  57.  
Success #stdin #stdout 0.44s 50836KB
comments (?)
stdin
copy 
5 2 1 7
1 2 5 6 4
stdout
copy 
4
https://ideone.com/8sGBWm
language:
C++14 (clang 8.0)
created:
5 days ago
visibility:
public

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!