CF1809G 题解

dAniel_lele · 2024-06-04 12:20:11 · 题解

不难发现比赛一定是设初始胜者为 t，t 吊打一些人后（即 a_x<a_t-k）被某个人吊打（即 a_t<a_x-k），然后依次类推。

设 p_i 表示第一个大于等于 a_i-k 的位置。

考虑 dp_i 表示目前胜者为 i 的方案数。

考虑 p_i\sim i-1 中的人，显然这些人应该放在 i 之后。注意到我们已经确定了 p_i 个人的相对位置（即，前 p_{i-1} 个人和 i），于是 i\to j 的转移就是 dp_i\times\binom{n-p_i-1}{p_j-p_i-1}\times(p_i-p_j-1)!\to dp_j。化简可以得到 dp_i\times\frac{(n-p_i-1)!}{(n-p_j)!}\to dp_j。维护 dp_i\times(n-p_i-1)! 的前缀和，设为 pre_i，则 dp_i=pre_{p_i-1}\times\frac{1}{(n-p_j)!}。

总复杂度 O(n\log n) 或 O(n)（如果你愿意使用双指针求 p_i 的话）。

#include <bits/stdc++.h>
#define int long long
#define s(i,j) ((i-1)*m+j)
#define add(i,j) ((i+j>=mod)?i+j-mod:i+j)
using namespace std;
const int mod=998244353;
int a[1000005],p[1000005],fac[1000005],inv[1000005];
int dp[1000005],pre[1000005];
int qp(int a,int b){
    int ans=1;
    while(b){
        if(b&1) (ans*=a)%=mod;
        (a*=a)%=mod;
        b>>=1;
    }
    return ans;
}
void init(){
    fac[0]=1; for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
    inv[1000000]=qp(fac[1000000],mod-2); for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    init();
    int n,k; cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i];
    if(a[n]-a[n-1]<=k){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++) p[i]=lower_bound(a+1,a+n+1,a[i]-k)-a;
    dp[0]=1,pre[0]=fac[n-1];
    for(int i=1;i<=n;i++){
        (dp[i]+=pre[p[i]-1]*inv[n-p[i]])%=mod;
        pre[i]=(pre[i-1]+dp[i]*fac[n-p[i]-1])%mod;
    }
    cout<<dp[n];
    return 0;
}