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

发表于 分类于 本文字数： 1.8k 阅读时长 ≈ 7 分钟

Description

Link：HDU 7979

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

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

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

在游戏开始前，Alice 可以决定房间的访问顺序，访问顺序可以用一个排列 pp 描述，表示依次经过房间 p1,p2,⋯ ,pnp_1, p_2, \cdots, 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 博弈：对于若干堆石子 a1,a2,⋯ ,ama_1, a_2, \cdots, 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)。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#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;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/