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;
}
第一次发博客和题解，主要目的是为了记录学习过程啦，也希望各位dalao能给本蒟蒻一点建议
标签：right,int,Codeforces,Round,pos,Div,mex,left From： https://www.cnblogs.com/zwh-zzz/p/16755547.html