C.打牌的贝贝(卡特兰数)

后手赢的条件是 先手的每张票都都可以出一张更大的。

可以转成括号序列，先手的牌是左括号，后手的牌是右括号，只要是合法的括号序列后手就赢。因此后手的答案就是卡特兰数h(n)=C2nnn+1h(n)=\dfrac{C_{2n}^n}{n+1}h(n)=n+1C2nn​​

总方案数为C2nnC_{2n}^nC2nn​ ，因此先手赢得次数就是C2nn−h(n)C_{2n}^n-h(n)C2nn​−h(n)

预处理阶乘 、阶乘逆元、逆元。就可以O(1)O(1)O(1)查询。

时间复杂度：O(n)O(n)O(n)

#include 
using namespace std;#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)typedef long long LL;constexpr int N = 1e6 + 10, md = 1e9 + 7;int T, n, m;
LL f[N], fac[2 * N], ifac[N], inv[N];LL fpow(LL a, int b)
{LL res = 1;while(b){if(b & 1)res = res * a % md;a = a * a % md;b >>= 1;}return res;
}LL finv(int i)
{   return fpow(i, md - 2);
}void init()
{int R = N - 8; // 1e6 + 2fac[0] = 1;rep(i, 1, 2 * R) //阶乘逆元fac[i] = fac[i - 1] * i % md;ifac[R] = fpow(fac[R], md - 2);dwn(i, R, 2) //阶乘倒数逆元ifac[i - 1] = ifac[i] * i % md;rep(i, 1, R) //倒数逆元inv[i] = fac[i - 1] * ifac[i] % md;f[0] = 1;R -= 2;//最大的i + 2也被算出来了lop(i, 0, R){ //计算卡特兰数f[i + 1] = f[i] * (4 * i + 2) % md * inv[i + 2] % md;//这是一个很坑的点i+2}
}LL C(LL n, LL m)
{//n选mreturn fac[n] * ifac[m] % md * ifac[n - m] % md;
}int main()
{cin.tie(0);cout.tie(0);cin.sync_with_stdio(false);init();cin >> T;while (T--){cin >> n; LL ans1 = ((C(2 * n, n) - f[n]) % md + md) % md;cout << ans1 << ' ' << f[n] << el;}
}