QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#520750 | #1436. Split in Sets | 123456xwd | WA | 6ms | 6148kb | C++14 | 2.0kb | 2024-08-15 15:18:46 | 2024-08-15 15:18:46 |
Judging History
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[n-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);
res.fi+=k*(1ll<<d);
return res;
}
if(cnt<k){
for(int i=1;i<=n;i++){
if(!((a[i]>>d)&1)) a[++j]=a[i];
else sum+=a[i];
}
pii res=solve(d-1,k-cnt,j);
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);
res.fi+=(k-1)*(1ll<<d);
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;
}
Details
Tip: Click on the bar to expand more detailed information
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: 5960kb
input:
4 1 44 47 74 77
output:
8 1
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 2ms
memory: 5412kb
input:
4 4 44 47 74 77
output:
242 24
result:
ok 2 tokens
Test #4:
score: 0
Accepted
time: 2ms
memory: 5360kb
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 671056390
result:
ok 2 tokens
Test #5:
score: -100
Wrong Answer
time: 6ms
memory: 6148kb
input:
99988 19981 11771832 114 110908254 348 553453 840525742 342620766 12408 27914 2 29 4914992 79461083 133 0 44575 11059027 13445407 3508312 227 50410231 1253800 12277 201525297 39 88 20236754 417742 0 8412502 172886086 35315 144742219 211319 352393 10445 1330114 56814394 90807971 3 69704 104497 0 9176...
output:
3436057797599 430589528
result:
wrong answer 1st words differ - expected: '3435071736287', found: '3436057797599'