这种DP是打死我也想不到的
学习自这篇神级博客
题目抽象一下就是
所以选出的排列根据p来排序一定是这种形态：
也就是很多博客里说的M型。
我们把一条边叫做一条链，也就是相邻两个数构成的即为一条链。（s，t是不算做链的）
我们的dp就是去维护这样一个形态。
我们考虑从小到大往排列里放数，对于一个“山峰”，其左右两边的数一定在它之前就放过了（因为比它小）。
那么对于这一个数（要求不是s也不是t。因为s或t一定是起点/终点，而不是中间的一个），它可以去合并两条链，也可以自己单独作为一个新链。
如果这个数是s或者t的话，可以选择新开一个链或是作为某一条链的起点/终点。
定义f[i][j]为走了i步，现在有j跳链的方案数
结果即为f[n-1][0]
#include<bits/stdc++.h> #define LL long long #define N 2003 #define mod 1000000007 using namespace std; int read() { int f=1,x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } LL f[N][N];// int main() { int n=read(),s=read(),t=read(); f[0][0]=1; for(int i=1;i<n;++i) for(int j=0;j<i;++j) { if(!f[i-1][j])continue; if(i!=s&&i!=t) { f[i][j+1]=(f[i][j+1]+f[i-1][j])%mod;//新开一条链 if(j)f[i][j-1]=(f[i][j-1]+(f[i-1][j]*j%mod*(((j-1)+(i>s)+(i>t))%mod))%mod)%mod;//j*(j-1)+j*(i>s)+j*(i>t) //考虑上S和T，如果他们已经在之前被操作了，那么S所在的链头可以作为被合并的前半部分，方案数+j， //同理T可以在后半部分，方案数+j } else { f[i][j]=(f[i][j]+f[i-1][j])%mod;//新开一条链，但s、t不算在链里 if(j)f[i][j-1]=(f[i][j-1]+f[i-1][j]*j%mod)%mod; } } printf("%lld ",f[n-1][0]); } /* */