[AT_abc431_f] [ABC431F] Almost Sorted 2 题解

· · 题解

条件就是在说，前一项最多比后一项大 D。

考虑从大到小地填数。设当前填到数值 i，c_i 表示序列中有多少个 i，那么这些数只能插到当前序列的头部，或者满足 x\le i+D 的 x 后方。设 s_i=s_{i-1}+c_i 即 c 的前缀和，则可以插入的空数量为 T=s_{i+D}-s_i+1。

下面分析插入的方案数怎么计算。第一个被插入的 i 有 T 种方案，第二个在此基础上可以选择插入到第一个后方，有 T+1 种方案，以此类推。由于每个 i 完全相同，而前面却对 i 钦定了顺序，所以最后还要除以 c_i!。推知方案数为 \displaystyle\frac{T(T+1)\cdots(T+c_i-1)}{c_i!}=\frac{(T+c_i-1)!}{(T-1)!c_i!}=\binom{T+c_i-1}{c_i}=\binom{s_{i+D}-s_{i-1}}{c_i}。

最终答案如下。

\boxed{\prod_{i=1}^{10^6}\binom{s_{i+D}-s_{i-1}}{c_i}}

计算组合数，设 p=998244353，可以先求出 \text{frac}_i=(i\times\text{frac}_{i-1})\bmod p 表示 i 的阶乘，然后费马小定理求出 \text{inv}_{10^6}=(\text{frac}_{10^6})^{p-2}\bmod p=(\text{frac}_{10^6})^{-1}\bmod p。然后递推 \text{inv}_{i-1}=(i\times\text{inv}_i)\bmod p，于是 \displaystyle\binom{n}{m}=(\text{frac}_n\times\text{inv}_m\times\text{inv}_{n-m})\bmod p。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
using namespace std;
typedef long long ll;
const ll maxn=1000007,p=998244353;
ll n,D,c[maxn],s[maxn],ans,frac[maxn],inv[maxn];
ll qpow(ll a,ll b){ll E=1; for(;b;b>>=1,a=a*a%p)if(b&1) E=E*a%p; return E;}
void init(void){
    frac[0]=1;
    for(ll i=1;i<maxn;i++) frac[i]=frac[i-1]*i%p;
    inv[maxn-1]=qpow(frac[maxn-1],p-2);
    for(ll i=maxn-1;i>=1;i--) inv[i-1]=inv[i]*i%p;
}
ll C(ll a,ll b){return (a<b||b<0)?0:frac[a]*inv[b]%p*inv[a-b]%p;}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>D,init();
    for(ll i=1,x;i<=n;i++) cin>>x,c[x]++;
    for(ll i=1;i<maxn;i++) s[i]=s[i-1]+c[i];
    ans=1;
    for(ll i=maxn-1;i>=1;i--)if(c[i]) ans=ans*C(s[min(maxn-1,i+D)]-s[i-1],c[i])%p;
    cout<<ans<<"\n";
    return 0;
}

::::