Skip to content

S2OJ - 1153. 字符串

题解约 1.3 千字
# 动态规划 # S2OJ # 数学 # 组合数学 # 2018 # 计数
检测到 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 个整数 x1∼xnx_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,xi≤5n, x_i \leq 5；
  • 对于 50%50\% 的数据，n≤20n \leq 20；
  • 对于另外 10%10\% 的数据，a=ba = b；
  • 对于另外 20%20\% 的数据，a=1a = 1；
  • 对于 100%100\% 的数据，1≤n≤1051 \leq n \leq 10^5，1≤a,b,xi≤1091 \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;
}