「PKUSC 2018」真实排名

题目链接

\(Solution\)

我们将现在所要进行的数设为\(now\)

我们分情况讨论一下

他自己不翻倍
他自己翻倍

我们首先来看看\(1\)操作

如果要满足他对排名没有影响，那么不能进行翻倍的数只有\([\lceil\frac{now}{2}\rceil,now]\)。(我考场上不知道在干吗，写的是能进行翻倍的数，麻烦好多，常数也大)。我们假设这一段为\(cnt\)个,那么这一段的答案就是:

\[C_{n-cnt}^{k}
\]

再来看看\(2\)操作

如果我们要讲\(now*2\)要使得排名不变，那么\([now,now*2)\)则必须翻倍,将区间内的数射为res,其他的随便选那些数都可以。答案就是

\[C_{n-res}^{k-res}
\]

最后的答案就是

\[C_{n-res}^{k-res}+C_{n-cnt}^{k}
\]

\(Code\)

代码写的十分丑陋，毕竟是考场写的吗

#include<bits/stdc++.h>

#define int long long

#define rg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

const int mod=998244353;

using namespace std;

int read(){

    int x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();

    return f*x;

}

struct node {

	int id,x;

}a[100010];

bool cmp(const node & a , const node & b ){

	return a.x<b.x;

}

int b[100010],jc[100010],c[100010];

int ksm(int a,int b){

	int ans=1;

	while(b){

		if(b&1)

			ans=a*ans%mod;

		a=a*a%mod;

		b>>=1;

	}

	return ans;

}

main(){

	file("sort");

	int n=read(),k=read();

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

		a[i].id=i,a[i].x=read();

	sort(a+1,a+1+n,cmp);

	jc[0]=1;

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

		b[i]=a[i].x,jc[i]=jc[i-1]*i%mod;

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

		int x=b[i]/2,ans=0;

		if(b[i]&1)

			x++;

		int p=lower_bound(b+1,b+1+n,x)-b-1;

		int j=lower_bound(b+1,b+1+n,b[i])-b-1;

		int pp=n-j-1;

		if(p+pp>=k)

			ans+=jc[p+pp]*ksm(jc[k]*jc[p+pp-k]%mod,mod-2)%mod;

		int ppp=max(lower_bound(b+1,b+1+n,b[i]*2)-b-1-j,1ll*1);

		int kk=k-ppp;

		if(kk>=0)

			p=n-ppp,ans+=jc[p]*ksm(jc[kk]*jc[p-kk]%mod,mod-2)%mod;

		c[a[i].id]=ans%mod;

	}

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

		cout<<c[i]<<endl;

	return 0;

}

巴特西

「PKUSC 2018」真实排名

题目链接

\(Solution\)

\(Code\)

最新文章

热门文章