QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #859971 | #9967. Imbalanced Teams | Judgelight | WA | 10ms | 10120kb | C++14 | 983b | 2025-01-18 09:07:37 | 2025-01-18 09:08:32 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define mk make_pair
#define N 2009
#define K 1000009
using namespace std;
const int Size=1000000,mod=1e9+7;
int n,k,a[N],b[K][2],cnt[K],c[N][N];
signed main(){
scanf("%d%d",&n,&k);
c[0][0]=1;for(int i=1;i<=n;i++){
c[i][0]=c[i][i]=1;for(int j=1;j<i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1],(c[i][j]>=mod)&&(c[i][j]-=mod);
}
for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;
sort(a+1,a+n+1);int ans1=0,ans2=1;for(int i=1;i<=k;i++)ans1+=a[n-i+1]-a[i];
for(int i=1;i<=k;i++)b[a[i]][0]++,b[a[n-i+1]][1]++;
if(a[k]!=a[n-k+1]){
for(int i=1;i<=Size;i++){
ans2=1ll*ans2*c[cnt[i]][b[i][0]]%mod*c[cnt[i]][b[i][1]]%mod;
}
}
else{
for(int i=1;i<=Size;i++){
if(i!=a[k])ans2=1ll*ans2*c[cnt[i]][b[i][0]]%mod*c[cnt[i]][b[i][1]]%mod;
else ans2=1ll*ans2*c[cnt[i]][b[i][0]+b[i][1]]%mod*c[b[i][0]+b[i][1]][b[i][0]]%mod*((mod+1)/2)%mod;
}
}
printf("%d %d",ans1,ans2);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 9ms
memory: 8040kb
input:
6 2 2 5 7 2 5 2
output:
8 6
result:
ok 2 number(s): "8 6"
Test #2:
score: 0
Accepted
time: 9ms
memory: 8032kb
input:
5 2 1 1 1 1 1
output:
0 15
result:
ok 2 number(s): "0 15"
Test #3:
score: 0
Accepted
time: 8ms
memory: 8028kb
input:
2 1 1 1
output:
0 1
result:
ok 2 number(s): "0 1"
Test #4:
score: 0
Accepted
time: 7ms
memory: 8020kb
input:
2 1 1 2
output:
1 1
result:
ok 2 number(s): "1 1"
Test #5:
score: 0
Accepted
time: 9ms
memory: 7928kb
input:
10 4 3 3 1 2 4 6 2 4 4 1
output:
12 1
result:
ok 2 number(s): "12 1"
Test #6:
score: 0
Accepted
time: 8ms
memory: 8072kb
input:
14 3 57 57 57 57 57 57 57 57 57 57 57 57 57 57
output:
0 30030
result:
ok 2 number(s): "0 30030"
Test #7:
score: -100
Wrong Answer
time: 10ms
memory: 10120kb
input:
13 5 858336 900782 858336 900782 900782 858336 900782 858336 858336 858336 858336 858336 52093
output:
976027 140
result:
wrong answer 2nd numbers differ - expected: '280', found: '140'