题意
给定一个序列 \(m\) ，你需要求出满足以下性质排列 \(p\) 的个数，对大质数取模：
- 对于任意 \(l,r\) ，\(p_{l...r}\) 为一个 \([l,r]\) 的排列与 \(r \le m_l\) 不同时成立。
Sol
考虑从题目的奇怪限制入手（也只能从这里入手），我们记一个区间 \([l,r]\) 是坏的当且仅当区间中元素是 \([l,r]\) 的排列，记一个区间是非常坏的当且仅当区间是坏的且 \(r \le m_l\)。
我们考虑一定存在一些性质，不然出题人为什么要把限制搞成连续的一段 \([l,m_l]\) 呢？可以考虑固定左端点，然后向右移动右端点，在区间扩展的过程中，若只要移动到了一个非常坏的区间，就可以立马停止，因为两个左端点相同的非常坏区间显然没有同时存在的必要。
接下来就是若干个左端点互不相同的区间，考虑分析此时区间 \([l1,r1]\) 和 \([l2,r2]\) 互相之间的联系，不妨设 \(l1<l2\) ，那么有三种情况：
- \(l1<r1<l2<r2\)，此时两个区间相互独立。
- \(l1<l2<r1<r2\)，此时可以发现，两个区间的交集也是一个坏区间，也就是说原来两段区间分裂成了三段 \([l1,l2),[l2,r1),[r1,r2)\)。
- \(l1<l2<r2<r1\)，同理可将原区间划分为 \([l1,l2),[l2,r2),[r2,r1)\)。
在经过了上述修正之后，所有坏区间互不相交且从左至右顺序排列，记 \(p_l\) 表示以 \(l\) 为左端点的坏区间的最小右端点，不存在为 \(n+1\)。我们需要让任意的 \(l\) 均满足 \(p_l>m_l\)。
为了避免算重，我们定义 \([l,r]\) 为原始坏区间当且仅当不存在 \([l1,r1]\) 为 \([l,r]\) 真子集且其为坏区间，显然原始坏区间，显然上述操作的边界就是若干个原始坏区间。
我们要求同时满足 \(n\) 个形如 \(p_l>m_l\) 限制的排列个数，自然地考虑容斥（或称二项式反演），定义 \(f_k\) 表示内部有 \(k\) 个原始坏区间的方案数，\(g_k\) 表示钦定内部存在 \(\ge k\) 个原始坏区间的方案数，则有：
.
我们考虑扩展这一式子，进行区间 dp，设 \(f_{l,r}\) 表示 \(p_{l...r}\) 是一个 \([l,r]\) 的排列，且其子区间均不满足这一性质的方案数，\(g_{l,r,x,0/1}\) 表示 \([l,r]\) 中有 \(x\) 个未被覆盖的元素，其余元素均被恰好一个坏区间覆盖，且当前有奇数/偶数个坏区间的方案数，转移如下：
其中 o=0/1.
这个式子中需要强制钦定 \(mid \le r\)，也就是新产生的坏区间不能为空（不然容斥就失效了）。
这个式子还有一个小问题是会 \(g(l,r,x,o)\) 和 \(f(l,r)\) 循环转移，把他们提到外面更新即可，时间复杂度小常数 \(\mathcal{O}(n^4)\)。
代码：
#include<bits/stdc++.h>
#define N 205
#define M 1000000007
#define I 1ll
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define MP make_pair
using namespace std;
int f[N][N],g[N][N][N][2],n,ri[N],fac[N];
void inc(int &x,int y){x+=y; if(x>=M) x-=M;}
signed main(){
scanf("%d",&n),fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=I*fac[i-1]*i%M;
for(int i=1;i<=n;i++) scanf("%d",&ri[i]);
if(ri[1]==n) return !printf("0");
for(int i=1;i<=n+1;i++) f[i][i-1]=g[i][i-1][0][0]=1;
for(int ln=1;ln<=n;ln++) for(int l=1;l+ln-1<=n;l++){
int r=ln+l-1; for(int x=0;x<=r-l+1;x++) for(int o=0;o<2;o++){ if(x) g[l][r][x][o]=g[l][r-1][x-1][o];
for(int t=l+1;t<=r;t++) if(r<=ri[t]) inc(g[l][r][x][o],I*g[l][t-1][x][o^1]*f[t][r]%M);
}for(int i=0;i<=r-l+1;i++)
inc(f[l][r],I*(g[l][r][i][0]+M-g[l][r][i][1])%M*fac[i]%M);
if(r<=ri[l]) inc(g[l][r][0][1],f[l][r]);
}return !printf("%d\n",f[1][n]);
}
Sol2
想不到吧
考虑从析合树的角度思考，继承上文所有定义，并定义集合 \(S\) 为初始时所有坏区间构成的集合，我们构造一棵这样子的树：
- 若集合为空，树为空。
- 否则，若集合中存在一个区间 \([l,r]\) 使得存在一个子集 \(T\) ，使得 \(T = \{[l,p_0],[p_0,p_1] ... [p_k,r]\}\)，那么删除区间 \([l,r]\) ，换句话说，删除所有可以由子区间紧密衔接拼成的大区间。
- 对于剩下的极长区间，从 root （代表区间 \([1,n]\)）向所有极长区间分别连边，并对每个极长区间执行二操作。
在这样的树上可以发现一个性质：除开叶节点以外，每个节点 \([l,r]\) 的左右两侧，即 \(l\) 和 \(r\) 位置的元素，一定是未被其任何一个子节点覆盖过的。容易使用反证法证明该结论。
考虑在这样的一棵树上，我们不在使用容斥，而是转为直接计算合法方案数，即直接要求每个节点 \([l,r]\) 都满足 \(r >m_l\)。
定义：
- \(f(l,r)\) 表示对于树上的一个点（极长坏区间）\([l,r]\)，其有多少种排列方式，使得其能成为树上一个点。
- \(g(l,r)\) 表示对于树上的一簇点，即若干个 \([l0,r0]\) 紧密衔接而成的大区间，有多少种排列方式。
- \(h(l,r,x)\) 表示对于一个区间 \([l,r]\)，其中有若干位置被树上的一些簇区间占据，剩下的为空白，且空白点有 \(x\) 个，的排列方式。
- \(a(x)\) 表示一个长度为 \(x\) 的排列，其中不包含任何一个坏区间的方案数。
对于 \(h\) 的转移，分作两类：末尾元素为空白点，从 \(h(l,r-1,x-1)\) 转移；末尾元素为非空白点，从 \(h(l,t,x) * g(t+1,r)\) 转移。
对于 \(g\) 的转移，考虑枚举最后一个极长坏区间的位置，从 \(g(l,p-1) * f(p,r)\) 转移。
tips：在本题中，g 与 h 可以合并，新的状态和 h 的转移类似，之所以保留 g 的状态是因为在某些题目中，关于左右端点还有别的性质，如果一次性乘到 h 的 \(O(n^4)\) 上会使复杂度爆炸，这里实际上是一种分部转移的思想，当转移形式过于复杂时，可以考虑进行分部转移，将转移拆解为中间变量的迭代过程，通俗的说，是“不把鸡蛋放在一个篮子里”。
对于 \(f\) 的转移，考虑从 \(h(l+1,r-1,x-2) * a(x)\) 转移过来，之所以要减二正如上文所言，两端元素必须不能被覆盖。
本题中，由于要求答案，应将若干个 \(f\) 数组合并起来，作为 root \([1,n]\) 的儿子，这个可以使用简单的线性 dp，或者称之为一种特殊的背包实现。
代码使用了 apiad 杜老师的代码，他直接将 \(g,h\) 合并成一个数组使代码更为简单。但正如笔者所言，这样的分部 dp 可以理清写题时的思路，也可以在 \(h\) 还要支持维护更多信息的时候避免不同维度之间互相干扰，是解决复杂动态规划问题的利器。
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=210;
int a[N];
int n;
ll f[N],f0[N][N],f1[N][N],g[N][N][N];
int main() {
scanf("%d",&n);
rep(i,1,n+1) scanf("%d",&a[i]);
//rep(i,1,n+1) a[i]=n;
f[0]=f[1]=1;
rep(i,2,n+1) {
f[i]=(ll)(i-1)*f[i-1]%mod;
rep(j,2,i-1) f[i]=(f[i]+(ll)(j-1)*f[j]%mod*f[i-j])%mod;
}
rep(l,1,n+2) g[l][l-1][0]=1;
per(l,1,n+1) rep(r,l,n+1) {
// consect
if (r-l<=1) {
f0[l][r]=1;
} else {
rep(c,2,r-l+2) {
f0[l][r]=(f0[l][r]+(ll)g[l+1][r-1][c-2]*f[c])%mod;
}
}
if (r<=a[l]) f0[l][r]=0;
f1[l][r]=f0[l][r];
rep(k,l,r) f1[l][r]=(f1[l][r]+f0[l][k]*f1[k+1][r])%mod;
rep(c,1,r-l+2) {
g[l][r][c]=(g[l][r][c]+g[l+1][r][c-1])%mod;
}
rep(k,l,r+1) rep(c,0,r-k+1) g[l][r][c]=(g[l][r][c]+f0[l][k]*g[k+1][r][c])%mod;
}
printf("%lld\n",f1[1][n]);
}
```