题解：P11505 [NordicOI 2018] Mysterious Array

一眼丁真秒掉的计数题，开心。

看到这个题想起来 ABC262Ex Max Limited Sequence。区别就是这题要求排列，那题没要求。

首先处理约束信息，因为要求的是区间最小值，所以我们可以用 set 处理出每个位置的值域下界，也就是所有包含该位置的区间约束的最大值。

然后对于一个最小值约束

\min=x

，可能存在若干对要求

(l,r)

，由于这是一个排列每个数只能出现一次，但是必须所有区间都合法。所以

x

必然出现在这些区间取交得出来的

[L,R]

中。

接下来考虑填入数字，对于每个位置是形如

a_i\ge x

的形式。如果按照序列顺序填入不好判断哪些数字用过了，所以我们考虑按照值域约束从大到小填入，这样子对于当前扫描到的数

x

，因为约束是

\ge x

，

[x,n]

之内的所有数就一视同仁了。先考虑确定

x

，就是在

[L,R]

之内选择一个数，那么是

R-L+1

种方案。

接着考虑安排其他

\ge x

位置的答案，我们就是要在

[x+1,n]

之内给他们分配（注意

x

这个时候已经被用过了），然后之前也用过若干个数字（所有满足值域下界

>x

的位置个数），设一共有

num

个，那么就是有

n-x-num

个数可以被我们利用，填入

y-1

个位置（

y

是要求

a_i\ge x

的位置个数，由于已经填入了

x

，所以是

y-1

），就是

A^{n-x-num}_{y-1}

。

时间复杂度

O(n\log n)

。

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
const int mod=1e9+7;
void add(int &x,int y){ x=x+y>=mod?x+y-mod:x+y; }
void sub(int &x,int y){ x=x<y?x-y+mod:x-y; }
void chkmax(int &x,int y){ x=x>y?x:y; }
void chkmin(int &x,int y){ x=x<y?x:y; }
struct limit{
	int l,r,x;
}lim[maxn];  
vector<int> pos[maxn],vec[maxn],ad[maxn],del[maxn]; 
int mn[maxn],fac[maxn],inv[maxn],ans=1,cnt=0,n,m; multiset<int> s;
int qpow(int x,int k){
	int res=1;
	for(;k;k>>=1){
		if(k&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;
	}
	return res;
}
void end(){ cout<<"0"; exit(0); }
int A(int N,int M){
	if(N==0||M==0) return 1;
	return 1ll*fac[N]*inv[N-M]%mod; 
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m; fac[0]=inv[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=qpow(fac[n],mod-2); for(int i=n-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	for(int i=1;i<=m;i++){
		cin>>lim[i].l>>lim[i].r>>lim[i].x;
		ad[lim[i].l].pb(i); del[lim[i].r+1].pb(i);
		vec[lim[i].x].pb(i);
	}
	for(int i=1;i<=n;i++){
		for(auto z:ad[i]) s.insert(-lim[z].x);
		for(auto z:del[i]) s.erase(s.find(-lim[z].x));
		if(s.size()){ int z=*s.begin(); mn[i]=-z; pos[-z].pb(i); }
		else pos[0].pb(i);
	}
	for(int i=n;i>=1;i--){
		if(!vec[i].size()) continue;
		int L=-n,R=n;
		for(auto z:vec[i]) chkmax(L,lim[z].l),chkmin(R,lim[z].r);
		int num=0,rest=n-i-cnt;
		if(rest+1<(int)pos[i].size()||L>R) end();
		for(auto z:pos[i])
			if(L<=z&&z<=R) num++;
		ans=1ll*ans*num%mod; num=pos[i].size()-1;
		ans=1ll*ans*A(rest,num)%mod;
		cnt+=pos[i].size();
	}
	ans=1ll*ans*fac[pos[0].size()]%mod;
	cout<<ans;
	return 0;
}

题解：P11505 [NordicOI 2018] Mysterious Array

文章操作

相关推荐

评论

题解：P11505 [NordicOI 2018] Mysterious Array