题解：CF2207E2 N-MEX (Counting Version)
__Cyrene
·
·
题解
全场最短且最简单的代码。
首先考虑数组 b 的限制。假如当前是第 (n-i+1) 个 \operatorname{mex} ，不难发现， b[i...n] 必须满足：
- 不能包含 a_i （否则 \operatorname{mex} 永远不可能有 a_i）。
- 在 [0, a_i-1] 中正好少 n-i+1-1=n-i 个元素（这样才能让补出来的是第(n-i+1) 个）。
假设 c_i 表示前 i 个元素构成的集合里，落在
由于 $c_i$ 表示 $[0, a_i-1]$ 中出现过的元素，因此 $c_i$ 必定满足 $c_i\in[0,i]$ 。除此之外，要想存在这样的数组，还有需要一个条件，就是序列本身必须单调不升，即 $\forall i\in[2,n],a_i\leq a_{i-1}$ 。
证明也比较简单。我们都知道， $\operatorname{mex}$ 满足一个定理：设两个集合 $A$ , $B$ 满足 $A \subseteq B$，则对于 $\forall t \in \mathbb{N}_+, t\operatorname{mex}(B) \leq (t+1)\operatorname{mex}(A)$ 。随着 $i$ 的增大，集合元素个数肯定单调不降，又因为 $n-i+1$ 也就是式子里的 $t$ 单调不升，因此代入不等式，自然对应的 $\operatorname{mex}$ ，也就是 $a_i$ 单调不升成立。
接下来，就可以分类讨论 $a_i$ 和 $a_{i-1}$ 的情况，显然有两种：
1. 如果 $a_i = a_{i-1}$ ，那么此时就需要填一个小于 $a_i$ 且从未出现过的数，这些数一共有 $a_i-n+i=c_i$ 个。
2. 如果 $a_i < a_{i-1}$ ，那么需要插入一个要么被用过要么比 $a_i$ 大的数，而方法数就是 $i$ 。
根据乘法原理，直接乘起来即可。
最后说一下怎么优化时空复杂度（虽然题目不卡）。由于每一次遍历关注的对象都只有 $a_i$ 和 $a_{i-1}$ ，既不受前面的影响也不受后面的影响，因此完全没有必要使用数组，用两个滚动变量表示 $a_i$ 和 $a_{i-1}$ ，只用一次遍历，边输入边处理即可。
时间复杂度 $O(Tn)$ ，空间复杂度 $O(1)$ ，常数极小。
```cpp
#include<iostream>
#define LoveCyrene ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
signed main(){
LoveCyrene;
long long T, n, x, y, i, s;
cin >> T; while(T--){
cin >> n;
for (i = 1, y = n, s = 1; i <= n; i++, y = x){
cin >> x; long long k = x - n + i;
if(k > i || k < 0 || (x > y)) s = 0;
s = s * (x == y ? k : i) % 1000000007ll;
}
cout << s << '\n';
}
}