QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471835 | #1436. Split in Sets | lichenyu_ac | WA | 2ms | 5520kb | C++14 | 1.7kb | 2024-07-11 09:53:46 | 2024-07-11 09:53:46 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,m;
ll a[N],ans,sum=1;
ll f[N],incf[N];
ll power(ll a,ll b){
ll ans=1;
for(;b;b>>=1){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
}
return ans;
}
void pre_work(int n){
f[0]=1;
for(int i=1;i<=n;i++)f[i]=f[i-1]*i%mod;
incf[n]=power(f[n],mod-2);
for(int i=n-1;i>=0;i--)incf[i]=incf[i+1]*(i+1)%mod;
}
vector<ll>b,c;
ll len(ll x){
ll ret=0;
while(x)ret++,x>>=1;
return ret;
}
void solve(int k){
int cnt=0,Max=0;
if(!b.size()||!k)return;
for(auto x:b){
int now_len=len(x);
if(now_len==Max)cnt++;
else if(now_len>Max)Max=now_len,cnt=1;
}
if(Max==0)return;
if(k==1){
ll tmp=-1;
for(auto x:b){
if(tmp==-1)tmp=x;
else tmp&=x;
}
ans+=tmp;
return;
}
if(cnt==k){
for(auto x:b)ans+=x;
sum=sum*f[k]%mod;
return;
}
if(cnt==b.size()){
for(auto &x:b)x-=(1<<(Max-1));
ans+=k*(1<<(Max-1));
solve(k);
return;
}
if(cnt<k){
c.clear();
for(auto x:b){
if(x>=(1<<(Max-1)))ans+=x;
else c.push_back(x);
}
sum=sum*f[k]%mod*incf[k-cnt]%mod;
b=c;
solve(k-cnt);
return;
}else{
c.clear();
ll tmp=-1;
for(auto x:b){
if(x>=(1<<(Max-1)))c.push_back(x-(1<<(Max-1)));
else{
if(tmp==-1)tmp=x;
else tmp&=x;
}
}
c.push_back(tmp);
ans+=(k-1)*(1<<(Max-1));
b=c;
solve(k);
return;
}
}
int main(){
pre_work(N-1);
// double st=clock();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),b.push_back(a[i]);
solve(m);
printf("%lld %lld\n",ans,sum);
// double ed=clock();
// printf("%lf\n",ed-st);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5520kb
input:
3 2 4 7 5
output:
11 2
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 2ms
memory: 5380kb
input:
4 1 44 47 74 77
output:
8 1
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 2ms
memory: 5340kb
input:
4 4 44 47 74 77
output:
242 24
result:
ok 2 tokens
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 5508kb
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 152712092
result:
wrong answer 2nd words differ - expected: '671056390', found: '152712092'