C - Contour Multiplication
解説
/
実行時間制限: 3 sec / メモリ制限: 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 である。
制約
- 入力は全て整数
- 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