一个长度为nn的序列aia_i(ai[0,2m)a_i \in [0, 2^m))

定义一个子序列的权值为子序列所有数的异或和的二进制表示中1的个数

对于所有i[0,m]i \in [0, m],求所有2n2^n个子序列中权值为ii的子序列的个数

答案对998244353998244353取模

n2×105,m35n \le 2 \times 10^5, m \le 35

CF 1336E1

Solution

首先考虑缩小规模,有一个经典的结论:

  • 如果有nn个数,其线性基内元素可以异或出kk,则异或和为kk的方案数等于2nx2^{n - x},其中xx为线性基大小。证明显然

建出线性基,把问题缩小到O(2m)O(2 ^ m)的规模。题目转化为,对每个ii用一个线性基异或出popcount=ipopcount = i的方案数

考虑meet in middle,令k=m/2k = m / 2,把线性基拆成AA集合(最高位>k> k)和BB集合(最高位k\le k

对于BB集合,直接dfs出数组G[j]G[j]表示异或出来的数为jj的方案数

对于AA集合,还要再加一维表示>2k> 2^k部分的popcountpopcount。即F[i][j]F[i][j]表示第k+1k + 1位至mm位的popcount=ipopcount = i,异或出来的数的前kk位的值为jj的方案数

考虑合并,对于每个F[i]F[i]把它与GG异或卷积卷一下(设结果数组为HH),用H[j]H[j]ans[i+popcount(j)]ans[i + popcount(j)]贡献答案即可

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 2e5;
const int MAXM = 35;
const int MAXL = (MAXM + 1) / 2;
const int MAXS = 1 << MAXL;
const int MOD = 998244353;

inline void ADD (int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % MOD) if (i & 1) ans = (LL) ans * a % MOD;
return ans;
}

int N, M, B;
int L, ALL;
LL A[MAXM + 5];
int pcnt[MAXS + 5];

inline void Init ()
{
L = M / 2, ALL = (1 << L) - 1;
for (int i = 0; i <= MAXS; ++i) pcnt[i] = __builtin_popcount (i);
}

inline void insert (LL x)
{
for (int i = MAXM; i >= 0; --i) if (x >> i & 1)
{
if (!A[i])
{
for (int j = i - 1; j >= 0; --j) if (x >> j & 1) x ^= A[j];
for (int j = i + 1; j <= MAXM; ++j) if (A[j] >> i & 1) A[j] ^= x;
A[i] = x;
++B;
return ;
}
x ^= A[i];
}
}

int F[MAXL + 5][MAXS + 5], G[MAXS + 5];

inline void dfs1 (int x, LL s)
{
if (x == L) { ++G[s]; return ; }
dfs1 (x + 1, s);
if (A[x]) dfs1 (x + 1, s ^ A[x]);
}

inline void dfs2 (int x, LL s)
{
if (x == M) { ++F[pcnt[s >> L]][s & ALL]; return; }
dfs2 (x + 1, s);
if (A[x]) dfs2 (x + 1, s ^ A[x]);
}

inline void FWT (int *A, int n, int fg)
{
for (int mid = 1; mid < n; mid <<= 1)
for (int i = 0; i < n; i += mid << 1)
for (int j = i; j < i + mid; ++j)
{
int x = A[j], y = A[j + mid];
A[j] = (x + y) % MOD;
A[j + mid] = (x - y + MOD) % MOD;
if (fg)
{
A[j] = (LL) A[j] * (MOD + 1) / 2 % MOD;
A[j + mid] = (LL) A[j + mid] * (MOD + 1) / 2 % MOD;
}
}
}

int Ans[MAXM + 5];

inline void Solve ()
{
Init ();

dfs1 (0, 0), dfs2 (L, 0);

FWT (G, 1 << L, 0);
for (int i = 0; i <= M - L; ++i)
{
FWT (F[i], 1 << L, 0);
for (int j = 0; j < 1 << L; ++j) F[i][j] = (LL) F[i][j] * G[j] % MOD;
FWT (F[i], 1 << L, 1);

for (int j = 0; j < 1 << L; ++j) ADD (Ans[i + pcnt[j]], F[i][j]);
}

for (int i = 0; i <= M; ++i) printf("%lld ", (LL) Ans[i] * Pow (2, N - B) % MOD);
}

inline void Input ()
{
N = read<int>(), M = read<int>();
for (int i = 1; i <= N; ++i)
{
LL x = read<LL>();
insert (x);
}
}

int main ()
{

#ifdef hk_cnyali
freopen("E1.in", "r", stdin);
freopen("E1.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}