AT_utpc2023_c.Contour Multiplication

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

有一个长度为 $2^N$ 的数列 $(A_0, A_1, \dots, A_{2^N-1})$ ，初始时 $A_0=A_1=\dots=A_{2^N-1}=1$ 。

有 $K$ 次操作。第 $i$ 次操作，会令所有满足 $\mathrm{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)$ 表示非负整数 $X$ 的二进制表示中 $1$ 的个数。

位运算 $\mathrm{XOR}$ （ $\oplus$ ）对非负整数 $A, B$ 的定义为：将 $A$ 和 $B$ 的二进制表示对应位进行异或操作，得到的第 $2^k$ 位为 $A$ 和 $B$ 的该位若只有一个为 $1$ 则为 $1$ ，否则为 $0$ 。

例如： $3 \oplus 5 = 6$ ，因二进制 $011 \oplus 101 = 110$ 。

输入按以下格式从标准输入给出：

$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}$ 以空格分隔，输出在一行中。

输入#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

第 $1$ 次操作， $A_3, A_5, A_6$ 都会变为 $1\times 4\bmod 100=4$ 。

第 $2$ 次操作， $A_3$ 会被变为 $4\times 25 \bmod 100=0$ 。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?