P14639 solution

4C45 · 2025-12-04 15:19:05 · 题解

我不喜欢组合数学。

P14639

记 k 出现了 t_k 次，小于 k 的总共出现 a_k 次。

:::info[省流]

:::

计算得到以 x 开头的满足条件的序列的方案数。可以把小于 x 的排一个单调不升序列，大于 x 的排一个单调不降序列，然后把 x 插入合并出一个长 n-1 的序列跟在 x 后面得到以 x 开头的合法序列。

把 x 并到单调不升序列合并有 \dbinom{n-1}{a_x+t_x-1} 种方案，并到单调不降序列合并有 \dbinom{n-1}{a_x} 种方案，容斥掉数重的 x 恰好填满前 t_x 项的方案数 \dbinom{n-t_x}{a_x}，把 x 枚举一下预处理阶乘逆元可以 \mathcal O(n+V) 做。

:::info[Code]

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ir(i,a,b) for(int i=b;i>=a;i--)
using namespace std;
const int P=998244353,maxn=1e6+114;
ll ifac[maxn],fac[maxn];
ll qpow(ll a,ll b)
{
    ll res=1,bas=a;
    while(b)
    {
        if(b&1) res=res*bas%P;
        bas=bas*bas%P;
        b/=2;
    }
    return res;
}
ll C(ll n,ll k)
{
    if(n<k) return 0;
    return fac[n]*ifac[k]%P*ifac[n-k]%P;
}
ll a[maxn];
int main()
{
    fac[0]=1;
    rep(i,1,1e6) fac[i]=fac[i-1]*i%P;
    ifac[1000000]=qpow(fac[1000000],P-2);
    ir(i,0,1e6-1) ifac[i]=ifac[i+1]*(i+1)%P;
    int n;
    cin>>n;
    rep(i,1,n)
    {
        int t;
        cin>>t;
        a[t]++;
    }
    ll ans=0,s=0;
    rep(i,1,1e6)
    {
        ans=(ans+C(n-1,s+a[i]-1)+C(n-1,s)-C(n-a[i],s)+P)%P;
        s+=a[i];
    }
    cout<<ans<<endl;
}

:::