QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#472378 | #1436. Split in Sets | zbrc | WA | 3ms | 6944kb | C++14 | 1.8kb | 2024-07-11 16:00:50 | 2024-07-11 16:00:50 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
int n,k,ans;
multiset<int>a;
int inv[N],fac[N];
int Pow(int x,int n){
if(n==0)return 1;
int a=Pow(x,n/2);
return a*a%mod*(n&1?x:1)%mod;
}
void init(){
inv[0]=fac[0]=1;
for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
inv[N-1]=Pow(fac[N-1],mod-2);
for(int i=N-2;i;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int P(int n,int m){
return fac[n]*inv[n-m]%mod;
}
int C(int n,int m){
if(m<0)return 0;
int res=0;
for(int i=0;i<=m;i++){
if((m-i)&1)res=(res+mod-Pow(i,n)*inv[i]%mod*inv[m-i]%mod)%mod;
else res=(res+Pow(i,n)*inv[i]%mod*inv[m-i]%mod)%mod;
}
return res;
}
int tot=1;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
init();
tot=tot*P(k,k);
for(int i=1;i<=n;i++){
int x;cin>>x;
a.insert(x);
}
if(k==1){
ans=*a.begin();
for(auto i : a)ans&=i;
cout<<ans<<' '<<1;
return 0;
}
vector<int>e;
for(int i=30;i>=0&&k;i--){
int cnt=0;
e.clear();
for(auto j : a){
if((j>>i)&1){
cnt++;
e.push_back(j);
}
}
// cout<<cnt<<' '<<tot<<' '<<k<<'\n';
if(i==0){
if(cnt<k)tot=tot*C(a.size()-cnt,k-cnt)%mod;
else tot=C(cnt+1,k)*tot%mod;
}
if(!cnt)continue;
if(cnt==a.size())ans+=k*(1LL<<i);
else ans+=(k-1)*(1LL<<i);
if(cnt<k){
k-=cnt;
for(int j=0;j<e.size();j++){
ans+=e[j]&((1LL<<i)-1);
a.erase(a.lower_bound(e[j]));
}
}else{
int s=0,flag=1;
for(auto j = a.rbegin();j != a.rend();j++){
if(lower_bound(e.begin(),e.end(),*j)==e.end()){
if(flag)s=*j,flag=0;
else s&=*j;
a.erase(a.lower_bound(*j));
}
}
if(cnt!=a.size())a.insert(s);
for(int j=0;j<e.size();j++){
a.erase(a.lower_bound(e[j]));
a.insert(e[j]-(1LL<<i));
}
}
}
cout<<ans<<' '<<tot<<'\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 6944kb
input:
3 2 4 7 5
output:
11 2
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 3ms
memory: 6732kb
input:
4 1 44 47 74 77
output:
8 1
result:
ok 2 tokens
Test #3:
score: -100
Wrong Answer
time: 3ms
memory: 6652kb
input:
4 4 44 47 74 77
output:
306 24
result:
wrong answer 1st words differ - expected: '242', found: '306'