F. Jellyfish and OEIS
sol
一个区间不是一个排列不太好做，考虑反向容斥，考虑钦定一个区间为一个排列。
但直接这么做还是很困难，然而本题存在一个性质，两个区间交叉的部分，其容斥系数可以抵消，也就是可以不考虑相交的区间。感性理解一下，是正确的。
那么我们钦定的区间就具有如下位置关系：要么包含，要么不交。这样容斥会方便许多，记钦定的区间集合为 \(S\)，容斥系数即为 \((-1)^{|S|}\)。
记 \(f_{l,r}\) 表示区间 \([l,r]\) 为 \([l,r]\) 的一个排列时带容斥系数的方案数，\(g_{l,r,x}\) 表示区间 \([l,r]\) 内含有 \(x\) 个散点的带容斥系数的方案数，实现上由于散点任意排列的方案数即为 \(x!\) 易求，计算 \(g\) 时可以忽略这个系数，转移时乘上即可。
按区间长度升序进行区间 DP，存在下述几种转移方式：
- 左端点为散点，有 \(g_{l,r,x}\gets g_{l,r,x}+g_{l+1,r,x-1}\)。
- 区间 \([l,k]\) 被钦定为 \([l,k]\) 的排列，满足 \(k\le m_l\land k<r\)，有 \(g_{l,r,x}\gets g_{l,r,x}-f_{l,k}g_{k+1,r}\)。
- 我们先计算出 \(f_{l,r}=\sum\limits_xx!g_{l,r,x}\)。
- 若 \(r\le m_l\)，\(g_{l,r,0}\gets g_{l,r,0}-f_{l,r}\)。
额外解释一下最后两步，\(f_{l,r}\) 是钦定区间 \([l,r]\) 为 \([l,r]\) 的排列的方案数，而 \(g_{l,r,0}\) 并不要求区间 \([l,r]\) 是 \([l,r]\) 的排列，因此 \(g_{l,r,0}\) 要更新上 \(f_{l,r}\) 而 \(f_{l,r}\) 无需额外的更新。
最后需要特判 \(m_1=n\) 的情况，此时无解。否则答案即为 \(f_{1,n}\)。
code
const int N=205;int n;
int m[N];
mint fc[N],iv[N];
mint f[N][N],g[N][N][N];inline void Main(){cin>>n;fc[0]=1;rep(i,1,n)fc[i]=fc[i-1]*i;rep(i,1,n)cin>>m[i];rep(i,0,n)g[i+1][i][0]=1;rep(l,1,n)rep(i,1,n-l+1){int j=i+l-1;rep(x,1,j-i+1)g[i][j][x]+=g[i+1][j][x-1];rep(k,i,min(m[i],j-1))rep(x,0,j-k)g[i][j][x]-=f[i][k]*g[k+1][j][x];rep(x,0,j-i+1)f[i][j]+=g[i][j][x]*fc[x];if(j<=m[i])g[i][j][0]-=f[i][j];}if(m[1]==n)return put(0),void();put(f[1][n]);
}