#P17276. [2024年南开中学集训]异或

[2024年南开中学集训]异或

问题描述

给定 n,kn,k 和长度为 nn 的整数序列 aa,满足 aa 的值域为 [0,B)[0,B)。

对于 ∀ 0≤x<B\forall\,0\le x<B,求解有多少个 kk 元组 1≤i1<i2<i3<⋯<ik≤n1\le i_1<i_2<i_3<\cdots<i_k\le n 满足

ai1⊕ai2⊕⋯⊕aik=xa_{i_1}\oplus a_{i_2}\oplus\cdots\oplus a_{i_k}=x,

其中 ⊕\oplus 表示异或操作,答案对 998244353998244353 取模。

输入格式

输入第 11 行,包含 33 个正整数,分别表示 n,k,Bn,k,B。

输入第 22 行,包含 nn 个整数,第 ii 个整数表示 aia_i。

输出格式

输出共 11 行,包含 BB 个整数,第 ii 个整数表示 x=i−1x=i-1 时的答案,答案对 998244353998244353 取模。

样例输入

4 2 4
0 1 2 3

样例输出

0 2 2 2

数据范围

对于所有测试数据,1≤n≤1051\le n\le10^5,1≤B≤655361\le B\le65536,1≤k≤163841\le k\le16384,且满足 1≤k≤n1\le k\le n。

测试点编号 n≤n\le k≤k\le B=B=
1 10310^3 128128
2 10510^5 2020 1638416384
3
4 10310^3
5
6
7 1638416384
8
9 6553665536
10