题解：CF2084E Blossom

Unnamed114514 · 2025-04-08 22:07:45 · 题解

首先我们把 MEX(a_{l,r}) 转化为 \sum\limits_{k=0}^{n-1}[\forall i\in [0,k],i \in a_{l,r}]，容易发现这显然是成立的，因为当 k<MEX 时，值显然为 1，当 k\ge MEX 时，MEX 一定不出现，所以为 0。然后一个 MEX 会贡献 [0,MEX-1] 的 k，恰好为 MEX 次。

我们先来想一个 O(n^3) 的最暴力的解法。枚举 k,l,r，记 [l,r] 中的 -1 个数为 c_1，我们需要的 -1 个数为 c_2，总的 -1 个数为 c_3，容易得到该对 (k,l,r) 的贡献是 {c_1\choose c_2}c_2!(c_3-c_2)!。

这个做法是 O(n^3) 的，注意到 c_2 随着 k 的递增简单处理即可，c_3 是定值，考虑钦定 c_1 统计合法的 [l,r]。

• 若 [0,k] 均未出现，那么区间可以在任意位置。我们统计全局每种 -1 数量的区间有多少个，记作 t。然后枚举 c_1，容易发现式子是 t_{c_1}{c_1\choose c_2}c_2!(c_3-c_2)。

• 若 [0,k] 中有数出现过，我们记 i 出现的位置为 pos_i，那么选择的区间必须包含 pos_0,\cdots,pos_k，即包含 [\min\{pos_i\},\max\{pos_i\}]。

注意到我们直接算包含是不好算的，但是容易发现随着 k 的增大，包含它的区间只减不增，因此每个区间只会删一次，每次更新区间的时候直接把它从 t 里面扣掉就行了。

常数很小，跑得很快，从时间上来说是 CF 的最优解，但是空间打不过。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=5005,mod=1e9+7;
int T,n,a[N],s[N],pos[N],fac[N],inv[N],t[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=5000;++i){
        fac[i]=1ll*fac[i-1]*i%mod;
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    }
    for(int i=2;i<=5000;++i) inv[i]=1ll*inv[i]*inv[i-1]%mod;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=0;i<n;++i) pos[i]=-1;
        for(int i=1;i<=n;++i){
            cin>>a[i];
            s[i]=s[i-1];
            if(~a[i]) pos[a[i]]=i;
            else ++s[i];
        }
        for(int i=0;i<=s[n];++i) t[i]=0;
        for(int l=1;l<=n;++l) for(int r=l;r<=n;++r) ++t[s[r]-s[l-1]];
        int ll=0,rr=-1,ans=0,cnt=0;
        for(int i=0;i<n;++i){
            if(~pos[i]){
                if(rr==-1){
                    for(int l=1;l<pos[i];++l) for(int r=l;r<pos[i];++r) --t[s[r]-s[l-1]];
                    for(int l=pos[i]+1;l<=n;++l) for(int r=l;r<=n;++r) --t[s[r]-s[l-1]];
                    ll=rr=pos[i];
                } else if(pos[i]>rr){
                    for(int l=1;l<=ll;++l) for(int r=rr;r<pos[i];++r) --t[s[r]-s[l-1]];
                    rr=pos[i];
                } else if(pos[i]<ll){
                    for(int l=pos[i]+1;l<=ll;++l) for(int r=rr;r<=n;++r) --t[s[r]-s[l-1]];
                    ll=pos[i];
                }
            } else ++cnt;
            for(int k=cnt;k<=s[n];++k) ans=(ans+1ll*t[k]*fac[k]%mod*inv[k-cnt]%mod*fac[s[n]-cnt])%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}