交换

图论

题面

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

• 交换$s[q_0],s[q_0+1]$
• 交换$s[q_1],s[q_1+1]$
  ...
  最后能使得排列$s=p$.
  问有多少个优美的排列,答案对$10^9+7$取模。

解析

这题构造数据挺难的，据说必须恰好有$n-1$个逆序对。
还是举个栗子通俗易懂。
比如，有一数列$\{a_n\}$为$\{2,5,1,3,6,4\}$，现在我们要把它转化为$\{1,2,3,4,5\}$。
怎么转呢？
虽然我们不能马上说出其操作整体顺序，但我们可以说出部分操作间的顺序。
我们肯定要把$5$挪到$位置2$，则有先后顺序$4,3,2$;同时，$1$在$2$前。
我们肯定要把$1$挪倒$位置3$，则有先后顺序$1,2$;同时，$3$在$2$前。
我们肯定要把$4$挪倒$位置6$，则有先后顺序$4,5$。
那个“同时”的附加条件保证的是先后顺序走了一边后，不会把已挪完的数再挪位置。
得到如此多的二元关系，我们就可以建图，前面的连一条边向后面的。
问题转化为“一笔画”该图的方案数。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
const int N=52;
const int mod=1e9+7;
il ll read(){
    RG ll d=0,w=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch<='9'&&ch>='0')d=d*10+ch-48,ch=getchar();
    return d*w;
}
int n,p[N],s[N],ans,f[N][N];
bool a[N][3];
il void end(){puts("0");exit(0);}
il void add(int i,int j){
    if(i==n||j==n)return;
    if(i<j){if(a[j][2])end();a[j][1]=1;}
    else{if(a[i][1])end();a[i][2]=1;}
}
int main()
{
    file();
    n=read();
    for(RG int i=1;i<=n;i++)p[i]=read()+1;  
    for(RG int i=1;i<=n;i++)
    {
        if(p[i]>i){
            for(RG int j=i;j<p[i]-1;j++)add(j,j+1);
            add(p[i],p[i]-1);
        }
        else if(p[i]<i){
            for(RG int j=i-1;j>p[i];j--)add(j,j-1);
            add(p[i]-1,p[i]);
        }
        else if(p[i]==i)end();
    }
    f[1][1]=1;
    for(RG int i=2;i<=n-1;i++)
    {
        RG int sum=0;
        if(!a[i][1]&&!a[i][2])
        {
            for(RG int j=1;j<i;j++)(sum+=f[i-1][j])%=mod;
            for(RG int j=1;j<=i;j++)f[i][j]=sum;
        }
        else if(a[i][2]){
            for(RG int j=i-1;j>=1;j--){
                (sum+=f[i-1][j])%=mod;f[i][j]=sum;
            }
        }
        else if(a[i][1]){
            for(RG int j=1;j<i;j++){
                (sum+=f[i-1][j])%=mod;
                f[i][j+1]=sum;
            }
        }
    }
    for(RG int i=1;i<=n-1;i++)(ans+=f[n-1][i])%=mod;
    printf("%d\n",ans);return 0;
}