QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471833 | #1436. Split in Sets | rainygame | WA | 1ms | 3592kb | C++17 | 1.3kb | 2024-07-11 09:52:41 | 2024-07-11 09:52:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 100001
#define MAXK 32
const int MOD(1e9+7);
int n, k, mxn, res(1), res2;
int fac[MAXN];
vector<int> a;
int qpow(int x, int k=MOD-2){
int res(1); for (; k; k>>=1, (x *= x) %= MOD) if (k & 1) (res *= x) %= MOD;
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
fac[0] = 1; for (int i(1); i<=n; ++i) fac[i] = (fac[i-1] * i) % MOD;
for (int i(1), x; i<=n; ++i){cin >> x; a.push_back(x);}
for (int i(MAXK-1), cnt; ~i; --i){
cnt = 0; for (auto j: a) if ((j>>i) & 1) ++cnt;
if (cnt < k){
vector<int> tmp;
for (auto j: a){
if (!((j>>i) & 1)) tmp.push_back(j);
else mxn += j;
}
a = tmp; (res *= (fac[k]*qpow(fac[k-cnt])) % MOD) %= MOD; k -= cnt;
}else if (cnt == a.size()){mxn += k * (1ll<<i); for (auto &j: a) j ^= (1ll<<i);}
else{
mxn += (k-1) * mxn;
vector<int> tmp; int now((1ll<<MAXK)-1);
for (auto j: a){
if ((j>>i) & 1) tmp.push_back(j ^ (1ll<<i));
else now &= j;
}
tmp.push_back(now); a = tmp;
}
}
for (int i(0); i<=k; ++i){
int ans((((k-i) & 1 ? -qpow(i, a.size()) : qpow(i, a.size()))+MOD) % MOD);
(res2 += (ans*qpow(fac[i]))%MOD*qpow(fac[k-i])) %= MOD;
}
cout << mxn << ' ' << (res2*res)%MOD;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
input:
3 2 4 7 5
output:
11 2
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
4 1 44 47 74 77
output:
8 1
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
4 4 44 47 74 77
output:
242 24
result:
ok 2 tokens
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3592kb
input:
1000 975 633065 7087 25267 3940676 618039 1695 2043 728466935 3498 13604984 4 99 119488 151315 12 32 52705062 26815 1902279 33952 480604 390647001 60 1 12566875 7591859 6 119892 7829822 2129 4 11644639 17 33200 5330 338 2 9 6862 3781 148087 57 198 13224999 10493180 1 5755424 216 1757297 210 1002623 ...
output:
815745567593 283125976
result:
wrong answer 1st words differ - expected: '35467198613', found: '815745567593'