「2025 杭电多校 1」1001. 博弈

    「2025 杭电多校 1」1001. 博弈

    HDU 7979

    Alice 和 Bob 正在玩取石子游戏。

    有 nn 个房间,第 ii 个房间中有 kik_i (ki≥1k_i \geq 1) 堆石子。Alice 和 Bob 轮流操作,Alice 先手。

    每次操作时,玩家必须在当前房间中,选择任意一个非空的堆,然后在该堆中取出任意一个石子。只有在当前房间中将所有石子取完,Alice 和 Bob 才可以到下一个房间继续进行游戏。若某位玩家无法进行操作(即到了最后一个房间并且房间为空),则该玩家输掉游戏。

    在游戏开始前,Alice 可以决定房间的访问顺序,访问顺序可以用一个排列 pp 描述,表示依次经过房间 p1,p2,…,pnp_1, p_2, \dots, p_n,只有房间 pip_i 没有石子的情况下,才可以去房间 pi+1p_{i + 1}。

    假设 Alice 和 Bob 进行的都是最优决策,Alice 想知道他有多少种排列 pp 可以获胜。答案对 109+710^9 + 7 取模。

    数据范围:1≤n≤1061 \leq n \leq 10^6,1≤∑ki≤1061 \leq \sum k_i \leq 10^6,石子数量 ∈[1,109]\in [1, 10^9]。

    时空限制:11s / 512512MiB。

    Solution

    反 NIM 博弈

    反 NIM 博弈:对于若干堆石子 a1,a2,…,ama_1, a_2, \dots, a_m,最后一个将石子取完的玩家失败。

    • 若 ∀ai=1\forall a_i = 1,则异或和 =0= 0 时先手获胜。
    • 若 ∃ai>1\exist a_i > 1,则异或和 >0> 0 时先手获胜。

    证明:∀ai=1\forall a_i = 1 的证明显然。下面证明 ∃ai>1\exist a_i > 1 的情况。

    • 情况 1:只有一堆石子数量 >1> 1。那么先手可以将该堆石子的数量控制到 00 或 11,从而转化为 ∀ai=1\forall a_i = 1 的情况,并且可以自己决定石子堆数的奇偶性。 (情况 1 下的异或和必定 >0> 0)
    • 情况 2:至少两堆石子数量 >1> 1。
      • 情况 2.1:异或和 >0> 0。此时一定可以转移到至少两堆石子数量 >1> 1 并且异或和 =0= 0 的局面(情况 2.2)。因为由 NIM 博弈可知,一定可以消成异或和 =0= 0 的局面,并且只有一堆石子数量 >1> 1 的情况异或和必定 >0> 0。
      • 情况 2.2:异或和 =0= 0。此时又有两种情况,转移到情况 2.1 或者转移到情况 1(随着游戏的进行,迟早会转移到情况 1)。

    根据我们的分析,情况 2.1 总可以情况 2.2 交给对方,情况 2.2 要么只能将情况 1 这一必胜态交给对方,要么将情况 2.1 交给对方(而对方又可以把情况 2.2 再交给自身)。于是情况 2.1 是必胜态,情况 2.2 是必败态。

    综上,若 ∃ai>1\exist a_i > 1,则异或和 >0> 0 时先手获胜。

    将石堆分成四类:

    • A:∀ai=1\forall a_i = 1,有偶数个石子。
    • B:∀ai=1\forall a_i = 1,有奇数个石子。
    • C:∃ai>1\exist a_i > 1,异或和 >0> 0。
    • D:∃ai>1\exist a_i > 1,异或和 =0= 0。

    先不考虑 A, B。对于 C 类点,由于情况 1 可以自由决定石子堆数的奇偶性,所以自己可以选择下一个房间是先手还是后手,而这先手与后手中必定有一个是胜利的,所以 C 类点是全局必胜态。同理,由于 D 类点会将情况 1 交给对方,所以 D 类点是全局必败态。所以,第一个碰到的 C 类点或 D 类点,就决定了全局的输赢。

    而在碰到 C, D 类点之前,我们会发现 A 类点完全无效,B 类点相当于是交换先后手。于是 Alice 想要获胜有两种可能:

    • 第一个 ∃ai>1\exist a_i > 1 的点是 C 类点,并且前面有偶数个 B 类点。
    • 第一个 ∃ai>1\exist a_i > 1 的点是 D 类点,并且前面有奇数个 B 类点。
    • (还有一种可能是完全没有 C, D 类点,全是 A, B 类点,注意特判)

    设 A, B, C, D 类点,各有 a,b,c,da, b, c, d 个。

    以计算第一种情况为例,先考虑放第一个 C 类点,然后再枚举前面有 ii 个 B 类点,再将剩下的 B, C, D 类点都放在第一个 C 类点之后,最后再插入所有剩下的 A 类点。则有

    c∑i=0b[i mod 2=0](bi)i!⋅(c+d−1+b−i)!⋅n!(n−a)!c \sum\limits_{i = 0}^b [i \bmod 2 = 0] \binom{b}{i} i! \cdot (c + d - 1 + b - i)! \cdot \frac{n!}{(n - a)!}

    (插入的方案数:若场上已经有 xx 个点,则有 x+1x + 1 个空隙可以插入)

    第二种情况同理。

    时间复杂度 O(n+∑ki)\mathcal{O}(n + \sum k_i)。

    一种简单粗暴的统计方法。

    以计算第一种情况为例,先考虑将第一个 C 类点固定在位置 xx,然后再枚举前面有 ii 个 B 类点,则相当于是要选 x−1−ix - 1 - i 个 A 类点和 ii 个 B 类点放到位置 xx 之前。位置 xx 之前随便排列,位置 xx 之后仍然随便排列,有

    c⋅(x−1)!⋅(n−x)!⋅(∑i=0x−1[i mod 2=0](bi)(ax−1−i))c \cdot (x - 1)! \cdot (n - x)! \cdot \left( \sum\limits_{i = 0}^{x - 1} [i \bmod 2 = 0] \binom{b}{i} \binom{a}{x - 1 - i}\right)

    括号里的部分是一个卷积式,使用任意模数 NTT 即可。

    时间复杂度 O(nlog⁡n+∑ki)\mathcal{O}(n \log n + \sum k_i)。

    #include <bits/stdc++.h>
    
    #define debug(a) std::cout << #a << "=" << (a) << ' '
    
    using s64 = long long;
    using u64 = unsigned long long;
    
    /* 取 min */
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    /* 取 max */
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    /* ----- ----- ----- 正文 ----- ----- ----- */
    
    const int mod = 1e9 + 7; // 模数需根据实际问题调整
    
    /* 模意义下 加法 */
    inline void add(int &x, const int &y) {
        x += y;
        if (x >= mod) {
            x -= mod;
        }
    }
    
    /* 模意义下 减法 */
    inline void dec(int &x, const int &y) {
        x -= y;
        if (x < 0) {
            x += mod;
        }
    }
    
    /* 模意义下 乘法 */
    inline void mul(int &x, const int &y) {
        x = 1ll * x * y % mod;
    }
    
    /* 快速幂 */
    int qpow(int a, int b, int p) {
        int ans = 1;
        for (; b; b >>= 1) {
            if (b & 1) ans = 1ll * ans * a % p;
            a = 1ll * a * a % p;
        }
        return ans;
    }
    
    int n;
    int a, b, c, d;
    
    struct BinomCoef {
        std::vector<int> fact, facv;
    
        void init(const int &n) {
            fact.resize(n + 1), facv.resize(n + 1);
            
            fact[0] = 1;
            for (int i = 1; i <= n; i ++) {
                fact[i] = 1ll * fact[i - 1] * i % mod;
            }
    
            facv[n] = qpow(fact[n], mod - 2, mod);
            for (int i = n - 1; i >= 0; i --) {
                facv[i] = 1ll * facv[i + 1] * (i + 1) % mod;
            }
        }
    
        int binom(int n, int m) {
            if (n < m || m < 0) {
                return 0;
            }
            return 1ll * facv[m] * facv[n - m] % mod * fact[n] % mod;
        }
    } bc;
    
    int calc1() {
        if (!c) return 0;
        int ans = 0;
        for (int i = 0; i <= b; i ++) {
            if (i % 2 != 0) continue;
            int cur = 1ll * bc.binom(b, i) * bc.fact[i] % mod;
            cur = 1ll * cur * bc.fact[c + d - 1 + b - i] % mod;
            add(ans, cur);
        }
        ans = 1ll * ans * c % mod;
        ans = 1ll * ans * bc.fact[n] % mod * bc.facv[n - a] % mod;
        return ans;
    }
    
    int calc2() {
        if (!d) return 0;
        int ans = 0;
        for (int i = 0; i <= b; i ++) {
            if (i % 2 != 1) continue;
            int cur = 1ll * bc.binom(b, i) * bc.fact[i] % mod;
            cur = 1ll * cur * bc.fact[c + d - 1 + b - i] % mod;
            add(ans, cur);
        }
        ans = 1ll * ans * d % mod;
        ans = 1ll * ans * bc.fact[n] % mod * bc.facv[n - a] % mod;
        return ans;
    }
    
    int calc3() {
        if (c || d) return 0;
        if (b % 2 == 0) {
            return 0;
        } else {
            return bc.fact[n];
        }
    }
    
    void work() {
        std::cin >> n;
        
        a = b = c = d = 0;
    
        for (int i = 1; i <= n; i ++) {
            int k;
            std::cin >> k;
    
            int mx = 0, xorsum = 0;
            for (int j = 1; j <= k; j ++) {
                int x;
                std::cin >> x;
    
                chmax(mx, x);
                xorsum ^= x;
            }
    
            if (mx == 1) {
                if (xorsum == 0) {
                    a ++;
                } else {
                    b ++;
                }
            } else {
                if (xorsum) {
                    c ++;
                } else {
                    d ++;
                }
            }
        }
    
        // std::cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
    
        bc.init(n);
    
        int ans = 0;
        add(ans, calc1());
        add(ans, calc2());
        add(ans, calc3());
    
        std::cout << ans << '\n';
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        int T;
        std::cin >> T;
        
        while (T --) {
            work();
        }
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/