题目的意思就是一个序列本来是0,1,2...n-1.然后要你变成p[0],p[1],p[2]...p[n-1],通过交换相邻的两个数每两个相邻的数都可以交换一次,你可以选择交换的顺序.问你有多少种交换顺序?
很有意思的一道记忆化搜索题目,emm,大佬教我做的...
具体怎么做呢?就是一个典型的分治,加记忆化搜索..分治就是枚举要交换的顺序,具体在哪个点交换,很显然的一个结论,假如那个点交换了,就相当于断开了,然后就可以分治了...具体再记忆化搜索下就可以了~dp[l][r][st][ed].表示区间l-r中开头为st,结尾是ed,然后交换的好序列的方案数是多少.然后复杂度是O(n^5)
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=52;
ll dp[N][N][N][N];
bool mp[N][N][N][N];
ll p[N];

ll fact[N];
inline ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

inline ll C(ll n,ll m)
{
    ll res=fact[n];
    return res*qp(fact[m],mod-2)%mod*qp(fact[n-m],mod-2)%mod;
}

void init()
{
    fact[1]=1;fact[0]=1;
    for(int i=2;i<=N-1;i++)
    {
        fact[i]=i*fact[i-1]%mod;
    }
}

inline ll dfs(ll l,ll r,ll st,ll ed)
{
    ll res=0,x1,y1,x2,y2;
    if(l==r)//递归出口.
    {
        if(st==p[l]) return 1;
        return 0;
    }
    if(mp[l][r][st][ed]) return dp[l][r][st][ed];
    mp[l][r][st][ed]=true;
    for(ll i=l;i<r;i++)//枚举交换位子. st i+1 i+2 ... ed
    {
        if(l==r-1)
        {
            x1=ed,y1=ed;
            x2=st,y2=st;
        }
        else if(i==l)
        {
            x1=i+1,y1=i+1;
            x2=st,y2=ed;
        }
        else if(i+1==r)
        {
            x1=st,y1=ed;
            x2=i,y2=i;
        }
        else
        {
            x1=st,y1=i+1;
            x2=i,y2=ed;
        }
        //cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl;
        res=(res+dfs(l,i,x1,y1)*dfs(i+1,r,x2,y2)%mod*C(r-l-1,i-l))%mod;
    }
    return dp[l][r][st][ed]=res;
}

int main()
{
    ll n;
    scanf("%lld",&n);
    init();
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&p[i]);
        p[i]++;
    }
    printf("%lld\n",dfs(1,n,1,n));
    return 0;
}