专栏文章

题解：CF2084E Blossom

炸炸鸡块君
CF2084E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mink42ap
此快照首次捕获于
2025/12/02 03:43
3 个月前
此快照最后确认于
2025/12/02 03:43
3 个月前
查看原文

简要题意

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

题解

经过一些思考，会发现钦定一个区间的 mex 等于 xx 不如钦定大于等于 xx（因为后者不用担心 mex 更大的问题，好处理），这样也可以求出答案，因为有 ∑i≥1i∗way[mex=i]=∑i≥1way[mex≥i]\sum_{i\ge 1} i*\mathrm{way}[\mathrm{mex}=i]=\sum_{i\ge 1}\mathrm{way}[\mathrm{mex}\ge i]。
接下来考虑：做到大于等于一个 mex 值要填的数字个数是固定的。例如要做到 mex≥5mex\ge 5，(1,2,4)(1,2,4) 出现过且 (0,3)(0,3) 未出现过，则一定是找区间内两个 −1-1 填成 (0,3)(0,3)（要求1）、而且这个子区间必须包含 (1,2,4)(1,2,4) 三个数字（要求二）。符合条件的子区间对答案的贡献是 Ckc(m−c)!c!C_k^c(m-c)!c!，之中 kk 是子区间内 −1-1 个数、mm 是原数组内 −1-1 个数、cc 是大于等于目标 mex 值所至少需要的 −1-1 个数（上例中为 22），式子的含义是在 kk 个 −1-1 中选择 cc 个用来填缺失的数字、其余的 −1-1 随意填写。问题变成了如何快速求这样的子区间个数。
定义 sks_k 表示满足要求 22 的包含 kk 个 −1-1 的子区间个数，在最开始令 sks_k 等于所有包含 kk 个 −1-1 的子区间个数。为了便于处理要求 22，我们按 mex 从小到大来处理，定义 l,rl,r 是所有小于 mex 的已出现数字中最靠左与最靠右的下标，考虑到 mex=i\mathrm{mex}=i 时若 i−1i-1 在原数组有出现则用其更新 l,rl,r，更新 l,rl,r 时可以通过暴力删除不再合法的子区间的方式来更新 ss 数组，由于每个区间只会被删一次，所以这样做的复杂度正确。
C
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...