Skip to content

S2OJ - 1153. 字符串

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

nn 堆石子,第 ii 堆有 xix_i 个。

Alice 和 Bob 轮流取石子(先后手未定),Alice 每次从一堆中取走 aa 个,Bob 每次从一堆中取走 bb 个,无法操作者输。

不难发现只会有四种情况:Alice 必胜、Bob 必胜、先手必胜、后手必胜。

你需要选定若干堆石子(共有 2n2^n 种方案),Alice 和 Bob 只能在你选出的堆中取,问以上四种情况对应的方案数。对 109+710^9 + 7 取模。

#输入格式

第一行三个整数 n,a,bn, a, b,第二行 nn 个整数 x1xnx_1 \sim x_n

#输出格式

一行四个整数,分别表示 Alice 必胜、Bob 必胜、先手必胜和后手必胜的方案数,对 109+710^9 + 7 取模。

#输入输出样例

样例输入 #1

2 2 3
2 3

样例输出 #1

2 0 1 1

样例解释 #1

选定空集时后手必胜,选定 {2}\{2\} 时 Alice 必胜,选定 {3}\{3\} 时先手必胜,选定 {2,3}\{2, 3\} 时 Alice 必胜。

#数据范围与约定

  • 对于 10%10\% 的数据,n,xi5n, x_i \leq 5
  • 对于 50%50\% 的数据,n20n \leq 20
  • 对于另外 10%10\% 的数据,a=ba = b
  • 对于另外 20%20\% 的数据,a=1a = 1
  • 对于 100%100\% 的数据,1n1051 \leq n \leq 10^51a,b,xi1091 \leq a, b, x_i \leq 10^9

#思路

先令每次取的石子较少的一方为 Alice,另一方为 Bob。

显然 xix_i 中只有 xi mod (a+b)x_i \bmod (a + b) 能对答案产生贡献,将其记为 rir_i

每堆石子可以分为以下几种情况:

  1. ri[0,a)r_i \in [0, a):这堆石子谁也取不到。
  2. ri[a,b)r_i \in [a, b):只要存在这种情况则 Alice 必胜,因为取到最后的时候 Alice 能多取一次而 Bob 不能。
  3. ri[b,2a)r_i \in [b, 2a):这种情况下,取走本堆的那个人能多走一步,相当于改变先后手顺序。
  4. ri[2a,a+b)r_i \in [2a, a + b):这种情况下,Alice 能多走至少 2 步,Bob 能多走至少 1 步。
    1. 如果 Alice 先手,则 Alice 必胜(先从该堆中取走一次后相当于多了一个情况 2);
    2. 如果 Bob 先手,则相当于多出了一个情况 3;
    3. 如果这个情况出现了两次,则 Alice 不论先手后手都必胜。

对于情况 1,在计算最终答案时乘上 2cnt12^{cnt_1} 即可。

计算先手必胜的方案数:

2cnt1×(i mod 2=1(cnt3i)+i mod 2=0(cnt3i)cnt4)2^{cnt_1} \times \left( \sum_{i \bmod 2 = 1} \binom{cnt_3}{i} + \sum_{i \bmod 2 = 0} \binom{cnt_3}{i} cnt_4 \right)

计算后手必胜的方案数:

2cnt1×(i mod 2=0(cnt3i))2^{cnt_1} \times \left( \sum_{i \bmod 2 = 0} \binom{cnt_3}{i} \right)

#代码

C++
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
#include <iostream>
#include <algorithm>
#include <functional>
#include <iterator>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int n, a, b, winner,
cnt_le_a, cnt_le_b, cnt_le_2a, cnt_rest,
ans_winner, ans_first, ans_second;
int fac[N], inv[N], fac_inv[N];
std::vector<int> v;

enum Winner {
Alice = 0,
Bob = 1,
};

int C(int n, int m) {
if (n < m || n < 0 || m < 0) return 0;
return static_cast<long long>(fac[n]) * fac_inv[m] % mod * fac_inv[n - m] % mod;
}

constexpr int binpow(int a, int b, int mod = ::mod) {
int res = 1;
a %= mod;

while (b) {
if (b & 1) res = static_cast<long long>(res) * a % mod;
a = static_cast<long long>(a) * a % mod;
b >>= 1;
}

return res;
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

fac[0] = 1;
for (int i = 1; i < N; i++) {
fac[i] = static_cast<long long>(fac[i - 1]) * i % mod;
}

inv[0] = inv[1] = 1;
for (int i = 2; i < N; i++) {
inv[i] = static_cast<long long>(mod - (mod / i)) * inv[mod % i] % mod;
}

fac_inv[0] = fac_inv[1] = 1;
for (int i = 2; i < N; i++) {
fac_inv[i] = static_cast<long long>(fac_inv[i - 1]) * inv[i] % mod;
}

cin >> n >> a >> b;

if (a < b) {
winner = Winner::Alice;
} else {
std::swap(a, b);
winner = Winner::Bob;
}

std::copy_n(std::istream_iterator<int>(cin), n, std::back_inserter(v));
std::transform(v.begin(), v.end(), v.begin(), std::bind(std::modulus<int>(), std::placeholders::_1, a + b));
std::for_each(v.begin(), v.end(), [&](int x) {
if (x < a) cnt_le_a++; // [1, a)
else if (x < b) cnt_le_b++; // [a, b)
else if (x < 2 * a) cnt_le_2a++; // [b, 2a)
else cnt_rest++; // [2a, a + b)
});

for (int i = 0; i <= cnt_le_2a; i++) {
if (i % 2 == 0) {
ans_first = (static_cast<long long>(ans_first) + static_cast<long long>(C(cnt_le_2a, i)) * cnt_rest % mod) % mod;
ans_second = (static_cast<long long>(ans_second) + C(cnt_le_2a, i)) % mod;
} else { // i % 2 == 1
ans_first = (static_cast<long long>(ans_first) + C(cnt_le_2a, i)) % mod;
}
}

ans_first = static_cast<long long>(ans_first) * binpow(2, cnt_le_a) % mod;
ans_second = static_cast<long long>(ans_second) * binpow(2, cnt_le_a) % mod;
ans_winner = ((static_cast<long long>(binpow(2, n)) - ans_first - ans_second) % mod + mod) % mod;

if (winner == Winner::Alice) {
cout << ans_winner << ' ' << 0 << ' ' << ans_first << ' ' << ans_second << endl;
} else {
cout << 0 << ' ' << ans_winner << ' ' << ans_first << ' ' << ans_second << endl;
}

return 0;
}