分数: 1000 点
问题陈述
给你正整数 N, M,和 K,以及一系列 M 非负整数 A = (A_{0}, A_{1}, \dots, A_{M-1})。在这里, 2^{N - 1} \leq K < 2^{N} 成立。
在输入中, K 给出为 N- 以二进制表示的数字,而其他整数以十进制表示。
此外, A 未直接在输入中给出。相反,对于每个 i = 0, 1, \dots, M - 1,你会得到一个序列 L_i 整数 X_{i} = (X_{i,0}, X_{i,1}, \dots, X_{i,L_{i}-1}) 这样 A_{i} = \sum_{j=0}^{L_{i}-1} 2^{X_{i,j}}。在这里, 0 \leq X_{i,0} < X_{i,1} < \cdots < X_{i,L_{i}-1} < N 成立。
求逆数,模 998244353,序列 B = (B_{0}, B_{1}, \dots, B_{MK-1}) 定义如下。
- 对于任何整数 a 这样 0 \leq a < K 和任何整数 b 这样 0 \leq b < M,以下成立:
- B_{aM+b} 等于以下情况下的余数: \operatorname{popcount}(a \operatorname{AND} A_{b}) 除以 2.
什么是 \operatorname{AND}?
按位 \operatorname{AND} 整数 A 和 B,表示为 A \operatorname{AND} B,定义如下:
- 在二进制表示中 A \operatorname{AND} B,位于的数字 2^k (k \geq 0)地方是 1 当且仅当位于 2^k 放置在两者的二进制表示中 A 和 B 是 1;否则,就是 0.
例如, 3 \operatorname{AND} 5 = 1 (二进制: 011 \operatorname{AND} 101 = 001)。 一般来说,按位 \operatorname{AND} of k 整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1 \operatorname{AND} p_2) \operatorname{AND} p_3) \operatorname{AND} \dots \operatorname{AND} p_k),并且可以证明这与顺序无关 p_1, p_2, p_3, \dots, p_k.
什么是 \operatorname{popcount}?
对于非负整数 x, \operatorname{popcount}(x) 是数量 1s 的二进制表示形式 x。更准确地说,对于非负整数 x 这样 \displaystyle x = \sum_{i=0}^{\infty} b_i 2^i\ (b_i \in {0, 1}),它认为 \displaystyle \operatorname{popcount}(x) = \sum_{i=0}^{\infty} b_i。
例如, 13 is 1101 为二进制,所以 \operatorname{popcount}(13) = 3.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 2^{N-1} \leq K < 2^{N}
- 0 \leq L_{i} \leq N
- \sum L_{i} \leq 2 \times 10^5
- 0 \leq X_{i,0} < X_{i,1} < \cdots < X_{i,L_{i}-1} < N
- 所有输入值均为整数。
- K 以二进制表示法给出。
- 除 K 以十进制表示。
输入
输入由标准输入按以下格式给出:
N M
K
L_{0} X_{0,0} X_{0,1} \cdots X_{0,L_{0}-1}
L_{1} X_{1,0} X_{1,1} \cdots X_{1,L_{1}-1}
\vdots
L_{M-1} X_{M-1,0} X_{M-1,1} \cdots X_{M-1,L_{M-1}-1}
输出
打印答案。
示例输入 1
2 4 11 1 0 2 0 1 0 1 1
示例输出 1
9
A = (1, 3, 0, 2), B = (0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1).
示例输入 2
3 3 101 2 1 2 2 0 1 1 0
示例输出 2
23
A = (6, 3, 1), B = (0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0).
示例输入 3
16 7 1101010000100110 11 0 1 2 3 7 10 11 12 13 14 15 7 4 6 8 10 11 12 13 6 0 1 6 8 10 12 8 0 3 5 6 10 11 12 13 10 0 1 2 3 4 5 6 8 12 13 9 3 4 5 6 8 9 11 14 15 8 0 4 7 9 10 11 13 14
示例输出 3
97754354
示例输入 4
92 4 10101100101111111111011101111111101011001011111110011110111111101111111110100111100010111011 23 1 2 5 13 14 20 28 32 34 39 52 56 59 60 62 64 67 69 71 78 84 87 91 20 15 17 22 28 36 40 43 47 52 53 57 67 72 77 78 81 87 89 90 91 23 7 8 9 10 11 13 16 19 22 23 30 33 42 49 51 52 58 64 71 73 76 79 83 22 1 13 19 26 27 28 29 35 39 40 41 46 55 60 62 64 67 74 79 82 89 90
示例输出 4
291412708
求模数 998244353.