← 返回题目列表

AtCoder · arc178_f

F. 长序列反转

中文机器翻译题面 查看原题

分数: 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.