PKUWC 2018 真实排名

PKUWC2018 真实排名

题面描述

共有\(n\)个人，每个人有一个能力值，每个人的排名为所有能力值不比他小的人的个数（包括他自己）。

现在有\(k\)个人能力值翻倍，但我们无法得知是哪\(k\)个人

问每个人有多少种情况排名不变。

思路

把所有人按照能力值从小到大排序。

分类讨论一下：此人是否翻倍。

若此人翻倍，则他后面有一段的人也要跟着翻倍，否则就会被他超过

若此人不翻倍，则他前面有一段的人也不能翻倍，否则就会超过他

另外特判一下\(0\)的情况即可

代码

#include<bits/stdc++.h>

using namespace std;

const int sz=1e5+7;

const int mod=998244353;

int L,R;

int n,m,k;

int ans[sz];

int sum[sz];

int l[sz],r[sz];

int a[sz],b[sz];

int c[sz],cnt[sz];

int inv[sz],fac[sz],ifac[sz];

void init(){

	fac[0]=ifac[0]=1;

	fac[1]=ifac[1]=inv[1]=1;

	for(int i=2;i<sz;i++){

		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

		fac[i]=1ll*i*fac[i-1]%mod;

		ifac[i]=1ll*inv[i]*ifac[i-1]%mod;

	}

}

int C(int n,int m){

	if(n<m) return 0;

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

	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;

}

int main(){

	init();

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];

	sort(b+1,b+n+1);

	b[0]=c[0]=-1;

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

		if(b[i]!=b[i-1]) c[++m]=b[i];

		++cnt[m];

	}

	L=0,R=0;

	c[m+1]=INT_MAX;

	for(int i=1;i<=m;i++)

		sum[i]=sum[i-1]+cnt[i];

	for(int i=1;i<=m;i++){

		while(2*c[L]<c[i]) L++;

		while(2*c[i]>c[R+1]) R++;

		l[i]=L,r[i]=R;

	}

	if(c[1]==0) ans[1]=C(n,k);

	for(int i=(c[1]==0)+1;i<=m;i++){

		ans[i]=(ans[i]+C(n-(sum[i-1]-sum[l[i]-1]+1),k))%mod;

		ans[i]=(ans[i]+C(n-(sum[r[i]]-sum[i-1]),k-(sum[r[i]]-sum[i-1])))%mod;

	}

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

		int num=lower_bound(c+1,c+m+1,a[i])-c;

		printf("%d\n",ans[num]);

	}

}

巴特西

PKUWC 2018 真实排名

PKUWC2018 真实排名

题面描述

思路

代码

最新文章

热门文章