题解：P17856 [LBA-OI R6 D] 奶龙游戏

· · 题解

闲话

做完题没事干，写一篇题解吧。

概率题，数据量这么大大概率不是 DP，是一个公式题。

感觉这种使用卡特兰数思想的计数问题特别少，这题差不多蓝题水平。

Solution

总方案数 \binom{2n}{n}，计完数一除就好。

考虑怎么计数恰好 k 个的，由于 Alice 后手，只要她有能力赢 k 次，她就能做到赢 k 次。

通过观察，我们可以发现 n-bob \le k \le alice，其中 bob 表示 Bob 最多赢多少局，其中 alice 表示 Alice 最多赢多少局。

下文记 a_i 为 Alice 的数组，b_i 为 Bob 的数组。

继续观察：我们发现 j 取决于 a_i > b_j 的 (i,j) 对数且任意两个对 (i_1,j_1)，(i_2,j_2) 都满足 i_1 \neq i_2 且 j_1 \neq j_2。

考虑这样的一个对满足什么性质，不妨从小到大考虑[1,2n] 的所有数：

如果前面有一个数分给 Bob 了，且这个数分给了 Alice，对数 +1。

如果前面有一个数分给 Alice 了，且这个数分给了 Bob，对数 +1。

由于前面的 Alice 贡献一定会有 Bob 结算，因此，我们可以在一但有一个数就对数 +1，反之对数 -1，对数的最大值与最小值大小就是 bob 和 alice 的最大值大小。

所以我们的任务：

构造一个长度为 2 \times n 的数组 s，s_i \in \left\{ 0,1 \right\}，使得其任意前缀在 [-k,n-k] 之间，\mathcal{O}(1) 查询。

这是一个特别经典的问题，就像卡特兰数（任意前缀都在 [0,+\infty] 之间）。

记 +1 是往上走一个，-1 是往右走一个， 问题等价于从 (0,0) 走到 (n,n) 且路径不超过 y=x+k+1 与 y=x-k-1 的方案数。

做对称点然后相减即可。

答案就是：

\frac{\binom{2n}{n}-\binom{2n}{n+k+1}-\binom{2n}{k-1}}{\binom{2n}{n}}

::::success[代码]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
const int N = 2e6+5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n;
int frc[N * 2], infrc[N * 2];
int ksm(int a, int b) {
    a %= mod;
    int res = 1;
    while (b) {
        if (b & 1) res = (res * a) % mod;
        b >>= 1;
        a = (a*a) % mod;
    }
    return res;
}
int C(int n, int m) {
    if (n < 0 || n < m || m < 0) return 0;
    return frc[n] % mod*infrc[m] % mod*infrc[n - m] % mod;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    frc[0] = 1;
    rep(i, 1, 2 * n) frc[i] = (frc[i - 1] * i) % mod;
    infrc[2 * n] = ksm(frc[2 * n], mod - 2);
    per(i, 2 * n - 1, 0) infrc[i] = (infrc[i + 1] * (i + 1)) % mod;
    int tot = C(2 * n, n);
    int inv = ksm(tot, mod - 2);
    rep(k, 0, n) {
        int ans = tot;
        ans -= C(2 * n, n + k + 1) + C(2 * n, k - 1);
        ans = (ans % mod + mod) % mod;
        ans = ans % mod*inv % mod;
        cout << ans << '\n';
    }
    return 0;
}

::::