QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471833#1436. Split in SetsrainygameWA 1ms3592kbC++171.3kb2024-07-11 09:52:412024-07-11 09:52:42

Judging History

你现在查看的是最新测评结果

  • [2024-07-11 09:52:42]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3592kb
  • [2024-07-11 09:52:41]
  • 提交

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'