不明白出题人的脑回路是不是被宇宙射线改变过 /jy。
题目给出了若干个区间，要我们计算满足每个区间都不是对应下标的排列的数量，正着计算不满足要求的数量是困难的，我们将其容斥，转化为钦定一些区间要求其必须满足它是对应下标的排列，在下文中，我们称这样的区间为一个约束。
我们设约束的集合为 \(U\)，设 \(f(S)\) 表示属于 \(S\) 的约束必须满足，其它不作要求的排列个数，转化后的答案可以表示为:
\[\sum_{S\subset U}^{U} (-1)^{|U|-|S|} f(S) \]尽管题目中给定的 \(S\) 在一定程度上是连续的，但是如果一组约束中出现了相交的约束就会让求解变得困难，我们可以先考虑两个相交的约束有什么性质。
观察到如果两组约束 \([l_1,r_1]\)、\([l_2,r_2]\) 满足 \(l_1 <l_2 <r_1<r_2\) 那么我们可以将其拆为 \([l_1,l_2-1]\)、\([l_2,r_1]\)、\([r_1+1,r_2]\) 三组不交的约束，且约束力等价，对于更多的约束我们同样可以这么拆分。
更进一步地，每拆分一次后，容斥系数都会改变，且方案数仍然不变，如果 \([r_1+1,r_2]\) 这组约束满足 \(r_2 \leq m_{r_1+1}\) 拆分前后的贡献就会相互抵消。
这启发我们考虑使一些存在相交约束的 \(S\) 的贡献与其他的相消，继续考虑上述的拆分过程，虽然 \([r_1+1,r_2]\) 不一定合法，但是 \([l_1,l_2-1]\) 一定是合法的，拆分前如果不存在这个区间，这组方案就与加上这个区间的方案约束力相同容斥系数相反。
我们上述的描述实际上构建了一个有相交区间集合到其本身的双射，且对应集合约束力相同容斥系数相反，贡献可以相互抵消，于是我们就可以不用考虑有相交区间的 \(S\) 的贡献。
如果我们拉出一个剩下的 \(S\)，可以发现区间现在只有包含和不交两种关系，构成了一个树形结构，我们可以考虑使用区间 dp 批量计算这样的贡献。
具体地，设 \(f_{l,r}\) 表示 \([l,r]\) 这个区间的数是其下标的一个排列时包含于其中的钦定方案的方案数乘容斥系数之和，但是我们强制选择 \([l,r]\) 且不考虑其容斥系数，这等价于计算区间 \([l,r]\) 其本身的答案。设 \(g_{l,r,x}\) 表示 \([l,r]\) 这个区间有 \(x\) 个没有被覆盖到的点的的钦定方案的方案数乘容斥系数之和，有转移：
\[\sum_{x=0}^{r-l+1} g_{l,r,x}\times x! \rightarrow f_{l,r} \]\[g_{l+1,r,x+1}+\sum_{k=l}^{min(r-l,m_l)}(-f_{l,k})\times g_{k+1,r,x} \rightarrow g_{l,r,x} \]\[g_{l,r,0}-f_{l,r}\rightarrow g_{l,r,0} \]其中第一个式子由定义易得，而考虑我们安排 \([l,r]\) 的方案时是要在左边放一个散点还是拼上一个区间，前面要加上负号是因为在计算 \(f_{l,r}\) 时我们没有考虑 \([l,r]\) 所带来的容斥系数，我们拼上 \([l,r]\) 的意义是选择 \([l,r]\) 的所有钦定方案数之外，强制加上我们计算 \(f_{l,r}\) 时没有选择的 \([l,r]\) ，不选择 \([l,r]\)，只选择小区间的情况会在逐个拼接小区间的情况中被考虑，这里多加了个区间要乘上 \(-1\)。
最后，由于计算 \(g_{l,r,0}\) 时我们没有考虑选择整体区间 \([l,r]\) 的情况，所以最后 \(g_{l,r,0}\) 还要减去 \(f_{l,r}\) 表示加上选择 \([l,r]\) 的方案数乘上多选带来的 \(-1\)。
初值： \(g_{i,i,1}=1\) 和 \(g_{i,i,0}=-1\)，你也可以在代码中写成 \(g_{i,i-1,1}=1\)。
答案： \(f_{l,r}\)。
时间复杂度 \(O(n^4)\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 205
#define mod 1000000007
#define ll long long
using namespace std;
ll f[N][N],g[N][N][N];
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
ll m[N],fac[N];
int main(){
ll n=read();
for(ll i=1;i<=n;i++)m[i]=read();
fac[0]=1;
for(ll i=1;i<N;i++)fac[i]=(1ll*fac[i-1]*i)%mod;
for(ll i=1;i<=n+1;i++)g[i][i-1][0]=1;
for(ll len=1;len<=n;len++){
ll tp=n-len+1;
for(ll l=1;l<=tp;l++){
ll r=l+len-1;
for(ll x=1;x<=len;x++)g[l][r][x]=g[l+1][r][x-1];
for(ll k=l;k<=min(m[l],r-1);k++){
for(ll x=0;x<=r-k;x++){
g[l][r][x]=(g[l][r][x]+1ll*g[k+1][r][x]*(mod-f[l][k]))%mod;
}
}
for(ll x=0;x<=len;x++)f[l][r]=(f[l][r]+1ll*g[l][r][x]*fac[x])%mod;
if(r<=m[l])g[l][r][0]=(g[l][r][0]-f[l][r]+mod)%mod;
}
}
cout<<(m[1]>=n?0:f[1][n]);
}