Codeforces Round #804 (Div. 2) C(组合 + mex)

本萌新的第一篇题解qwq

题目链接：

题意：

给定一个\(\left [0,n-1 \right ]\)的排列，问有多少个排列，所有的子区间的mex值和原排列的mex值相同，求方案数对1e9 + 7 取模。

分析：

对于这个问题，我们要先知道，一个区间的mex是该区间没有出现过的最小正整数。所以对于\(\left [0,n-1 \right ]\)中的每个数字\(i\)，我们要知道的是\(\left [0,i-1 \right ]\)数字出现的位置情况，通过模拟样例，我们是可以发现，\(\left [0,i-1 \right ]\)区间中数字的左边的最右和右边的最左这块区域内，\(i\)是可以任意放置的，所以答案就可以更新为:

\[ans = ans * (r - l + 1 - i) % mod
\]

解释一下这里的公式的含义，\((r- l + 1)\) 是待定区间长度，因为\([0,i-1]\)个数被占掉了，所以要减去\(i\)个。

代码：

void solve(){
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> pos(n); // 记录数字出现的位置
	for (int i = 0;i < n;i ++) {
		cin >> a[i];
		pos[a[i]] = i;
	}
	int ans = 1;
	int l = Inf, r = -Inf;
	for (int i = 0;i < n; i++) {
		if(pos[i] >= l && pos[i] <= r) {
			ans = ans * (r - l + 1 - i) % mod;
		}
		l = min(l,pos[i]);
		r = max(r,pos[i]);
	}
	cout << ans << endl;
}