#P9077. 「HNOI2021 省集 Day1」异或

    ID: 5161 传统题 3000ms 512MiB 尝试: 3 已通过: 1 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS线性基阈值划分大小情况FWT全子集枚举位计数对称性分析计数 DP补集计数卷积转化CDQ 分治NTT

「HNOI2021 省集 Day1」异或

题目描述

给定两个大小分别为 nn 和 mm 的集合 SS 和集合 TT,集合 SS 中的第 ii 个元素为 sis_i(编号从 11 到 nn),集合 TT 中的第 ii 个元素为 tit_i(编号从 11 到 mm)。保证集合 SS 内的元素互不相同、保证集合 TT 内的元素互不相同。

你需要求有多少个长度为 LL 的序列 aa(下标从 11 到 LL)满足:

  • ∀i∈[1,L],ai∈S\forall i\in[1,L],a_i\in S。
  • 令 di=a1⊕a2⊕a3…⊕aid_i=a_1\oplus a_2\oplus a_3\ldots \oplus a_i,那么 ∀i∈[1,L],di∉T\forall i\in[1,L],d_i\not\in T。其中 ⊕\oplus 代表按位异或运算。

输出方案数对 998244353998244353 取模的结果。

输入格式

第一行三个正整数 n,m,Ln, m, L 分别表示集合 SS 和 TT 的大小,和一个正整数 LL。

第二行 nn 个非负整数依次表示集合 SS 中的元素,保证元素互不相同。

第三行 mm 个非负整数依次表示集合 TT 中的元素,保证元素互不相同。

输出格式

输出一行一个非负整数,表示答案对 998244353998244353 取模的结果。

样例

样例 1

4 4 4
3 4 5 6
0 3 1 2
3

样例 2

6 6 7
4 10 6 8 2 30
2 11 12 8 22 24
13118

样例 3

见下发文件中的 randomxor/randomxor3.in 与 randomxor/randomxor3.ans。

样例 4

见下发文件中的 randomxor/randomxor4.in 与 randomxor/randomxor4.ans。

数据范围

对于所有测试点:n≤35,m≤20,L≤4000,si,ti≤109n \le 35, m \le 20, L \le 4000, s_i, t_i \le 10^9。

测试点编号 nn mm LL 特殊性质
1∼21\sim 2 ≤16\le 16 ≤10\le 10 ≤50\le 50 保证 si,ti≤105s_i,t_i\le 10^5
3∼53\sim 5 无
6∼86\sim 8 ≤30\le 30 ≤20\le 20
9∼109\sim 10 ≤200\le 200
11∼1311\sim 13 ≤35\le 35 ≤500\le 500
14∼1814\sim 18 ≤2000\le 2000
19∼2019\sim 20 ≤5000\le 5000