QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#520858 | #1436. Split in Sets | A6n6d6y6 | WA | 1ms | 3836kb | C++14 | 1.1kb | 2024-08-15 16:46:26 | 2024-08-15 16:46:27 |
Judging History
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'