兔子的排列

NC21348. 兔子的排列

描述

牛牛有N张牌，每张牌上有一个数字，所有牌上的数字构成了一个完整的0到N-1的排列
现在牛牛将牌从左往右放在桌子上，第i张牌（从0开始）上面写的是i
牛牛想要调整牌的顺序使得第i张牌上面的数字是p[i]
调整策略如下
有N-1只兔子，兔子的标号为0到N-2，第i只兔子可以交换第i与i+1张牌
一个兔子的排列q[0],q[1]..q[N-2]被称为一个好排列当且仅当，按照这个排列的顺序让兔子们去交换牛牛的牌，操作结束后第i张牌恰好是p[i]
请问一共有多少的好排列，答案对1e9+7取模

输入描述

第一行输入一个整数N (2 ≤ N ≤ 50)
第二行输入N个整数表示0到N-1的一个排列

输出描述

输出一个整数

示例1

输入:

3
1 2 0

输出:

示例2

输入:

2
0 1

输出:

示例3

输入:

4
2 0 3 1

输出:

示例4

输入:

4
1 0 3 2

输出:

示例5

输入:

20
1 3 0 5 2 7 4 8 10 6 12 9 14 11 16 13 18 15 19 17

输出:

716743312

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 116ms, 内存消耗: 29484K, 提交时间: 2022-09-18 16:47:58

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
typedef long long LL;
const int N=55,mod=1000000007;
int n,p[N];
LL ans,f[N][N][N][N],c[N][N];
bool vis[N][N][N][N];

LL dfs(int l,int r,int x,int y)
{
	if(vis[l][r][x][y]) return f[l][r][x][y];
	vis[l][r][x][y]=1;
	if(l==r)
	{
		f[l][r][x][y]=(x==y && x==l);
		return f[l][r][x][y];
	}
	LL rt=0;
	rep(i,l,r-1)
	{
		int L=(i==l?x:p[i]);
		int R=(i+1==r?y:p[i+1]);
		rt=(rt+dfs(l,i,i==l?R:x,R)*dfs(i+1,r,L,i+1==r?L:y)%mod*c[r-l-1][i-l])%mod;
	}
	return f[l][r][x][y]=rt;
}

int main()
{
	scanf("%d",&n);
	rep(i,0,n) c[i][0]=1;
	rep(i,1,n) rep(j,1,i) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	rep(i,1,n) scanf("%d",&p[i]),++p[i];
	ans=dfs(1,n,p[1],p[n]);
	printf("%lld\n",ans);
	return 0;
}