题解：CF2084E Blossom

· · 题解

简要题意

给定一个长度为 n 的“部分排列”数组 a（元素来自 [0,n-1]，其中若干位置为 -1 表示缺失，且所有非 -1 元素互不相同），将所有 -1 用缺失的数补成合法排列后，对每个形成的排列计算其所有非空子段的 mex 之和，并把这些和值对所有可能填充方案求和，结果对 10^9+7 取模输出（多测试；1\le t\le 1000，每个用例 1\le n\le 5000，-1\le a_i<n，非 -1 的 a_i 两两不同，且所有用例的 n 之和 \le 5000）。

题解

经过一些思考，会发现钦定一个区间的 mex 等于 x 不如钦定大于等于 x（因为后者不用担心 mex 更大的问题，好处理），这样也可以求出答案，因为有 \sum_{i\ge 1} i*\mathrm{way}[\mathrm{mex}=i]=\sum_{i\ge 1}\mathrm{way}[\mathrm{mex}\ge i]。

接下来考虑：做到大于等于一个 mex 值要填的数字个数是固定的。例如要做到 mex\ge 5，(1,2,4) 出现过且 (0,3) 未出现过，则一定是找区间内两个 -1 填成 (0,3)（要求1）、而且这个子区间必须包含 (1,2,4) 三个数字（要求二）。符合条件的子区间对答案的贡献是 C_k^c(m-c)!c!，之中 k 是子区间内 -1 个数、m 是原数组内 -1 个数、c 是大于等于目标 mex 值所至少需要的 -1 个数（上例中为 2），式子的含义是在 k 个 -1 中选择 c 个用来填缺失的数字、其余的 -1 随意填写。问题变成了如何快速求这样的子区间个数。

定义 s_k 表示满足要求 2 的包含 k 个 -1 的子区间个数，在最开始令 s_k 等于所有包含 k 个 -1 的子区间个数。为了便于处理要求 2，我们按 mex 从小到大来处理，定义 l,r 是所有小于 mex 的已出现数字中最靠左与最靠右的下标，考虑到 \mathrm{mex}=i 时若 i-1 在原数组有出现则用其更新 l,r，更新 l,r 时可以通过暴力删除不再合法的子区间的方式来更新 s 数组，由于每个区间只会被删一次，所以这样做的复杂度正确。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
#define all(x) (x.begin()),(x.end())
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;

const ll mod=1e9+7;
ll fac[5010],inv[5010];
ll qp(ll a,ll b,ll mod=mod){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;b>>=1;
    }return ans;
}
ll getInv(ll x,ll p=mod){
    return qp(x,p-2,p);
}
ll getC(ll n,ll m,ll p=mod){
    return fac[n]*inv[m]%p*inv[n-m]%p;
}
// 动机：做到大于等于一个mex值要填的数字个数是固定的。
// 例如要做到mex>=5，[1,2,4] 出现过且 [0,3] 未出现过，则一定是找两个 -1 填成 [0,3]、而且这个子区间必须包含 [1,2,4] 三个数字
// s[i] : 包含了当前的 [l,r] 作为子区间、且恰有 i 个 -1 的子区间个数
ll T,n,a[5010],pos[5010],pre[5010],s[5010];
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    fac[0]=inv[0]=1;
    rep(i,1,5005){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=getInv(fac[i]);
    }
    cin>>T;
    while(T--){
        cin>>n;
        memset(pos,0,sizeof(pos));
        memset(s,0,sizeof(s));
        rep(i,1,n){
            cin>>a[i];
            pos[a[i]]=i;
            pre[i]=pre[i-1]+(a[i]==-1);
        }
        rep(i,1,n){
            rep(j,i,n){
                s[pre[j]-pre[i-1]]++;
            }
        }
        int l,r;
        l=r=-1; // [l,r] 是包含了 [1,mex-1] 中已确定位置的所有数的最小区间，因此要做到 mex 的区间一定要包含 [l,r]
        ll ans=0,c=0; // c 表示 <mex 的有多少个全数组都未出现
        rep(mex,1,n+1){
            if(pos[mex-1]){
                if(l==-1){ // 特判第一次加入出现过的数，将跨过他的区间贡献都减掉
                    rep(i,1,pos[mex-1]-1){
                        rep(j,i,pos[mex-1]-1){
                            s[pre[j]-pre[i-1]]--;
                        }
                    }
                    rep(i,pos[mex-1]+1,n){
                        rep(j,i,n){
                            s[pre[j]-pre[i-1]]--;
                        }
                    }
                    l=r=pos[mex-1];
                }
                else{
                    if(pos[mex-1]<l){
                        rep(i,pos[mex-1]+1,l){
                            rep(j,r,n){
                                s[pre[j]-pre[i-1]]--;
                            }
                        }
                        l=pos[mex-1];
                    }
                    else if(pos[mex-1]>r){
                        rep(i,1,l){
                            rep(j,r,pos[mex-1]-1){
                                s[pre[j]-pre[i-1]]--;
                            }
                        }
                        r=pos[mex-1];
                    }
                }
            }
            else{
                c++;
            }
            rep(k,c,pre[n]){
                ans=(ans+s[k]*getC(k,c)%mod*fac[c]%mod*fac[pre[n]-c])%mod;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}