题目传送门qwq

对于点 $i$ ,设当前值 $a_j \geq a_i$ 的 $j$ 有 $A$ 个,$2a_j<a_i$ 的 $j$ 有 $B$ 个,$2a_j\geq a_i$ 的有 $C$ 个 ($j\not=i$)。

首先,如果翻倍的 $k$ 个选手只存在于 $A$ 中和 $B$ 中,是对 $i$ 的排名造不成影响的,方案数为 $A+B\choose k$ 。

对 $i$ 的排名造成影响的是 $C$ 中的选手,很显然,如果我们选择了一个 $C$ 中的选手使其翻倍,那么 $i$ 也必须翻倍才能保住自己的排名,可能 $i$ 翻倍了又排名过前了,原先那些 $\geq a_i$ 但是 $<2a_i$ 的数必须翻倍。也就是说,我们需要将 $i$ 翻倍,耗费一个名额,然后将 $\geq a_i$ 但是 $<2a_i$ 的所有数字翻倍,如果这些数字的个数为 $D$ 个,将耗费 $D$ 个名额。最后的 $k-1-D$ 个名额留给 $C$ 中的和 $A,B$ 中的剩下的选手,方案数是 $C+A+B-D\choose k-1-D$ 。

$A,B,C,D$ 都是可以直接用桶计算出来的。

对于 $i$ 的答案就是 ${A+B\choose k}+{C+A+B-D\choose k-i-D}$

时间复杂度 $O(n)$ ,注意特判 $a_i=0$ 的情况,这种情况下无论如何都不会改变自己的排名,答案为 $n\choose k$ 。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+5;
const int mod=998244353;

int n,k,a[N],b[N],flag[N];
int cnt,H[N<<1],hep1[N<<1],hep2[N<<1],fac[N],inv[N];

inline int modpow(int x,int y,int res=1) {
    for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
    return res;
}
inline int QAQ(int n,int m) {
    if(n<0||m<0||m>n) return 0;
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int main() {
    IN(n),IN(k);
    for(int i=1;i<=n;++i)
        IN(a[i]),H[++cnt]=a[i],H[++cnt]=b[i]=a[i]<<1,flag[i]=!a[i];
    sort(H+1,H+1+cnt);
    int last=cnt;cnt=1;
    for(int i=2;i<=last;++i) if(H[i]!=H[cnt]) H[++cnt]=H[i];
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(H+1,H+1+cnt,a[i])-H,hep1[a[i]]++,
        b[i]=lower_bound(H+1,H+1+cnt,b[i])-H,hep2[b[i]]++;
    fac[0]=1;
    for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=0;i<=n;++i) inv[i]=modpow(fac[i],mod-2);
    for(int i=1;i<=cnt;++i) hep1[i]+=hep1[i-1];
    for(int i=1;i<=cnt;++i) hep2[i]+=hep2[i-1];
    for(int i=1;i<=n;++i)
        if(!flag[i]) {
            int A=hep1[cnt]-hep1[a[i]-1]-1;
            int B=hep2[a[i]-1];
            int C=hep2[cnt]-hep2[a[i]-1]-1-A;
            int D=hep1[b[i]-1]-hep1[a[i]-1]-1;
            printf("%d\n",(QAQ(A+B,k)+QAQ(C+A+B-D,k-1-D))%mod);
        } else printf("%d\n",QAQ(n,k));
    return 0;
}
最后修改:2019 年 12 月 11 日 04 : 17 PM