【题解】HackerRank-Stone Game

Posted on In Disqus:

题目

https://www.hackerrank.com/challenges/stonegame/problem

题意

给 \(n\) 个数，可以选择至多 \(n - 1\) 个数减少，问有多少中方案可以使操作后的 \(n\) 个数异或和为零。

题解

  • 令不考虑 \(n-1\) 的限制的答案为 \(f(a_1, a_2, \dots,a_n)\)，那么考虑限制后的答案为 \[ f(a_1, a_2, \dots, a_n) - f(a_1 - 1, a_2 - 1, \dots, a_n - 1) \]

  • 设所有数字的最高位为 \(m\)，且最高位 \(m\) 的数有 \(c\) 个。\(g\) 的含义就是让偶数个最高位为 \(m\) 的最高位取 1，并且至少剩下一个最高位为 \(m\) 的最高位取 0，而且那个数的低位为其他数的异或和（也就是这个数的低位不能自由选取，而用于抵消其他数的影响）。 \[ h(a_1,a_2,\dots,a_n)= \prod_{i=1}^n \begin{cases} a_i+1 & (a_i<m) \\ (a_i-m+1)x+m &(a_i\geqslant m) \\ \end{cases} =\sum_{i=0}^{k}b_ix_i \\ g(a_1, a_2, \dots, a_n)=\frac{\sum_{i(2i\neq c)} b_{2i}}{m} \]

  • 如果要全选偶数个最高位为 m 的数，那么就转化为不考虑 m 这一位的情况了。 \[ f(a_1, a_2,\dots,a_n)=g(a_1,a_2,\dots,a_n) + [c\text{ is even}] \cdot f(a_i \& \sim m) \\ f(0, 0, \dots ,0) = 1 \]

代码

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 100 + 5;
const LL MOD = 1E9 + 7;
int a[N], b[N];
int n;

LL pown(LL a, LL x) {
    LL ret = 1;
    for (; x; x >>= 1, a = a * a % MOD)
        if (x & 1) ret = ret * a % MOD;
    return ret;
}

LL go(int a[]) {
    int t = *max_element(a, a + n);
    if (t == 0) return 1;
    t = 1 << (31 - __builtin_clz(t));
    LL c0 = 1, c1 = 0, all = 1, even = true;
    FOR (i, 0, n) {
        if (a[i] & t) {
            even ^= 1;
            LL cc0 = (c0 * t + c1 * (a[i] - t + 1)) % MOD;
            LL cc1 = (c1 * t + c0 * (a[i] - t + 1)) % MOD;
            c0 = cc0; c1 = cc1;
            all = all * (a[i] - t + 1) % MOD;
        } else {
            c0 = c0 * (a[i] + 1) % MOD;
            c1 = c1 * (a[i] + 1) % MOD;
            all = all * (a[i] + 1) % MOD;
        }
    }
    if (even) c0 -= all;
    LL ans = c0 * pown(t, MOD - 2) % MOD;
    if (even) {
        FOR (i, 0, n) a[i] &= ~t;
        ans += go(a);
    }
    return (ans + 2 * MOD) % MOD;
}


LL solve() {
    FOR (i, 0, n) b[i] = a[i] - 1;
    return (go(a) - go(b) + MOD) % MOD;
}

int main() {
    cin >> n;
    FOR (i, 0, n) scanf("%d", &a[i]);
    cout << solve() << endl;
}