题目描述
$MYC$在$NOI2018$中，遇到了$day1T2$这样一个题，题目是让你求有多少“好”的排列。$MYC$此题没有获得高分，感到非常惭愧，于是回去专心研究排列了。如今数排列的题对$MYC$来说已经是小菜一碟了。于是$MYC$想考考你，扔给你了一个非常$naive$的数排列题给你。
给定一个$\{0,1,2,3,...,n-1\}$的排列$p$。一个$\{0,1,2,...,n-2\}$的排列$q$被认为是优美的排列，当且仅当$q$满足下列条件：
对排列$s=\{0,1,2,3,...,n-1\}$进行$n–1$次交换。
$1.$交换$s[q_0],s[q_0+1]$
$2.$交换$s[q_1],s[q_1+1]$
...
最后能使得排列$s=p$。
问有多少个优美的排列，答案对$10^9+7$取模。
原题见：$SRM517-600$
输入格式
第一行一个正整数$n$。
第二行$n$个整数代表排列$p$。
输出格式
仅一行表示答案。
样例
样例输入：
3
1 2 0
样例输出：
1
数据范围与提示
样例解释：
$q=\{0,1\}\{0,1,2\}\rightarrow\{1,0,2\}\rightarrow\{1,2,0\}$
$q=\{1,0\}\{0,1,2\}\rightarrow\{0,2,1\}\rightarrow\{2,0,1\}$
数据范围：
$20\%$：$n\leqslant 10$
$50\%$：$n\leqslant 50$
$70\%$：$n\leqslant 300$
$100\%$：$n\leqslant 5,000$
题解
题目可以转化为：一个大小为$n-1$的排列，某些地方限制了相邻两数的大小关系，求方案数。
考虑$DP$，设$dp[i][j]$表示进行到了第$i$个数，第$i$个数在前$i$个数中是第$j$小的方案数。
可以预处理出来哪些位置需要往左或右移即可。
注意一些限制，以向左移为例，第$i$次交换的位置要在第$i-1$次交换之前，反之同理。
这样做出来时间复杂度是$\Theta(n^3)$的，前缀和优化即可。
因为数据点没有给不满足的情况，所以下面代码中没有判不满足的情况，即$pos_i=i$。
时间复杂度：$\Theta(n^2)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n;
int a[5001];
bool com[5001];
long long dp[5001][5001],g[5001][5001];
long long ans;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
if(i<a[i]){com[i-1]=1;com[a[i]-1]=1;}
else for(int j=a[i];j<i-1;j++)com[j]=1;
dp[0][1]=g[0][1]=1;
for(int i=1;i<n-1;i++)
for(int j=1;j<=i+1;j++)
{
if(com[i-1])dp[i][j]=(dp[i][j]+g[i-1][i]-g[i-1][j-1]+mod)%mod;
else dp[i][j]=(dp[i][j]+g[i-1][j-1])%mod;
g[i][j]=(g[i][j-1]+dp[i][j])%mod;
}
for(int i=1;i<n;i++)ans=(ans+dp[n-2][i])%mod;
printf("%lld",ans);
return 0;
} rp++