给定序列 \(m_i\)，求有多少排列 \(p\) 满足：对于满足 \(l \le r \le m_l\) 的所有 \((l,r)\)，\(p_{l \sim r}\) 都不是 \(l \sim r\) 的排列。答案对 \(10^9 + 7\) 取模。
\(n \le 200\)，时限 \(\text{2.0s}\)。
限制形如要求全都不合法，我们考虑容斥，即在所有 \(\sum(m_i - i + 1)\) 个区间中钦定一些，要求其对应的 \(p_{l \sim r}\) 必须是 \(l \sim r\) 的一个排列，计算方案数乘上容斥系数后的和。
我们发现，如果钦定的区间存在相交的部分，这个方案数其实并不是很好计算。注意到，对于钦定的两个区间 \([a,b],[c.d]\)，若满足 \(a < c \le b < d\)，那么其实可以把它们拆成 \([a,c - 1],[c,b],[b+1,d]\)。这样方案数不变，但由于多了一条限制，容斥系数会乘上 \(-1\)，于是它们对答案的贡献会相互抵消。更进一步地，如果两组限制方案数相同而区间数奇偶性不同，贡献就能够相互抵消，基于此，我们继续发掘一些更好的性质。
现在考虑一组限制 \(b\)，满足其中任意区间都和 \(b\) 中的另一区间有交。我们每次取出 \(b\) 中两个有交的区间，按上面那样拆掉，再扔回 \(b\) 并去重，这样有限次之后能够得到另一组限制 \(t\)。对于任意一组限制 \(c\)，我们都可以把它写成某个 \(b\) 加上一些无交（但是可能相互包含，或者和 \(b\) 中的某些区间包含但无交）区间的形式。设 \(b\) 对应的 \(t\) 中有 \(k\) 个区间，那么对于每个区间，选或者不选都不影响答案，这样的方案数一共有 \(2^k\) 种。当 \(k \geq 1\) 时，其中一定恰好有一半是奇数一半是偶数，所以这部分贡献会直接抵消完。
而只有当 \(k=0\)，即不存在某两个区间相交时，容斥系数会由无交区间确定，并被保留下来。也就是说，我们仅需要考虑区间构成树结构的情况，这是一个非常大的进步。
此时满足一组限制的方案数容易计算：答案显然就是每一层散点个数阶乘的积。于是可以区间 DP，设 \(f_{l,r}\) 表示只考虑包含于 \(l,r\) 的区间，且假设 \([l,r]\) 这个区间已被选（但不贡献容斥系数），所有方案的容斥系数乘上方案数之和。\(g_{l,r,x}\) 表示只考虑包含于 \([l,r]\) 的区间，这一层有 \(x\) 个散点的所有方案的容斥系数乘上方案数之和。转移考虑当前的 \(l\) 是否新开出一个区间：
- 不开新区间，\(l\) 会成为一个散点，则 \(g_{l,r,x} \gets g_{l+1,r,x-1}\)。
- 新开一个区间，设之为 \([l,k](k \le m_l)\)，则 \([l,r]\) 部分的散点全都会被盖住，即 \(g_{l,r,x} \gets f_{l,k} \times g_{r + 1,k,x}\)。
在 \(g\) 转移完后令 \(f_{l,r} = \sum g_{l,r,x} \times x!\) 即可。最后一个小问题就是在转移 \(g\) 的时候我们时没管新开的区间是 \([l,r]\) 的情况，在这里可以利用 \(f\) 直接补上。总时间复杂度 \(\mathcal{O}(n^4)\)，常数很小，可以通过。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int N = 205, mod = 1e9 + 7;
bool Mbe;
int n, lim[N], f[N][N], g[N][N][N];
int fc[N];
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> lim[i];
for (int i = 1; i <= n + 1; i++) g[i][i - 1][0] = 1;
fc[0] = 1;
for (int i = 1; i <= n; i++) fc[i] = 1LL * fc[i - 1] * i % mod;
for (int L = 1; L <= n; L++)
for (int l = 1, r = l + L - 1; r <= n; l++, r++) {
for (int x = 1; x <= r - l + 1; x++) {
g[l][r][x] = g[l + 1][r][x - 1];
}
for (int k = l; k <= min(lim[l], r - 1); k++)
for (int x = 0; x <= r - (k + 1) + 1; x++) {
g[l][r][x] = (g[l][r][x] + 1LL * g[k + 1][r][x] * (mod - f[l][k]) % mod) % mod;
}
for (int x = 0; x <= r - l + 1; x++) {
f[l][r] = (f[l][r] + 1LL * fc[x] * g[l][r][x] % mod) % mod;
}
if (lim[l] >= r) g[l][r][0] = (g[l][r][0] + mod - f[l][r]) % mod;
}
int ans = f[1][n];
if (lim[1] == n) ans = 0;
cout << ans << "\n";
// cout << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}