AT ARC191E Unfair Game

· · 题解

cnblogs。

发现操作同一个包的人一定是交错的，这说明每个包初始给每个人时，每个包的胜负关系已经确定了且相互独立。
其实这里还没有对胜负进行定义，定义一个人对于一个包赢当且仅当最后是这个人取走的包内最后一枚硬币。

于是来考虑如何求解一个包的胜负情况。

因为金币能够转化为银币，而银币不能进一步转化，于是看起来金币更为关键。

首先若金币数为 0，则能够发现银币数为奇则先手赢，否则后手赢。

此时会发现我们只关心最后银币数的奇偶，于是不妨令 x\gets x + 1, y\gets y + 1 把第一种操作转化为把一枚金币转化为 x / y 枚银币，再取走一枚银币。
这样的好处是每一步都必定会取走一枚银币，不同点只在于要不要进行一次转化操作。

那么若 x, y 奇偶相同，转化完得到的银币数的奇偶一定相同，都为 (ax + b)\bmod 2。

若 x, y 奇偶不同，会发现偶数操不操作奇偶都不改变，但是奇数操作或不操作能够把奇偶两种情况都得到。
于是可以得出，只要能给到奇数操作，那么谁为奇数谁赢。

根据上述结论进行讨论，能够发现：

根据上述讨论，发现每个包的胜负情况分为 4 种：

发现一个人拿到了非自己必胜的包，结果就是用掉这个包；如果拿到了自己必胜的包，结果就是用掉这个包并调换先后手。
于是在考虑最终的胜负情况时只需要考虑自己必胜的包的个数。

记四种情况的包数分别为 c_0, c_1, c_2, c_3。
枚举 A 拿到的先手必胜包数 i，A 拿到的 A 必胜包数 a，B 拿到的 B 必胜包数 b，有答案为 2^{c_0}\sum\limits_{i = 0}^{c_1}\sum\limits_{a = 0}^{c_2}\sum\limits_{b = 0}^{c_3} [i + a > c_1 - i + b]\binom{c_1}{i}\binom{c_2}{a}\binom{c_3}{b}。

接下来考虑化简条件 [i + a > c_1 - i + b]。

根据前面的分析，能够知道 A 必胜 B 必胜中，一定是谁为奇谁必胜，这说明 c_2, c_3 必有至少一个值为 0。

于是考虑分讨：

时间复杂度为 \mathcal{O}(n)。

#include <bits/stdc++.h>
#include <atcoder/all>

using mint = atcoder::modint998244353;

constexpr int N = 2e5;

mint fac[N + 1], ifac[N + 1];

inline mint binom(int n, int m) {
    return fac[n] * ifac[n - m] * ifac[m];
}

int cnt[4];

mint sum[N + 2];

int main() {
    fac[0] = 1;
    for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i;
    ifac[N] = fac[N].inv();
    for (int i = N; i >= 1; i--) ifac[i - 1] = ifac[i] * i;

    int n, x, y;
    scanf("%d%d%d", &n, &x, &y);
    x = (x + 1) % 2, y = (y + 1) % 2;

    for (int a, b; n--; ) {
        scanf("%d%d", &a, &b);
        b %= 2;

        if (a == 0 || x == y) {
            cnt[(a * x + b) % 2]++;
            continue;
        }

        if (a == 1 && b == 1) {
            cnt[1]++;
        } else {
            cnt[2 + y]++;
        }
    }

    mint ans = 0;
    if (cnt[2] == 0) {
        sum[0] = 1;
        for (int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + (i <= cnt[3] ? binom(cnt[3], i) : 0);
        }
        for (int i = 0; i <= cnt[1]; i++) {
            if (i * 2 - cnt[1] > 0) {
                ans += sum[i * 2 - cnt[1] - 1] * binom(cnt[1], i);
            }
        }
    } else {
        for (int i = cnt[2]; i >= 0; i--) {
            sum[i] = sum[i + 1] + binom(cnt[2], i);
        }
        for (int i = 0; i <= cnt[1]; i++) {
            ans += sum[std::max(cnt[1] - i * 2 + 1, 0)] * binom(cnt[1], i);
        }
    }

    while (cnt[0]--) ans *= 2;
    printf("%d\n", ans.val());

    return 0;
}