题号 NC21348
名称 兔子的排列

戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：喵渺淼妙的死忠粉
题目的意思就是一个序列本来是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;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目1月28日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴