[CEOI2016] kangaroo题解

P5999 [CEOI2016] kangaroo

一类插入式的dp。

对于这道题，我们得先做出一个转化，依次考虑每个数插到哪个位置，于是变成了求 \(1\)~\(n\) 的排列同时满足每个位置上的元素要么大于要么小于它左右两边的数的排列个数（当然还要满足 \(s\) 必须在排列首，\(t\) 必须在排列尾）。显然的插入dp，令 \(f_{i,j}\) 表示已经插到第 \(n\) 个数，同时有 \(j\) 个段，转移：

• 当 \(i=s\) 或 \(i=t\) 时，\(f_{i,j}=f_{i-1,j-1}+f_{i-1,j}\)
• 否则，\(f_{i-1,j+1}=f_{i-1,j+1} \times j + f{i-1,j-1} \times (j-(i>s)-(i>t))\)

解释：这一类以段为状态的插入dp，一般有

• 在已有的段新增元。容易发现，如果不是在插入首或尾的数是会不合法的，所以这个转移仅在处理首尾元素。
• 新开段。只需要注意下不要影响到固定的首尾。
• 合并段。

code：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<iostream>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long LL;
const int N=2e3+100;
const LL MOD=1e9+7;
int n,t,s;
LL f[N][N];

int main()
{
	scanf("%d%d%d",&n,&s,&t);
	f[0][0]=1ll;
	rep(i,1,n)
		rep(j,1,i)
			if(i==s||i==t)(f[i][j]=f[i-1][j-1]+f[i-1][j])%=MOD;
			else (f[i][j]=f[i-1][j+1]*j%MOD+f[i-1][j-1]*(j-(i>s)-(i>t))%MOD)%=MOD;
	printf("%lld",f[n][1]);
	return 0;
}