Jellyfish and OEIS
题意
题解
恭恭敬敬给致远磕大头。
首先我们将原序列分割成很多块，使得每一块都是相对位置的排列。且这一块内不可分割出另外的块。
例如：\([3,1,2][5,4]\)，而 \([1,2,3]\) 是不合法的，因为他可以被分割为 \([1][2][3]\)。
在进行这一步操作之后，我们发现我们的序列被划分成了很多中括号。而需要满足的条件即为：\(r_i> m_{l_i}\) 。
我们进一步思考之后发现这有点问题。
\([3,2,1]\)，这个排列。
我们发现虽然他整体是一个部分，但是中间的 \(2\) ,同样也是一个在位置上的排列，那么我们此时就获得了嵌套：
\([3,[2],1]\)。
我们进一步思考性质，会发现一个非常显然而又经典事情：所有的括号只包含或相离而不相交。
这个是显然的。
这时候我们将整张图画出来，会发现我们的图形成了一个森林。
这时候我们得到了树状结构，那么如果我们可以解决由某一层递推到上一层的问题。那整道题目就迎刃而解了。
此时我们考虑嵌套的充要条件是什么：
首先下一层的 \([\ ]\) 我们不去管它，那剩下的位置呢？
经过思考后我们可以发现剩下的位置一定要满足他任意一个子序列都必须满足它里面的元素不是他的排列，即
即他是一个单层机构，只能被表达为 \([a_1,a_2,...,a_n]\)。
充分性是显然的：如果满足这个条件，那么一定框不出来，那么满足就一定合法。
接下来证明必要性：
在这里我们证明逆否条件：若不满足则一定不合法：
假设我们发现有一段 \([l,r]\) 不满足条件，即 \([a_l,...,a_r]\) 是 \([l,...,r]\) 的一个排列，那么我们此时可以将这一段框起来，那这就与下一层外没有嵌套相违背了，所以逆否条件得证，则原命题得证。
这样我们只要能够求出 \(h(n)\)：即任意一个子序列都必须满足它里面的元素不是他的排列的个数，我们就可以解决这道题了。
“那么我们按照题目要求我们做的。”
我们通过打表打出前 7 项 \(h(n)\) ，然后oeis，就能够得到 \(h(n)\) 的公式：
\(h(n)=(n-1)h(n-1)+\sum_{j=2}^{n-2}(j-1)\cdot h_j\cdot h_{n-j}\)
具体证明在这里不作解释。
那么此时我们整理一下式子：
设 \(dp_{l,r}\) 表示区间 \([l,r]\) 是合法的区间的方案数，\(f_{l,r,p}\) 用来辅助转移，表示 \([l,r]\) 这个区间，下一层空了 \(p\) 个位置的方案数。
转移是简单的：
\(dp_{l,r}=\sum_{p=2}^{len}h(p)\cdot f_{l+1,r-1,p-2}\)（因为我们要保证最左端和最右端不是括号组成的，否则就会分裂出去了）
当然要特判 \(l=r\) 的情况以及 \(r\) 是否 \(>m_l\) 。
\(f_{l,r,p}=f_{l,r-1,p-1}+\sum_{t=1}^{len}f_{l,r-t,p}\cdot dp_{r-t+1,r}\)
最后输出 \(f_{1,n,0}\) 就是答案（因为我们的最终序列是森林）。
代码
//think twice,code once
//think once,debug forever
const int MAXN=220,mod=1e9+7;
int h[MAXN];
int F[MAXN];
int a[MAXN];
int dp[MAXN][MAXN];
int f[MAXN][MAXN][MAXN];
int n;
void init()
{
h[1]=1;
forn(i,2,200)
{
h[i]=mul(i-1,h[i-1]);
forn(j,2,i-2)
{
h[i]+=mul(j-1,mul(h[j],h[i-j]));modcg(h[i]);
}
}
}
void solve()
{
MOD.init(mod);
init();
cin>>n;
forn(i,1,n)
{
cin>>a[i];
}
if(a[1]==n)
{
cout<<0<<endl;
return;
}
forn(l,1,n)
{
f[l][l-1][0]=1;
}
forn(len,1,n)
{
forn(l,1,n)
{
int r=l+len-1;
if(r>n)
{
break;
}
if(r>a[l])
{
if(l==r)
{
dp[l][r]=1;
}
else
{
forn(p,2,len)
{
dp[l][r]+=mul(h[p],f[l+1][r-1][p-2]);modcg(dp[l][r]);
}
}
}
forn(p,0,len)
{
if(p)
{
f[l][r][p]+=f[l][r-1][p-1];modcg(f[l][r][p]);
}
forn(t,1,len)
{
f[l][r][p]+=mul(f[l][r-t][p],dp[r-t+1][r]);modcg(f[l][r][p]);
}
}
}
}
cout<<f[1][n][0]<<endl;
}