C - Contour Multiplication Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 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