題目描述：

bz

luogu

題解：

組合數計數問題。

首先注意排名指的是成績不小于他的選手的數量（包括他自己）。

考慮怎么增大才能改變排名。

小學生都知道，對于成績為$x$的人，讓他自己不動并讓$\frac{x}{2} < y \leq x$的$y$增大能把$x$擠下去。

于是分情況討論。

自己不動，那么上述人都不能增大，答案為在剩下的人中選$k$個的方案數；

自己動，那么自己超過了$\frac{z}{2} \leq x < z$。若這種人有$i$個，那么這$i$個必須都加倍，在$i<=k-1$答案為剩下的人中選$k-1-i$個的方案數。

排序后可以雙指針直接掃，這樣排序$O(nlogn)$，計算$O(n)$，跑起來還是比較快的。

最重要的是最大值要至少開成$2e9$。

我不會說我開$0x3f3f3f3f$瘋狂$RE$的。

代碼：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N = 100050; const int MOD = 998244353; template<typename T> inline void read(T&x) {T f = 1,c = 0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}x = f*c; } int n,k,v[N],h[N]; ll jc[N<<1],ny[N<<1],jn[N<<1],ans[N],to[N]; ll C(ll x,ll y){return jn[x]*jn[y-x]%MOD*jc[y]%MOD;} struct Pair {int x,y;Pair(){}Pair(int x,int y):x(x),y(y){} }p[N]; bool cmp(Pair a,Pair b){return a.x<b.x;} void init() {jc[0]=jc[1]=jn[0]=jn[1]=ny[1]=1;for(int i=2;i<=2*n;i++){ny[i] = ((MOD-MOD/i)*ny[MOD%i]%MOD+MOD)%MOD;jc[i] = (jc[i-1]*i)%MOD;jn[i] = (jn[i-1]*ny[i])%MOD;} } int main() {read(n),read(k);init();for(int i=1;i<=n;i++){read(v[i]);p[i]=Pair(v[i],i);}sort(p+1,p+1+n,cmp);int mx = 0;for(int las=-1,i=1;i<=n;i++){if(p[i].x!=las){las = p[i].x;to[++mx]=las;}v[p[i].y]=mx;h[mx]++;}to[mx+1]=0x3f3f3f3f3f3f3f3fll;for(int i=1;i<=mx+1;i++)h[i]+=h[i-1];for(int tmp,i=1,j1=0,j2=1;i<=mx;i++){while(2ll*to[j1+1]<to[i])j1++;while(to[j2+1]<2ll*to[i])j2++;if(!to[i]){ans[i]=C(k,n);continue;}if((tmp=h[j1]+n-h[i-1]-1)>=k)ans[i]=C(k,tmp);if((tmp=h[j2]-h[i-1]-1)<=k-1&&k-1-tmp<=h[i-1]+n-h[j2])ans[i]=(ans[i]+C(k-1-tmp,h[i-1]+n-h[j2]))%MOD;}for(int i=1;i<=n;i++)printf("%lld\n",ans[v[i]]);return 0; } View Code

?

轉載于:https://www.cnblogs.com/LiGuanlin1124/p/10862262.html

總結

以上是生活随笔為你收集整理的bzoj5368 [Pkusc2018]真实排名的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。