QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#519998 | #1436. Split in Sets | hanmm81 | WA | 1ms | 3748kb | C++14 | 1.2kb | 2024-08-15 10:09:42 | 2024-08-15 10:09:45 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n,k,m,a[100005],inv[100005],jc[100005],size,ans1,ans2=1;
int ksm(int x,int y){
int ans = 1;
while (y){
if (y&1) ans = ans * x % mod;
x = x * x % mod,y >>= 1;
}
return ans;
}
int C(int x,int y){
int ans = 0;
for (int i = 0;i <= y;i++) ans = (ans+ksm(mod-1,y-i)*ksm(i,x)%mod*inv[i]%mod*inv[y-i]%mod)%mod;
return ans;
}
void dfs(int x,int y,int k){
if (x < 0 || k == 0 || y > n) return;
int cnt = 0,sum = 0;
for (;y <= n;y++){
if (a[y] >= (1ll<<x) && cnt != k-1) cnt++,sum += a[y];
else break;
}
ans1 += sum;
if (cnt != k-1) ans2 = (x == 0 ? C(n-y+1,m-cnt) : 1),dfs(x-1,y,k-cnt);
else{
ans2 = (x == 0 ? C(cnt+1,m) : 1);
int andd = -1;
for (;y <= n;y++) andd = (andd == -1 ? a[y] : andd&a[y]);
if (andd != -1) ans1 += andd;
}
}
signed main(){
cin >> n >> k,m = k,jc[0] = inv[0] = 1;
for (int i = 1;i <= n;i++) jc[i] = jc[i-1]*i%mod,inv[i] = ksm(jc[i],mod-2);
for (int i = 1;i <= n;i++) cin >> a[i];
sort(a+1,a+n+1,[](int a,int b){return(a>b);});
dfs(31,1,k);
cout << ans1 << " " << ans2*jc[k]%mod;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
3 2 4 7 5
output:
11 2
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
4 1 44 47 74 77
output:
8 1
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
4 4 44 47 74 77
output:
242 24
result:
ok 2 tokens
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3748kb
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 0
result:
wrong answer 2nd words differ - expected: '671056390', found: '0'