QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#520928 | #1436. Split in Sets | pjt_camellia | WA | 1ms | 4060kb | C++14 | 2.3kb | 2024-08-15 17:35:58 | 2024-08-15 17:35:59 |
Judging History
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'