bzoj 5368 真实排名

Posted on | Views:

分类讨论 + 简单组合计数.

题目描述可以等价为变化之后,分数严格小于 $A_i$ 的人数不变.

分两种情况讨论.

情况一, $A_i$ 没有翻倍.

若其它的某个翻倍的分数原来是 $x$ ,为了使排名不变,必须满足 $2x<A_i$ 或 $x\ge A_i$ .

排序后二分,找出这样的 $x$ 有 $p$ 个,那么这种情况的方案数就是 $p \choose k$ .

情况二, $A_i$ 翻倍.

为了使排名不变,其余 $A_i\le x<2A_i​$ 的数也必须翻倍,另外的数可以随意选择.

排序后二分,找出这样的 $x$ 一共有 $q$ 个,若 $q<k-1$ ,则方案数为 $0$ ,否则为 $n-q-1\choose k-q-1$ .

根据加法原理,把两种情况的方案数加在一起就是答案.

时间复杂度 $O(n\log n)$ .

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=1e5+10;
int n,k,fac[MAXN],invfac[MAXN];
void init_fac()
{
	fac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=mul(fac[i-1],i);
	invfac[n]=fpow(fac[n],P-2);
	for(int i=n-1;i>=0;--i)
		invfac[i]=mul(invfac[i+1],i+1);
}
int C(int M,int N)
{
	if(M<0 || N<0 || M<N)
		return 0;
	return mul(fac[M],mul(invfac[M-N],invfac[N]));
}
int A[MAXN],a[MAXN],ans[MAXN];
int Binary_Search(int val)
{
	int L=1,R=n,res=0;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(A[mid]<=val)
			res=mid,L=mid+1;
		else
			R=mid-1;
	}
	return res;
}
int calc(int L,int R)//L<=x<=R
{
	if(L>R)
		return 0;
	return Binary_Search(R)-Binary_Search(L-1);
}
void solve()
{
	for(int i=1;i<=n;++i)
	{
		int val=A[i];
		int p=calc(A[1],(val+1)/2-1)+calc(val,A[n])-1;
		int q;
		if(val<=2*val-1)
			q=calc(val,2*val-1)-1;
		else
			q=0;
		ans[i]=add(C(p,k),C(n-q-1,k-q-1));
	}
}
int main()
{
	n=read(),k=read();
	init_fac();
	for(int i=1;i<=n;++i)
		A[i]=a[i]=read();
	sort(A+1,A+1+n);
	solve();
	for(int i=1;i<=n;++i)
	{
		int pos=lower_bound(A+1,A+1+n,a[i])-A;
		printf("%d\n",ans[pos]);
	}
	return 0;
}