QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#520858#1436. Split in SetsA6n6d6y6WA 1ms3836kbC++141.1kb2024-08-15 16:46:262024-08-15 16:46:27

Judging History

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

  • [2024-08-15 16:46:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3836kb
  • [2024-08-15 16:46:26]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10,mod=1e9+7;
int n,k,sum,pro,a[maxn],b[maxn],jc[maxn]={1},inv[maxn]={1};
int ksm(int a,int b){
	int c=1;
	while(b){
		if(b&1)c=c*a%mod;
		a=a*a%mod;b>>=1;
	}
	return c;
}
signed main(){
	cin>>n>>k;sum=0;pro=1;
	for(int i=1;i<=n;i++)
		jc[i]=jc[i-1]*i%mod,inv[i]=ksm(jc[i],mod-2);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=30;i>=0;i--){
		int tmp=(1ll<<31)-1,tot=0,cnt=0;
		for(int j=1;j<=n;j++)cnt+=a[j]>>i&1;
		if(cnt<k){
			pro=(pro*jc[k]*inv[k-cnt]%mod)%mod;
			for(int j=1;j<=n;j++){
				if((a[j]>>i)&1)sum+=a[j];
				else b[++tot]=a[j];
			}
			k-=cnt,n=tot;
			for(int j=1;j<=n;j++)a[j]=b[j];
		}else if(cnt==n)sum+=(1ll<<i)*k;
		else{
			sum+=(1ll<<i)*(k-1);
			for(int j=1;j<=n;j++){
				if(a[j]>>i&1)b[++tot]=a[j];
				else tmp&=a[j];
			}
			b[++tot]=tmp,n=tot;
			for(int j=1;j<=n;j++)a[j]=b[j];
		}
		for(int j=1;j<=n;j++)a[j]&=(1ll<<i)-1;
	}
	int ans=0;
	for(int i=0;i<=k;i++)
		ans=(ans+((k-i)&1?mod-1:1)*ksm(i,n)%mod*inv[i]%mod*inv[k-i]%mod*jc[k]%mod)%mod;
	cout<<sum<<" "<<pro*ans%mod;
	return 0;
}

詳細信息

Test #1:

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

input:

3 2
4 7 5

output:

11 2

result:

ok 2 tokens

Test #2:

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

input:

4 1
44 47 74 77

output:

8 1

result:

ok 2 tokens

Test #3:

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

input:

4 4
44 47 74 77

output:

242 24

result:

ok 2 tokens

Test #4:

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

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 -669920382

result:

wrong answer 2nd words differ - expected: '671056390', found: '-669920382'