QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#520735#1436. Split in Sets123456xwdWA 2ms5976kbC++142.0kb2024-08-15 15:14:172024-08-15 15:14:17

Judging History

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

  • [2024-08-15 15:14:17]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5976kb
  • [2024-08-15 15:14:17]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
using namespace std;
int rd(){
	int x=0,f=1; char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}
const int N=1e5+5,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;

int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod,b>>=1;
	}
	return ans;
}
int jc[N+5],jc_inv[N+5];	
void init(){
	jc[0]=1;
	for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;
	jc_inv[N]=ksm(jc[N],mod-2);
	for(int i=N;i>=1;i--) jc_inv[i-1]=jc_inv[i]*i%mod;
}
int C(int n,int m){
	return jc[n]*jc_inv[m]%mod*jc_inv[n-m]%mod;
}
int A(int n,int m){
	return jc[n]*jc_inv[m]%mod;
}
int n,k;
int a[N];
void add(int &x,int y){
	x+=y;
	if(x>mod) x-=mod;
}
pii solve(int d,int k,int n){
	if(d<0){
		int res=0;
		for(int i=0;i<=k;i++){
			if((k-i)&1) add(res,(mod-C(k,i)*ksm(i,n)%mod)%mod);
			else add(res,C(k,i)%mod*ksm(i,n)%mod);
		}
		return m_p(0,res);
	}
	int cnt=0,j=0,sum=0;
	for(int i=1;i<=n;i++) if((a[i]>>d)&1) cnt++;
	if(cnt==0) return solve(d-1,k,n);
	if(cnt==n){
		for(int i=1;i<=n;i++) a[i]-=(1ll<<d);
		pii res=solve(d-1,k,n);
		add(res.fi,k*(1ll<<d)%mod);
		return res;
	}
	if(cnt<k){
		for(int i=1;i<=n;i++){
			if(!((a[i]>>d)&1)) a[++j]=a[i];
			else add(sum,a[i]);
		}
		pii res=solve(d-1,k-cnt,j);
		add(res.fi,sum);
		res.se=res.se*A(k,cnt)%mod;
		return res;
	}
	int tmp=(1ll<<30)-1;
	for(int i=1;i<=n;i++){
		if((a[i]>>d)&1) a[++j]=a[i];
		else tmp&=a[i];
	}
	a[++j]=tmp;
	pii res=solve(d-1,k,j);
	add(res.fi,(k-1)*(1ll<<d)%mod);
	return res;
}
	
signed main(){
	n=rd(),k=rd();
	for(int i=1;i<=n;i++) a[i]=rd();
	init();
	pii ans=solve(29,k,n);
	printf("%lld %lld\n",ans.fi,ans.se);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 5356kb

input:

3 2
4 7 5

output:

11 2

result:

ok 2 tokens

Test #2:

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

input:

4 1
44 47 74 77

output:

8 1

result:

ok 2 tokens

Test #3:

score: 0
Accepted
time: 2ms
memory: 5352kb

input:

4 4
44 47 74 77

output:

242 24

result:

ok 2 tokens

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 5976kb

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 822896319

result:

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