QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#472434#1436. Split in SetszbrcWA 386ms44148kbC++141.5kb2024-07-11 16:23:202024-07-11 16:23:20

Judging History

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

  • [2024-07-11 16:23:20]
  • 评测
  • 测评结果:WA
  • 用时:386ms
  • 内存:44148kb
  • [2024-07-11 16:23:20]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10,mod=1e9+7;
int n,k,ans;
multiset<int>a;
int inv[N],fac[N];
int Pow(int x,int n){
	if(n==0)return 1;
	int a=Pow(x,n/2);
	return a*a%mod*(n&1?x:1)%mod;
}
void init(){
	inv[0]=fac[0]=1;
	for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
	inv[N-1]=Pow(fac[N-1],mod-2);
	for(int i=N-2;i;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int P(int n,int m){
	return fac[n]*inv[n-m]%mod;
}
int C(int n,int m){
	if(m<0)return 0;
	int res=0;
	for(int i=0;i<=m;i++){
		if((m-i)&1)res=(res+mod-Pow(i,n)*inv[i]%mod*inv[m-i]%mod)%mod;
		else res=(res+Pow(i,n)*inv[i]%mod*inv[m-i]%mod)%mod;
	}
	return res;
}
int tot=1;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	init();
	tot=tot*P(k,k);
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		a.insert(x);
	}
	if(k==1){
		ans=*a.begin();
		for(auto i : a)ans&=i;
		cout<<ans<<' '<<1;
		return 0;
	}
	for(int i=40;i>=0;i--){
		int cnt=0,len=a.size();
		multiset<int>nw;
		for(auto j : a){
			if((j>>i)&1)cnt++;
		}
		if(cnt==a.size())ans+=min(k,cnt)*(1LL<<i);
		else ans+=min((k-1),cnt)*(1LL<<i);
		if(i==0){
			if(cnt<k)tot=tot*C(a.size()-cnt,k-cnt)%mod;
			else tot=C(cnt+1,k)*tot%mod;
		}
		if(cnt<k){
			k-=cnt;
			for(auto j : a){
				if((j>>i)&1)ans+=j&((1LL<<i)-1); 
				else nw.insert(j);
			}
		}else{
			int s=INT_MAX;
			for(auto j :a){
				if((j>>i)&1)nw.insert(j);
				else s&=j;
			}
			if(cnt!=len)a.insert(s);
		}
		a=nw;
	}
	cout<<ans<<' '<<tot<<'\n';
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 18ms
memory: 34860kb

input:

3 2
4 7 5

output:

11 2

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 17ms
memory: 35024kb

input:

4 1
44 47 74 77

output:

8 1

result:

ok 2 tokens

Test #3:

score: 0
Accepted
time: 21ms
memory: 34796kb

input:

4 4
44 47 74 77

output:

242 24

result:

ok 2 tokens

Test #4:

score: 0
Accepted
time: 19ms
memory: 34936kb

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:

35467198613 671056390

result:

ok 2 tokens

Test #5:

score: -100
Wrong Answer
time: 386ms
memory: 44148kb

input:

99988 19981
11771832 114 110908254 348 553453 840525742 342620766 12408 27914 2 29 4914992 79461083 133 0 44575 11059027 13445407 3508312 227 50410231 1253800 12277 201525297 39 88 20236754 417742 0 8412502 172886086 35315 144742219 211319 352393 10445 1330114 56814394 90807971 3 69704 104497 0 9176...

output:

3435071736310 430589528

result:

wrong answer 1st words differ - expected: '3435071736287', found: '3435071736310'