[POI2016]Nim z utrudnieniem

Description

A 和 B 两个人玩游戏,一共有 $m$ 颗石子,A 把它们分成了 $n$ 堆,每堆石子数分别为 $a _{1, 2, \dots, n}$,每轮可以选择一堆石子,取掉任意颗石子,但不能不取。谁先不能操作,谁就输了。

在游戏开始前,B 可以扔掉若干堆石子,但是必须保证扔掉的堆数是 $d$ 的倍数,且不能扔掉所有石子。A 先手,请问 B 有多少种扔的方式,使得 B 能够获胜。

$$
1 \le n \le 5 \times 10 ^5, 1 \le m \le 10 ^6, 1 \le d \le 10 \\
\texttt{Memory Limit = 64MB}
$$

Solution

考虑朴素 DP: 设 $f(i, j, k)$ 表仅考虑前 $i$ 堆石子,当前已经扔掉的堆数模 $d$ 为 $j$,且扔掉的石子异或和(注意这里和网上题解的状态定义有所区别)为 $k$ 的方案数。

考虑第 $i$ 堆选与不选,有转移:

$$
f(i, j, k) = f(i - 1, j - 1, k \oplus a _i) + f(i - 1, j, k)
$$

复杂度 $O(nmd)$ 起飞了,考虑怎么优化。

异或运算有一个性质:一个数 $x$ 无论与比他小的数怎么异或,得到结果都小于 $2x$。利用二进制很容易得到。

所以先将石子堆按颗数排序,那么对于第 $i$ 堆石子而言,$k \ge 2 a _i$ 的状态必然毫无意义。于是只要将 $k$ 枚举到 $2 a _i - 1$ 即可,时间复杂度降为 $O(md)$。

再考虑空间限制。首先第一维可以滚动数组,但是还是超过了 64MB 的限制。

实际上,开滚动数组只是为了避免新状态转移到新状态。仔细考虑上述转移式,易得应当将 $j$ 从大到小,即从 $d - 1$ 到 1 枚举,这样可避免重复问题。为何省去了 0?因为 0 从 $d - 1$ 转移而来,所以开一个临时数组,转移之前先记下 $d - 1$ 这一维的情况,转移完 $d - 1 \to 1$ 之后再对 0 进行转移,可以省去滚动数组的空间。

由于题目要求不能全部扔掉,所以特判 $d | n$ 的情况,令答案减一即可。

时空复杂度 $O(md)$。

Code

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
/**********************************************************
* Author : EndSaH
* Email : hjxhb1@gmail.com
* Created Time : 2019-09-22 15:26
* FileName : wib.cpp
* Website : https://endsah.cf
* *******************************************************/

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The message in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define __bufsize (1 << 21 | 1)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[50];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__________;

inline int read()
{
register int x = 0, flag = 1;
register char ch;
while (!isdigit(ch = getchar()))
if (ch == '-')
flag = -1;
while (x = x * 10 + (ch & 15), isdigit(ch = getchar()));
return x * flag;
}

template <typename _INT>
inline void write(_INT x)
{
if (x < 0)
putchar('-'), x = -x;
while (*++stkpos = x % 10 ^ 48, x /= 10, x);
while (stkpos != _stk)
putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

const int maxN = 5e5 + 5;
const int maxM = 1 << 20;
const int mod = 1e9 + 7;

int n, d, sum;
int a[maxN];
int f[10][maxM], tmp[maxM];

inline void Mod(int& x)
{ x >= mod ? x -= mod : 0; }

int main()
{
#ifndef ONLINE_JUDGE
freopen("wib.in", "r", stdin);
freopen("wib.out", "w", stdout);
#endif
n = read(), d = read();
for (int i = 1; i <= n; ++i)
sum ^= (a[i] = read());
std::sort(a + 1, a + n + 1);
f[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
memcpy(tmp, f[d - 1], std::min((a[i] * 2 + 1), maxM) * sizeof(int));
for (int j = d - 1; j; --j)
for (int k = 0; k < std::min(a[i] * 2, maxM); ++k)
Mod(f[j][k] += f[j - 1][k ^ a[i]]);
for (int k = 0; k < std::min(a[i] * 2, maxM); ++k)
Mod(f[0][k] += tmp[k ^ a[i]]);
}
int ans = f[0][sum];
if (n % d == 0)
--ans;
printf("%d\n", (ans + mod) % mod);
return 0;
}