fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 1000000007;
  5. const int B = 14;
  6. const int SZ = 1 << B;
  7.  
  8. long long modpow(long long a, long long e) {
  9.     long long res = 1;
  10.     while (e > 0) {
  11.         if (e & 1) res = res * a % MOD;
  12.         a = a * a % MOD;
  13.         e >>= 1;
  14.     }
  15.     return res;
  16. }
  17.  
  18. int submod(int a, int b) {
  19.     a -= b;
  20.     if (a < 0) a += MOD;
  21.     return a;
  22. }
  23.  
  24. int addmod(int a, int b) {
  25.     a += b;
  26.     if (a >= MOD) a -= MOD;
  27.     return a;
  28. }
  29.  
  30. int main() {
  31.     ios::sync_with_stdio(false);
  32.     cin.tie(nullptr);
  33.  
  34.     int n, k, L, R;
  35.     cin >> n >> k >> L >> R;
  36.  
  37.     vector<int> cnt(SZ, 0);
  38.  
  39.     for (int i = 0; i < n; i++) {
  40.         int x;
  41.         cin >> x;
  42.         cnt[x]++;
  43.     }
  44.  
  45.     vector<int> fact(n + 1), invfact(n + 1);
  46.  
  47.     fact[0] = 1;
  48.     for (int i = 1; i <= n; i++) {
  49.         fact[i] = 1LL * fact[i - 1] * i % MOD;
  50.     }
  51.  
  52.     invfact[n] = modpow(fact[n], MOD - 2);
  53.     for (int i = n; i >= 1; i--) {
  54.         invfact[i - 1] = 1LL * invfact[i] * i % MOD;
  55.     }
  56.  
  57.     auto C = [&](int N, int K) -> int {
  58.         if (K < 0 || K > N) return 0;
  59.         return 1LL * fact[N] * invfact[K] % MOD * invfact[N - K] % MOD;
  60.     };
  61.  
  62.     // SOS DP:
  63.     // cnt[mask] = number of elements x such that x is a submask of mask.
  64.     for (int b = 0; b < B; b++) {
  65.         for (int mask = 0; mask < SZ; mask++) {
  66.             if (mask & (1 << b)) {
  67.                 cnt[mask] += cnt[mask ^ (1 << b)];
  68.             }
  69.         }
  70.     }
  71.  
  72.     vector<int> ways(SZ);
  73.  
  74.     // ways[mask] = number of k-subsets whose OR is a submask of mask.
  75.     for (int mask = 0; mask < SZ; mask++) {
  76.         ways[mask] = C(cnt[mask], k);
  77.     }
  78.  
  79.     // Möbius inversion:
  80.     // after this, ways[mask] = number of k-subsets whose OR is exactly mask.
  81.     for (int b = 0; b < B; b++) {
  82.         for (int mask = 0; mask < SZ; mask++) {
  83.             if (mask & (1 << b)) {
  84.                 ways[mask] = submod(ways[mask], ways[mask ^ (1 << b)]);
  85.             }
  86.         }
  87.     }
  88.  
  89.     int ans = 0;
  90.  
  91.     for (int mask = max(0, L); mask < SZ && mask <= R; mask++) {
  92.         if (mask % 3 == 0) {
  93.             ans = addmod(ans, ways[mask]);
  94.         }
  95.     }
  96.  
  97.     cout << ans << '\n';
  98.     return 0;
  99. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
5 2 1 7
1 2 5 6 4
stdout 
4
https://ideone.com/7wtKKJ
language:
C++ (gcc 8.3)
created:
6 hours 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!