| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1066123 | vjudge1 | Swapping Cities (APIO20_swap) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
//#define szz(s) int(s.size())
#define int long long
const int N = (1 << 20) + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
int n, k, l, r, res;
int a[N];
void fixmod(int &x){
if(x >= MOD) x -= MOD;
}
namespace sub1{
int f[260][260][260];
void solve(){
FOR(i, 1, n){
f[i][1][a[i]] += 1; fixmod(f[i][1][a[i]]);
FOR(t, 1, k){
FOR(x, 0, min(r, 255ll)){
f[i + 1][t][x] += f[i][t][x]; fixmod(f[i + 1][t][x]);
if((x | a[i + 1]) <= r){ f[i + 1][t + 1][x | a[i + 1]] += f[i][t][x]; fixmod(f[i + 1][t + 1][x | a[i + 1]]); }
}
}
}
// cout << f[2][1][3];
for(int x = l; x <= min(r, 255ll); ++x) if(x % 3 == 0){
// cout << x << " " << f[n][k][x] << "\n";
res += f[n][k][x]; fixmod(res);
}
cout << res;
}
}
namespace sub2{
int f[N], cnt[N][25], t;
int gt[N], nd[N], c[N];
int mul(int a, int b){
if(b == 0) return 1;
a %= MOD;
int r = mul(a, b / 2);
int t = (1ll * r * r) % MOD;
if(b % 2) return (1ll * t * a) % MOD;
else return t;
}
void pre(){
gt[0] = nd[0] = 1;
for(int i = 1; i <= n; ++i){
gt[i] = (1ll * gt[i - 1] * i) % MOD;
nd[i] = mul(gt[i], MOD - 2);
}
}
int C(int k, int n){
if(k < 0) return 0;
if(k > n) return 0;
return ((((1ll * gt[n] * nd[k]) % MOD) * 1ll * nd[n - k]) % MOD) % MOD;
}
void solve(){
if(l % 3 != 0){
cout << 0; return;
}
pre();
t = __builtin_popcount(l) % 2;
FOR(i, 1, n) ++cnt[a[i]][0];
// cout << cnt[1][0] << "\n";
FOR(mask, 0, (1 << 20) - 1){
if((mask | l) != l) continue;
FOR(k, 1, 20){
if(mask & (1 << k - 1)){
cnt[mask][k] = (cnt[mask][k - 1] + cnt[mask ^ (1 << k - 1)][k - 1]);
fixmod(cnt[mask][k]);
}else cnt[mask][k] = cnt[mask][k - 1];
}
f[mask] = C(k, cnt[mask][20]);
int tmp = __builtin_popcount(mask) % 2;
int s = (tmp == t ? 1 : -1);
// cout << mask << " " << cnt[mask][20] << " " << f[mask] << "\n";
res = (res + s * f[mask] + MOD) % MOD;
}
// cout << cnt[9][1] << "\n";
cout << res;
}
}
void solve(){
cin >> n >> k >> l >> r;
FOR(i, 1, n) cin >> a[i];
if(l == r) sub2::solve();
else sub1::solve();
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inp("in.txt");
// out("out.txt");
int t = 1;
// cin >> t;
while(t--){
solve();
}
}