「Nowcoder Contest 295 H」Playing games

H. Playing games

题意

你有 \(n\) 堆石子,数量分别是 \(a_1,..,a_n\)

问最多能选出几堆使得玩 Nim游戏 满足后手必胜

\(n,a_i\le 5*10^5\)


做法

首先题意可以转化为选出尽量多的数使得异或和为 \(0\)

这等价于选出尽量少的数的异或和等于 \(a_1,..,a_n\) 的异或和

\(s\) 表示 \(a_1,..,a_n\) 的异或和

可以发现至多选出 \(\lceil \log_2 max\{a_i\}\rceil\) 个数可以满足要求

这非常小

于是我们枚举一个答案 \(ans\)

用一个数列记录每个值出现的次数,异或卷积 \(ans\) 次幂的第 \(s\) 位如果不为空,那么 \(ans\) 是可行的

用FWT加速这个过程,总复杂度 \(\mathcal O(n\log^2n)\)


考虑增加一个元素 \(0\) 使得答案具有可二分性

复杂度 \(\mathcal O(n\log n\log\log n)\)


事实上我们并不需要每次IFWT

令集合幂级数 \(f\) 表示集合幂级数 \(\hat f\) 的沃尔什逆变换(Inverse Walsh Transform)

\[f_S=\frac{1}{2^n}\sum_{T\subseteq 2^U}\hat f_T(-1)^{|S\cap T|}\]

这可以在 \(\mathcal O(n)\) 的时间内求出IFWT后一位的值

这样只需要在一开始做一次FWT

总复杂度 \(\mathcal O(n\log n)\)


代码

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
#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}

const int N = 1<<19, P = 998244353;
int n, sum, cnt[N], f[N], g[N];
inline void FWT(int *f){
for(int i=1; i<N; i<<=1) for(int j=0; j<N; j+=i<<1) for(int k=j; k<i+j; ++k){
int x=f[k], y=f[k+i];
f[k]=(x+y)%P, f[k+i]=(x-y)%P;
}
}
int main() {
read(n);
for(int i=1, x; i<=n; ++i) read(x), f[x]=1, sum^=x;
f[0]=1;
FWT(f);
for(int i=1; i<N; ++i) cnt[i]=cnt[i^(i&-i)]+1;
for(int i=0; i<N; ++i) g[i]=1;
for(int i=0; i<=19; ++i){
ll ans=0;
for(int j=0; j<N; ++j) ans+=(cnt[j&sum]&1?-g[j]:g[j]);
if(ans%P) return printf("%d", n-i), 0;
for(int j=0; j<N; ++j) g[j]=(ll)g[j]*f[j]%P;
}
return 0;
}
0%