M_sea

洛谷5368 [PKUSC2018]真实排名
LuoguBZOJLOJ分析假设现在在算第 $i$ 个人的答案。分两种情况讨论:$a_i$ 没翻倍比较简单。假设 ...
扫描右侧二维码阅读全文
10
2019/05

洛谷5368 [PKUSC2018]真实排名

Luogu

BZOJ

LOJ

分析

假设现在在算第 $i$ 个人的答案。分两种情况讨论:

  • $a_i$ 没翻倍

比较简单。

假设 $j$ 翻倍后满足条件,那么显然要有 $a_j<\lceil\frac{a_i}{2}\rceil\bigcup a_j\geq a_i$ 。

二分出对应的位置即可得到满足条件的人数,假设为 $s$ ,那么这一部分的答案就是 $C_s^k$ 。

  • $a_i$ 翻倍了

可以这么考虑:先把所有数翻倍,再把一些数除以 $2$ 。

假设 $j$ 除以 $2$ 后满足条件,那么显然要有 $a_j<a_i\bigcup a_j\geq 2a_i$ 。

同样二分出对应的位置即可得到满足条件的人数,假设为 $s$ ,那么这一部分的答案就是 $C_s^{n-k}$ 。

注意当 $k=0$ 时这一部分答案为 $0$ 。


另外要注意特判一下 $a_i=0$ 的情况,此时答案为 $C_n^k$ 。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int mod=998244353;

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

int A[N],B[N];
int fac[N],inv[N];

inline int C(int n,int m) {
    if (n<m) return 0;
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int main() {
    int n=read(),k=read();
    for (re int i=1;i<=n;++i) A[i]=B[i]=read();
    sort(B+1,B+n+1);
    
    fac[0]=1;
    for (re int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2);
    for (re int i=n;i>=1;--i) inv[i-1]=1ll*inv[i]*i%mod;
    
    for (re int i=1;i<=n;++i) {
        int x=A[i];
        if (!x) { printf("%d\n",C(n,k)); continue; }
        int a=lower_bound(B+1,B+n+1,(x+1)/2)-B-1;
        int b=n-(lower_bound(B+1,B+n+1,x)-B);
        int c=lower_bound(B+1,B+n+1,x)-B-1;
        int d=n-(lower_bound(B+1,B+n+1,x*2)-B)+1;
        int ans=C(a+b,k);
        if (k) ans=(ans+C(c+d,n-k))%mod;
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 07 PM

1 条评论

  1. smy

    去年没有特判0然后做这题做了2.5h

    mmp

发表评论