P5368 [PKUSC2018]真实排名

Problem Link

对于每个 \(a_i\) 我们可以考虑这 \(k\) 个选手中要不要有 \(a_i\)

如果没有的话，那我们就看看有哪些 \(a_j\) 在翻倍后不会影响到 \(a_i\) 的排名

显然 \(2*a_j<a_i\) 或者 \(a_i \le a_j\) 的这些 \(a_j\) 都满足要求，我们记它们的个数为 \(cnt_1\)

那么如果这 \(k\) 个中有 \(a_i\) ，那么我们也要让 \(a_i\) 翻倍时会影响到的那些 \(a_j\) 也翻个倍，其他就随便选了

显然 \(a_i \le a_j < 2*a_i\) 的这些 \(a_j\) 都符合要求，我们记它们的个数为 \(cnt_2\)

计算 \(cnt_1,cnt_2\) 。。。这二分啥的怎么搞都可以的吧，我这里直接暴力动态开点权值线段树，不用离散化，岂不美哉

现在来算答案

第一部分的答案就是那些 \(a_j\) 随便选 \(k\) 个，也就是 \(C_{cnt_1}^k\)，\(C\) 为组合数

第二部分：

因为符合要求的 \(cnt_2\) 个选手都得翻个倍，也就是说都得选，如果 \(cnt_2>k\) 当然这部分的答案为 0 了

如果 \(cnt_2 \le k\) 那么我们就能从剩下的 \(n-cnt_2\) 个选手中随便挑 \(k-cnt_2\) 个选手，因为他们无论如何都不会影响到 \(a_i\) 的排名

那么这部分答案就是 \(C_{n-cnt_2}^{k-cnt_2} ,(cnt_2\le k)\)

注意要特判 \(a_i=0\) 的情况，\(a_i=0\) 的答案是 \(C_n^k\)

那么最后的答案就是这两个组合数的和

千万不要忘记取模！！！

// This code wrote by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
const int MaxN=100050;
const int p=998244353;
const int MaxAi=10000050;
template <class t> inline void read(t &s)
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(s<<3)+(s<<1)+(c^48),c=getchar();
    s*=f;
    return;
}
// int _1;
int mypow[MaxN];
int Ans[MaxN];
int val[MaxAi],ls[MaxAi],rs[MaxAi];
int ndn=1;
int n,k;
int a[MaxN];
// int _2;
inline int fastpow(int a,int b)
{
    reg int ans=1;
    for(;b;b>>=1,a=a*a%p)
        if(b&1)
            ans=ans*a%p;
    return ans;
}
inline int getC(int n,int m)
{
    if(n<m)
        return 0;
    return mypow[n]*fastpow(mypow[m],p-2)%p*fastpow(mypow[n-m],p-2)%p;
}
#define lson ls[u]
#define rson rs[u]
inline void pushup(int u)
{
    val[u]=val[lson]+val[rson];
    return;
}
inline void modify(int &u,int l,int r,int p,int k)
{
    if(!u)
        u=++ndn;
    if(l==r)
    {
        val[u]+=k;
        return;
    }
    reg int mid=(l+r)>>1;
    if(p<=mid)
        modify(lson,l,mid,p,k);
    else
        modify(rson,mid+1,r,p,k);
    pushup(u);
    return;
}
inline int query(int u,int l,int r,int ql,int qr)
{
    if(!u)
        return 0;
    if(ql<=l&&r<=qr)
        return val[u];
    reg int mid=(l+r)>>1,ans=0;
    if(ql<=mid)
        ans+=query(lson,l,mid,ql,qr);
    if(mid<qr)
        ans+=query(rson,mid+1,r,ql,qr);
    return ans;
}
signed main(void)
{
    // freopen("data.in","r",stdin);
    // freopen("my.out","w",stdout);
    // printf("MBs %lld\n",(&_2-&_1)>>18);
    cin>>n>>k;
    mypow[0]=1;
    for(int i=1;i<MaxN;++i)
        mypow[i]=mypow[i-1]*i%p;
    reg int rt=1;
    for(int i=1;i<=n;++i)
        read(a[i]),modify(rt,0,1e9+1,a[i],1);
    // reg int highest=a[n].x;
    //,full=getC(n,k);
    for(int i=1;i<=n;++i)
    {
        if(!a[i])
        {
            printf("%lld\n",getC(n,k));
            continue;
        }
        reg int cnt=0;
        /*
        for(int j=1;j<=n;++j)
            if(a[j].x>=a[i].x||a[j].y<a[i].x)
                ++cnt;
        --cnt;
        */
        // printf("find %lld %lld\n",find1(a[i].x-1),find2(a[i].x));
        cnt=query(rt,0,1e9+1,a[i],1e9+1)+query(rt,0,1e9+1,0,(a[i]-1)/2)-1;
        // printf("cnt1 %lld\n",cnt);
        reg int ans=getC(cnt,k);
        /*
        for(int j=1;j<=n;++j)
            if(a[i].x<=a[j].x&&a[j].x<=a[i].y)
                ++cnt;
        */
        cnt=query(rt,0,1e9+1,a[i],a[i]*2-1);
        // printf("cnt2 %lld\n",cnt);
        if(cnt<=k)
            ans+=getC(n-cnt,k-cnt);
        printf("%lld\n",ans%p);
    }
    return 0;
}

P5368 [PKUSC2018]真实排名

原文：https://www.cnblogs.com/chinesepikaync/p/12329233.html