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

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

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

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

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

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

时间复杂度：$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 + 2
    fac[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选m
    return 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72