QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#520928#1436. Split in Setspjt_camelliaWA 1ms4060kbC++142.3kb2024-08-15 17:35:582024-08-15 17:35:59

Judging History

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

  • [2024-08-15 17:35:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4060kb
  • [2024-08-15 17:35:58]
  • 提交

answer

// Problem: H - Split in Sets
// Contest: Virtual Judge - 20240710 多校集训 div2 贪心与构造(pb)
// URL: https://vjudge.net/contest/639510#problem/H
// Memory Limit: 253 MB
// Time Limit: 1000 ms
// Date: 2024-08-15 15:40:06
// 
// Powered by CP Editor (https://cpeditor.org)

/*

*/
#include <bits/stdc++.h>
using namespace std;
inline long long read(){
    long long x=0,w=0;char c=0;
    while(!isdigit(c)) {w|=c=='-';c=getchar();}
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return w?-x:x;
}
const long long mod=1e9+7;
long long n,k,ans,cnt=1;
vector<int> a;
long long fac[100500],inv[100500];
inline long long ksm(long long a,long long b){
	long long res=1;
	while(b){
		if(b&1){
			res=res*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
inline long long C(long long x,long long y){
	if(x<0||y<0||x<y){
		return 0;
	}
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
inline long long str(long long x,long long y){
	long long res=0;
	for(int i=0;i<=y;i++){
		if(i&1){
			res=(res+mod-C(y,i)*ksm(y-i,x)%mod)%mod;
		}
		else{
			res=(res+C(y,i)*ksm(y-i,x)%mod)%mod;
		}
	}
	return res*inv[y]%mod;
}
void work(vector<int> a,int k,int dep){//k个盒子,二进制下第dep位
	int cnt0=0,cnt1=0;
	for(int i:a){
		if((i>>dep)&1){
			cnt1++;
		}
		else{
			cnt0++;
		}
	}
	ans=(ans+min(k-(cnt0>0),cnt1)*(1ll<<dep))%mod;
	if(dep==0){
		if(k>cnt1){
			cnt=cnt*str(cnt0,k-cnt1)%mod;
		}
		else{
			cnt=cnt*str(cnt1+1,k)%mod;
		}
		return;
	}
	if(k>cnt1){
		vector<int> b;
		for(int i:a){
			if((~i>>dep)&1){
				b.push_back(i);
			}
			else{
				ans=(ans+(i&((1<<dep)-1)))%mod;
			}
		}
		work(b,k-cnt1,dep-1);
	}
	else{
		vector<int> b;
		long long maxx=LONG_LONG_MAX;
		for(int i:a){
			if((i>>dep)&1){
				b.push_back(i);
			}
			else{
				maxx&=i;
			}
		}
		if(cnt0){
			b.push_back(maxx);
		}
		work(b,k,dep-1);
	}
}
int main(){ 
	n=read();
	k=read();
	for(int i=1,x;i<=n;i++){
		x=read();
		a.push_back(x);
	}
	fac[0]=1;
	for(int i=1;i<=n;i++){
		fac[i]=fac[i-1]*i%mod;
	}
	inv[n]=ksm(fac[n],mod-2);
	for(int i=n;i;i--){
		inv[i-1]=inv[i]*i%mod;
	}
	sort(a.begin(),a.end());
	work(a,k,30);
	cnt=cnt*fac[k]%mod;
	printf("%lld %lld",ans,cnt);
	return 0; 
}
/*

*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 4060kb

input:

3 2
4 7 5

output:

11 2

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

4 1
44 47 74 77

output:

8 1

result:

ok 2 tokens

Test #3:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

4 4
44 47 74 77

output:

242 24

result:

ok 2 tokens

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3880kb

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'