bzoj5368 [Pkusc2018]真实排名

题目描述：

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
",ans[v[i]]);
    return 0;
}