AT_abc295_e [ABC295E] Kth Number 题解

· · 题解

题目意思我不叙述了，题面已经讲得很清楚了。

老套路，枚举 i 表示 a_k 不少于 i。挨个算方案数就成。

为了满足条件，序列中需要 n-k+1 个数 \ge i。

首先减去序列中本来就 \ge i 的数，然后再从剩下的 0 里边挑就行。

假设还需要 x 个 \ge i 个数并且一共有 y 个 0。

不再需要（x \le 0）和 0 数量不足（x > y）先给特判掉。

然后就可以推出一个显而易见的式子：

\sum^{y}_{j=x}=\binom{y}{j} \times \left(\frac{m-i+1}{m}\right)^j \times \left(\frac{i-1}{m}\right)^{(k-j)}

那么就结束了。记得预处理组合数，以及备好快速幂函数。

代码也还不算长。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2005;
const LL mod = 998244353;
LL n,m,k,a[N],c[N][N],ans=1;
void init(){
    c[0][0]=1;
    for(int i=1;i<=n;i++){
        c[i][0]=1,c[i][i]=1;
        for(int j=1;j<i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
    return;
}
LL QP(LL x,LL y){LL as=1;while(y){if(y&1)as=(as*x)%mod;x=(x*x)%mod,y>>=1;}return as;}
int main(){
    cin>>n>>m>>k;init();
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2;i<=m;i++){
        LL x=n-k+1,y=0;
        for(int j=1;j<=n;j++)x-=(a[j]>=i),y+=(!a[j]);
        if(x<0||x>y){ans+=(x<0);continue;}
        LL mul=(m-i+1)*QP(m,mod-2)%mod,div=mod+1-mul;
        LL now=QP(mul,x)*QP(div,y-x)%mod;div=QP(div,mod-2);
        for(int j=x;j<=y;j++)ans=(ans+c[y][j]*now%mod)%mod,now=now*mul%mod*div%mod;
    }
    cout<<ans<<"\n";
    return 0;
}