交换

DP 排列

题面

给定一个$\{1,2,3,4,...,n\}$的排列$p$。一个$\{1,2,3,...,n-1\}$的排列$q$被认为是优美
的排列,当且仅当$q$满足下列条件:
对排列$s=\{1,2,3,4,...,n\}$进行$n–1$次交换。

• 交换 $s[q1],s[q2 + 1]$
• 交换 $s[q2],s[q2 + 1]$
  ...

最后能使得排列$s = p$
问有多少个优美的排列,答案对$10^9+7$取模。

解析

首先显而易见的是这个排列有$n-1$对逆序对。

能影响每个位置的值的交换，只有两个：

• 其前面一个的交换，会把自己与前一个数字交换；
• 其自己的交换，会把自己与后一个数字交换。

然后想想把$i$调到其在$s$中的位置$pos[i]$需要满足哪些条件。
若$pos[i]<i$，说明$i$要向左调，因此其前面一个的交换应比其自己的交换靠前。
而在$pos[i]+1～i-1$中，它们自己的交换应比其前面一个的交换靠前，否则无法保证$i$到达$pos[i]$。

这样就能得出这$n-1$个交换的相对顺序。
设$f[i][j]$为统计到第$i$个位置的交换，该交换在排列中排第$j$个。
然后再枚举上一个位置交换排第几个，依限制$DP$转移即可，复杂度$O(n^3)$。
发现可以转移的部分不是前缀就是后缀，可以前缀和优化，复杂度降到$O(n^2)$。

嗯，还有个只能让蒟蒻挂掉的细节：
$f[i-1][j]->f[i][j]$的转移是合法的。
因为从前往后转移的过程实际上是插入数的过程，所以如果第$i$个位置的交换在第$j$个，后面所有交换的位置都会后移一位。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=5e3+100,mod=1e9+7;
int n,pos[N],ans,op[N],tag=1,f[N][N],g[N][N];
bool vis[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!=-'-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
//op前面操作先于后面操作1 or 前面操作后于后面操作2
il void Pre()
{
  fp(i,1,n)
    {
      if(pos[i]==i) tag=0;
      if(pos[i]<i)
    {
      if(pos[i]!=1) op[i]|=1;
      fp(j,pos[i]+1,i-1) op[j]|=2;
    }
      if(pos[i]>i)
    {
      if(pos[i]!=n) op[i]|=2;
      fp(j,i+1,pos[i]-1) op[j]|=1;
    }
    }
  fp(i,1,n-1) if(op[i]==3) tag=0;
}
int main()
{
  n=gi();
  fp(i,1,n) pos[gi()+1]=i;
  Pre();
  if(!tag) return puts("0"),0;
  f[1][1]=g[1][1]=1;
  fp(i,2,n-1)
  {
    fp(j,1,i)
    {
      if(op[i]==0) (f[i][j]+=g[i-1][i-1])%=mod;
      if(op[i]==1) (f[i][j]+=g[i-1][j-1])%=mod;
      if(op[i]==2) (f[i][j]+=g[i-1][i-1]-g[i-1][j-1]+mod)%=mod;
    }
    fp(j,1,i) g[i][j]=(g[i][j-1]+f[i][j])%mod;
  }
  printf("%d\n",g[n-1][n-1]);
  return 0;
}