← 返回题目列表

AtCoder · utpc2023_c

C. 轮廓乘法

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

配点 : 100 点

問題文

长度 小于或等于 2^N 序列 使用 (A_0, A_1, \dots, A_{2^N-1}) 。最初,A_0=A_1=\dots=A_{2^N-1}=1 。

K 操作。i 次操作中,\text{popcount}(j \oplus C_i) = D_i 的每一个都 j \ (0 \leq j < 2^N) , 当我输入A_j 该值应乘以 (A_j \times X_i)\bmod M 替换为那样。

完成所有操作后的 A_0, A_1, \dots, A_{2^N-1} 各自求出。

\mathrm{popcount} 是什么? 表示

非負整数 X 反对 \text{popcount}(X) 是什么? 表示 X 该值应乘以 2 当用进制表示时 1 的个数,即 2^k 的位是 1 的非负整数 k 的号码。

位单位 \mathrm{XOR} 演算 \oplus 是什么? 表示

非負整数 A, B 按位 \mathrm{XOR}、A \oplus B 定义如下。 当

  • A \oplus B 该值应乘以 2 用进制表示时的 2^k (k \geq 0) 中的位数为A, B 该值应乘以 2 用进制表示时的 2^k 数字中只有一位是 1 如果 1,否则 输出为 0 。
例如,3 \oplus 5 = 6 为(2 以十进制表示: 011 \oplus 101 = 110)。

制約

  • 所有输入均为整数
  • 1 \leq N \leq 18
  • 2 \leq M \leq 10^9
  • 1 \leq K \leq 5 \times 10^5
  • 0 \leq C_i < 2^N
  • 0 \leq D_i \leq N
  • 2 \leq X_i \leq 10^9

入力

输入是按以下格式从标准输入给出的。

N M K
C_1 D_1 X_1
C_2 D_2 X_2
\vdots
C_K D_K X_K

出力

A_0, A_1, \dots, A_{2^N-1} 以空格分隔 在 1 行输出。


入力例 1

3 100 2
0 2 4
3 0 25

出力例 1

1 1 1 0 1 4 4 1

1 次操作中,A_3,A_5,A_6 是 在 1\times 4\bmod 100=4 。

2 次操作中,A_3 是 在 4\times 25 \bmod 100=0 。


入力例 2

4 998244353 7
0 2 4
3 0 25
9 4 37
4 1 16
6 3 8
1 4 68
13 3 97

出力例 2

1552 8 1 9700 1 64 229696 1 8 4 388 8 64 8 68 1