CF1699C The Third Problem 题解

· · 题解

来一篇与出题人情投意合的题解（其实就是无脑枚举）

一开始没有什么头绪，可以从小开始枚举寻找规律。

定义 p_i 表示数字 i 在 a 中的下标。考虑 0 的位置，因为 \operatorname{mex}\{a_{p_{0}}\}=1，因此 b 中 0 的位置也是 p_0 （可以发现样例也是如此）

考虑 1 的位置，假设其在 0 的右边（可以发现在左边和右边的情况是相似的），即 p_1>p_0,\operatorname{mex}\{a_{p_0}\cdots a_{p_1}\}\geq 2，我们可以发现 b 中的 1 必定在 p_0 与 p_1 之间，共有 (p_1-p_0) 种选择（ p_0 不能选 ）

那么对于 2 而言，当它处在 0 与 1 之间的时候， 序列 a 即为 [\cdots0\cdots2\cdots1\cdots],\operatorname{mex}\{a_{p_0}\cdots a_{p_0}\}\geq 3，对应地：\operatorname{mex}\{b_{p_0}\cdots b_{p_1}\}\geq 3，也就是说 2 必定在 p_0 与 p_1 之间，共有 (p_1-p_0-1) 种选择（ p_0 及 p_1 都不能选 ）；当它处在 0 与 1 之外的时候，序列 a 即为 [\cdots 2\cdots 0\cdots 1\cdots] 或 [\cdots 0\cdots 1\cdots 2\cdots] 此时 \operatorname{mex}\{a_{p_2}\cdots a_{p_0}\}=1 或 \operatorname{mex}\{a_{p_1}\cdots a_{p_2}\}=0， 2 在 b 中的位置仅能为 p_2

然后枚举 3,4\cdots 懒得写了

到这里我们可以发现规律了，除了 0 之外，第 k 个数若在 0 至 k-1 组成的区间中，那么它就有 (r-l-k) 种选择（如果你看不出来，可以参考其他大佬的思路），若不在，说明只有一种情况。最后把这些情况全部乘在一起即可。

【代码】 
#include<cstdio>
#include<iomanip>

using namespace std;
const int N=1e5+50,MOD=1e9+7;
int a[N],pos[N],n,t;
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;
        int l=pos[0],r=pos[0];
        long long ans=1;
        for(int i=1;i<n;i++){
            if(pos[i]<l) l=pos[i];
            else{
                if(pos[i]>r) r=pos[i];
                else ans*=(long long)(r-l+1-i),ans%=MOD; 
            }
        }
        printf("%lld\n",ans%MOD);
    }
    return 0;
}