kangaroo 题解

转化题意：

我们需要求满足以下条件的序列的数目：

1. 长度为 (n)。
2. 如果当前为第 (i) 个数，第 (i-1) 和 (i + 1) 个数要么同时大于第 (i) 个数, 要么同时小于第 (i) 个数。

题解：

设 (f_{i, j}) 表示 前 (i) 个数分 (j) 段且任意一段满足要求的方法数。

1. 当 (i ot = s)，(i ot = t) 时，可以将 (i) 看做单独的一段，可以插在任意位置。若 (i > s) 就不能插在首，若 (i > t) 就不能插在尾，所以分别要减去 (1) 个方案数。贡献为 ((j - c) imes f_{i - 1, j - 1})，(c = (i > s) + (i > t))。

   (i) 还可以用作两端的合并，因为 (i) 为从小到大枚举，一定比两边大，所以一定是可以合并的，贡献为 (j imes f_{i - 1, j +1})。

   所以, (f_{i, j} = (j - c) imes f_{i - 1, j - 1} + j imes f_{i- 1, j +1})。

2. 当 (i = s)，(i = t) 时，(i) 只能放在首或尾，或者单独成一段。
   (f_{i, j} = f_{i-1, j - 1} + f_{i - 1, j})。

#include <iostream>
#include <cstdio>
#define orz cout << "AK IOI"
#define int long long 

using namespace std;
const int mod = 1e9 + 7;
const int maxn = 2e3 + 10;

inline int read()
{
	int f = 0, x = 0; char ch = getchar();
	while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
inline void print(int X)
{
	if(X < 0) {X = ~(X - 1); putchar('-');}
	if(X > 9) print(X / 10);
	putchar(X % 10 + '0');
}
int n, s, t, f[maxn][maxn];
signed main()
{
	
    n = read(), s = read(), t = read();
    f[1][1] = 1;
    for(int i = 2; i <= n; i++)
    {
    	if(i != s && i != t)
			for(int j = 1; j <= i; j++)
				f[i][j] = (f[i - 1][j - 1] * (j - (i > s) - (i > t)) + f[i - 1][j + 1] * j) % mod;
		else 
		for(int j = 1; j <= i; j++)
			f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
	}
	print(f[n][1]); 
	return 0;
}