[PKUSC2018]真实排名

[PKUSC2018]真实排名

题目大意：

有\(n(n\le10^5)\)个人，每个人有一个成绩\(A_i(0\le A_i\le10^9)\)。定义一个人的排名为\(n\)个人中成绩不小于他的总人数。现在恰好有\(k\)个人的成绩翻倍。问对于每个人，有多少种情况满足这个人的排名不变。

思路：

排名不变的情况不外乎两种：

1. \(A_i\)本身不翻倍，且满足\(\lfloor\frac{A_i+1}2\rfloor\le A_j<A_i\)的\(A_j\)均不翻倍。
2. \(A_i\)本身翻倍，且满足\(A_i\le A_j<2A_i\)的\(A_j\)均翻倍。

对\(A_{1\sim n}\)进行排序，设排序后的数组为\(tmp\)。令：

• p=std::lower_bound(&tmp[1],&tmp[n]+1,(a[i]+1)/2)-tmp-1 。
• q=std::lower_bound(&tmp[1],&tmp[n]+1,a[i])-tmp 。
• r=std::lower_bound(&tmp[1],&tmp[n]+1,a[i]*2)-tmp+!a[i] 。

其中\(p\)的 -1 是为了方便将\(A_i\)本身也算入不翻倍的部分，而\(r\)的 +!a[i] 是考虑\(A_i=0\)的情况，将\(A_i\)自身算入翻倍的部分。

显然，对于第一种情况，方案数为\(\binom{n-q+p}k\)；对于第二种情况，方案数为\(\binom{n-r+q}{k-r+q}\)。

组合数可以直接预处理阶乘及阶乘逆元，剩下主要是排序和二分。时间复杂度\(\mathcal O(n\log n)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

typedef long long int64;

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=1e5+1,mod=998244353;

int a[N],tmp[N],fact[N],factinv[N];

void exgcd(const int &a,const int &b,int &x,int &y) {

	if(!b) {

		x=1,y=0;

		return;

	}

	exgcd(b,a%b,y,x);

	y-=a/b*x;

}

inline int inv(const int &x) {

	int ret,tmp;

	exgcd(x,mod,ret,tmp);

	return (ret%mod+mod)%mod;

}

inline int C(const int &n,const int &m) {

	if(n<m||n<0||m<0) return 0;

	return (int64)fact[n]*factinv[m]%mod*factinv[n-m]%mod;

}

int main() {

	const int n=getint(),k=getint();

	for(register int i=1;i<=n;i++) {

		tmp[i]=a[i]=getint();

	}

	std::sort(&tmp[1],&tmp[n]+1);

	for(register int i=fact[0]=1;i<=n;i++) {

		fact[i]=(int64)fact[i-1]*i%mod;

	}

	factinv[n]=inv(fact[n]);

	for(register int i=n;i;i--) {

		factinv[i-1]=(int64)factinv[i]*i%mod;

	}

	for(register int i=1;i<=n;i++) {

		const int p=std::lower_bound(&tmp[1],&tmp[n]+1,(a[i]+1)/2)-tmp-1;

		const int q=std::lower_bound(&tmp[1],&tmp[n]+1,a[i])-tmp;

		const int r=std::lower_bound(&tmp[1],&tmp[n]+1,a[i]*2)-tmp+!a[i];

		printf("%d\n",(C(n-q+p,k)+C(n-r+q,k-r+q))%mod);

	}

	return 0;

}