题目
题目描述
WYF正试图用一个栈来构造一棵树，现在他已经构造了n个元素作为树的节点，只要将这n个元素依次入栈出栈就可以形成一棵树了。当然，这个问题与树并没有关系，所以它叫做WYF的栈。每次你可以入栈一个新元素或者当栈非空时出栈一个元素，n个元素必须依次入栈，而WYF希望其中第m个元素入栈之后，栈中恰好有k个元素，现在他想知道一共有多少种入栈出栈顺序满足这个条件。
输入描述
第一行一个正整数T，表示数据组数。(1<=T<=10000)
对于每组数据包含一行三个正整数n,m,k。
输出描述
对于每组数据输出一个正整数表示答案。
由于答案可能过大，所以只需要输出对10^9+7取模后的答案
示例1
输入
2
3 3 3
3 3 2
输出
1
2
示例2
输入
5
10 3 2
10 2 2
10 7 5
10 6 2
10 7 6
输出
6864
11934
2200
3780
924
示例3
输入
2
5 4 4
5 2 1
输出
5
14
备注
1<=n,m,k<=10^6
题解
知识点：卡特兰数。
设 \((x,y)(x \geq y)\) 表示入栈 \(x\) 次，出栈 \(y\) 次。
这里需要求两次卡特兰数：
- 从 \((0,0)\) 到 \((m-1,m-k)\) ，因为要保证第 \(m\) 次入栈立刻就能得到 \(k\) 个元素。
- 从 \((m,m-k)\) 到 \((n,n)\) ，但这里要反过来求，因为 \((m,m-k)\) 不是标准的起点但 \((n,n)\) 可以是，此时需要把横纵坐标交换看，就等效于 \((1,1)\) 到 \((n-m+k,n-m)\) 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
namespace Number_Theory {
const int N = 1e7 + 7;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int fact[N], invfact[N];
void init(int n) {
fact[0] = 1;
for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;
invfact[n] = qpow(fact[n], P - 2);
for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;
}
}
namespace CNM {
using namespace Number_Theory;
int C(int n, int m) {
if (n == m && m == -1) return 1; //* 隔板法特判
if (n < m || m < 0) return 0;
return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;
}
}
namespace Catalan {
int F(int n, int m) {
if (n < m || m < 0) return 0;
return (CNM::C(n + m, m) - CNM::C(n + m, m - 1) + P) % P;
}
int H(int n) { return F(n, n); }
}
bool solve() {
int n, m, k;
cin >> n >> m >> k;
cout << 1LL * Catalan::F(m - 1, m - k) * Catalan::F(n - m + k, n - m) % P << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
CNM::init(2e6);
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}