题意
给定 $n$ 个选手的成绩, 选中其中 $k$ 个使他们的成绩翻倍. 对于每个选手回答有多少种方案使得他的排名不发生变化.
$n\le 10^5$
题解
场上唯一A掉的题?
分两类讨论, 一类是当前选手翻倍了, 一类是不加倍.
- 如果当前选手不加倍, 那么所有加倍后会超过当前选手的选手都不能加倍, 其他人随意. 方案数量显然就是在剩下的人中选 $k$ 个的方案数量。
- 如果当前选手加倍, 那么所有加倍后被超过的选手也必须加倍, 其他人随意. 方案数也是个组合数.
于是这沙雕题就做完了. 场上只A这一题的我可真是个沙雕.
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#include <bits/stdc++.h>
const int MAXN=1e5+10;
const int MOD=998244353;
int n;
int k;
int a[MAXN];
int s[MAXN];
int h[MAXN];
int d[MAXN];
int inv[MAXN];
int fact[MAXN];
int ReadInt();
int C(int,int);
int Pow(int,int,int);
int main(){
n=ReadInt();
k=ReadInt();
for(int i=1;i<=n;i++)
s[i]=a[i]=ReadInt();
std::sort(s+1,s+n+1);
fact[0]=1;
for(int i=1;i<=n;i++)
fact[i]=1ll*fact[i-1]*i%MOD;
inv[n]=Pow(fact[n],MOD-2,MOD);
for(int i=n;i>=1;i--)
inv[i-1]=1ll*inv[i]*i%MOD;
for(int i=1;i<=n;i++){
if(a[i]==0)
printf("%d\n",C(n,k));
else{
int ans=0;
int d=std::lower_bound(s+1,s+n+1,a[i])-std::lower_bound(s+1,s+n+1,(a[i]+1)/2);
(ans+=C(n-d-1,k))%=MOD;
d=std::lower_bound(s+1,s+n+1,a[i]*2)-std::lower_bound(s+1,s+n+1,a[i]);
(ans+=C(n-d,k-d))%=MOD;
printf("%d\n",ans);
}
}
return 0;
}
int C(int n,int m){
return n<m||n<0||m<0?0:1ll*fact[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int Pow(int a,int n,int p){
int ans=1;
while(n>0){
if(n&1)
ans=1ll*a*ans%p;
a=1ll*a*a%p;
n>>=1;
}
return ans;
}
inline int ReadInt(){
int x=0;
register char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
|