兔子的排列

题意：
给你一个长度为n的目标数列，源数列为0，1，2.....,n-1。有编号为0到n-2的操作数，你可以使用编号为i的操作数交换源数列第i个和第i+1个数，请你计算源数列变成目标数列操作数的排列方式有多少种？

思路：
分治+记忆化搜索
在[l,r]区间使用编号为i的操作数时数列将分为[l,i]和[i+1,r]二个小问题，因为每个编号的操作数都是唯一的，当使用了一个编号时，编号左右两边将没有联系了，所以可以划分为二个小问题，然后左边和右边二个小问题的解决方法之积乘以C(i-l(左边操作次数),r-l-1(区间操作次数-1，本次划分表示为先进行编号为i的操作))。因为左右不相关，所以当左右问题顺序确认时一共有（区间操作次数-1）操作，其中确认左边操作次数，右边次数填补空位，所以是乘C(i-l(左边操作次数),r-l-1(区间操作次数-1，本次划分表示为先进行编号为i的操作)).可以划分的标准为划分后左区间和等于目标左区间和并且划分后右区间和等于目标右区间和。

详情可以参考代码。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf=1e9+7;

int a[105], suma[105], b[105], sumb[105];   //b序列为源序列，a序列为目标序列

ll dp[105][105];

ll qpow(ll n,ll k)   // 快速幂函数
{
    ll z=1;
    while(k)
    {
        if(k&1)
        {
            z=z*n%inf;
        }
        n=n*n%inf;
        k>>=1;
    }
    return z;
}

ll C(int m,int n)     // 求组合数函数
{
    if(m>n-m)
    {
        m=n-m;
    }
    ll x=1, y=1;
    for(ll i=1, j=n;i<=m;i++,j--)
    {
        x=x*j%inf;
        y=y*i%inf;
    }
    return x*qpow(y,inf-2)%inf;
}

ll fun(int l,int r)   // 解决问题
{
    if(dp[l][r]!=-1)   // 记忆化
    {
        return dp[l][r];
    }
    if(l==r&&a[l]==b[l])
    {
        if(a[l]==b[l])
        {
            return 1;
        }
        return 0;
    }
    ll k=0;
    for(int i=l; i<r; i++)
    {
        int li=sumb[i-1]-sumb[l-1], ri=sumb[r]-sumb[i+1];
        li=li+b[i+1];
        ri=ri+b[i];
        if(li==suma[i]-suma[l-1]&&ri==suma[r]-suma[i])   //判断是否可以划分。
        {
            swap(b[i],b[i+1]);
            sumb[i]=sumb[i-1]+b[i];
            k=(k+fun(l,i)*fun(i+1,r)%inf*C(i-l,r-l-1)%inf)%inf;
            swap(b[i],b[i+1]);
            sumb[i]=sumb[i-1]+b[i];
        }
    }
    dp[l][r]=k;
    return k;
}

int main()
{
    int n;
    scanf("%d",&n);
    suma[0]=sumb[0]=0;
    memset(dp,-1,sizeof(dp));
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        a[i]++;
        suma[i]=suma[i-1]+a[i];
        b[i]=i;
        sumb[i]=sumb[i-1]+b[i];
    }
    cout << fun(1,n) << endl;
    return 0;
}