QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521006#1436. Split in Setsc20251515WA 13ms22100kbC++141.6kb2024-08-15 19:46:342024-08-15 19:46:34

Judging History

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

  • [2024-08-15 19:46:34]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:22100kb
  • [2024-08-15 19:46:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,mod=1e9+7;
ll n,K,a[N],ans1=0,ans2=1;
ll fac[N],inv[N];
ll maxn=0;
bool vis[N];
vector<ll> p;
ll ksm(ll x,ll k){
	ll tmp=1;
	while(k){
		if(k%2==1) tmp=tmp*x%mod;
		x=x*x%mod;
		k/=2;
	}
	return tmp;
}
void init(){
	fac[0]=1;
	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=ksm(fac[1000000],mod-2);
	for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll c(ll x,ll y){
	if(x<y) return 0;
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void get(ll x){
	ll now=0;
	while(x){
		x/=2;
		now++;
	}
	maxn=max(maxn,now-1);
}
ll strling(ll x,ll y){
	if(x<y) return 0;
	if(y==0) return 0;
	if(x==y) return 1;
	if(y==1) return 1;
	return (strling(x-1,y-1)+y*strling(x-1,y)%mod)%mod;
}
void dfs(vector<ll> s,ll k,ll deep){
	if((ll)s.size()<k) exit(0);
	ll cnt0=0,cnt1=0;
	for(auto x:s){
		if(x&(1ll<<deep)) cnt1++;
		else cnt0++;
	}
	ans1=(ans1+(1ll<<deep)*min(k-(cnt0>0),cnt1))%mod;
	if(deep==0){
		if(cnt1>=k) ans2=ans2*strling(cnt1+1,k)%mod;
		else ans2=ans2*strling(cnt0,k-cnt1)%mod;
		return;
	}
	if(k > cnt1) {
		vector<ll> B;
		for(auto i : s) if((~i >> deep) & 1) B.push_back(i); else ans1 += i & ((1 << deep) - 1);
		dfs(B,k - cnt1,deep - 1);
	} else {
		vector<ll> B;ll andsum = INT_MAX;
		for(auto i : s) if((i >> deep) & 1) B.push_back(i); else andsum &= i;
		if(cnt0) B.push_back(andsum);
		dfs(B,k,deep - 1);
	}
}
int main(){
	cin>>n>>K;
	init();
	for(int i=1;i<=n;i++){
		cin>>a[i];
		get(a[i]);
		p.push_back(a[i]);
	}
	dfs(p,K,maxn);
	ans2=ans2*fac[K]%mod;
	cout<<ans1<<" "<<ans2;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 12ms
memory: 19952kb

input:

3 2
4 7 5

output:

11 2

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 6ms
memory: 20564kb

input:

4 1
44 47 74 77

output:

8 1

result:

ok 2 tokens

Test #3:

score: 0
Accepted
time: 3ms
memory: 22100kb

input:

4 4
44 47 74 77

output:

242 24

result:

ok 2 tokens

Test #4:

score: -100
Wrong Answer
time: 13ms
memory: 20176kb

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:

467198368 671056390

result:

wrong answer 1st words differ - expected: '35467198613', found: '467198368'