QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#521000 | #1436. Split in Sets | c20251515 | WA | 11ms | 22004kb | C++14 | 1.7kb | 2024-08-15 19:40:22 | 2024-08-15 19:40:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,mod=1e9+7;
ll n,K,a[N],ans1=0,ans2=1;
ll fac[N],inv[N];
ll maxn=0;
bool vis[N];
vector<ll> p;
ll ksm(ll x,ll k){
ll tmp=1;
while(k){
if(k%2==1) tmp=tmp*x%mod;
x=x*x%mod;
k/=2;
}
return tmp;
}
void init(){
fac[0]=1;
for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
inv[1000000]=ksm(fac[1000000],mod-2);
for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll c(ll x,ll y){
if(x<y) return 0;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void get(ll x){
ll now=0;
while(x){
x/=2;
now++;
}
maxn=max(maxn,now-1);
}
ll strling(ll x,ll y){
if(x<y) return 0;
if(y==0) return 0;
if(x==y) return 1;
if(y==1) return 1;
return (strling(x-1,y-1)+y*strling(x-1,y)%mod)%mod;
}
void dfs(vector<ll> s,ll k,ll deep){
if((ll)s.size()<k) exit(0);
ll cnt0=0,cnt1=0;
for(auto x:s){
if(x&(1ll<<deep)) cnt1++;
else cnt0++;
}
ans1=(ans1+(1ll<<deep)*min(k-(cnt0>0),cnt1))%mod;
if(deep==0){
if(cnt1>=k) ans2=ans2*strling(cnt1+1,k)%mod;
else ans2=ans2*strling(cnt0,k-cnt1)%mod;
return;
}
if(cnt1>=k){
ll tmp=INT_MAX;
vector<ll> record;
for(auto x:s){
if(x&(1ll<<deep)) record.push_back(x);
else tmp&=x;
}
if(cnt0) record.push_back(tmp);
dfs(record,k,deep-1);
}
else{
vector<ll> record;
for(auto x:s){
if((x&(1ll<<deep))==0) record.push_back(x);
else ans1=(ans1+(x&((1ll<<deep)-1)))%mod;
}
dfs(record,k-cnt1,deep-1);
}
}
int main(){
cin>>n>>K;
init();
for(int i=1;i<=n;i++){
cin>>a[i];
get(a[i]);
p.push_back(a[i]);
}
dfs(p,K,30);
ans2=ans2*fac[K]%mod;
cout<<ans1<<" "<<ans2;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 8ms
memory: 20852kb
input:
3 2 4 7 5
output:
11 2
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 3ms
memory: 20104kb
input:
4 1 44 47 74 77
output:
8 1
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 11ms
memory: 22004kb
input:
4 4 44 47 74 77
output:
242 24
result:
ok 2 tokens
Test #4:
score: -100
Wrong Answer
time: 6ms
memory: 21176kb
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'