AT_arc151_d [ARC151D] Binary Representations and Queries

[problemUrl]: https://atcoder.jp/contests/arc151/tasks/arc151_d 長さ $ 2^N $ の整数列 $ A\ =\ (A_0,\ A_1,\ \ldots,\ A_{2^N-1}) $ が与えられます。 また、$ Q $ 個のクエリが与えられます。 $ i\ =\ 1,\ 2,\ \ldots,\ Q $ について、$ i $ 番目のクエリでは $ 2 $ つの整数 $ X_i,\ Y_i $ が与えられ、下記の操作を行います。 > $ j\ =\ 0,\ 1,\ 2,\ \ldots,\ 2^N-1 $ の順に下記の手順を行う。 > > 1. まず、$ j $ の $ N $ 桁の $ 2 $ 進数表現を $ b_{N-1}b_{N-2}\ldots\ b_0 $ とおく。また、$ b_{N-1}b_{N-2}\ldots\ b_0 $ から $ b_{X_i} $ を反転（ $ 0 $ ならば $ 1 $ に、$ 1 $ ならば $ 0 $ に変更）させて得られる $ 2 $ 進数表現によって表される整数を $ j' $ とおく。 > 2. そして、$ b_{X_i}\ =\ Y_i $ ならば、$ A_{j'} $ に $ A_j $ の値を加算する。 すべてのクエリを入力で与えられる順番に実行した後の $ A $ の各要素を $ 998244353 $ で割ったあまりを出力してください。 $ N $ 桁の $ 2 $ 進数表現とは？非負整数 $ X $ ($ 0\ \leq\ X\ )\ の\ N $ 桁の $ 2 $ 進数表現とは、$ 0 $ と $ 1 $ のみからなり下記の条件を満たす唯一の、長さ $ N $ の列 $ b_{N-1}b_{N-2}\ldots\ b_0 $です。 - $ \sum_{i\ =\ 0}^{N-1}\ b_i\ \cdot\ 2^i\ =\ X $

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_0 $ $ A_1 $ $ \ldots $ $ A_{2^N-1} $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_Q $ $ Y_Q $

$ i\ =\ 0,\ 1,\ \ldots,\ 2^N-1 $ について、すべてのクエリを実行した後の $ A_i $ を $ 998244353 $ で割ったあまり $ A'_i $ を、下記の形式にしたがって空白区切りで出力せよ。 > $ A'_0 $ $ A'_1 $ $ \ldots $ $ A'_{2^N-1} $

### 制約 - $ 1\ \leq\ N\ \leq\ 18 $ - $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ A_i\ \lt\ 998244353 $ - $ 0\ \leq\ X_i\ \leq\ N-1 $ - $ Y_i\ \in\ \lbrace\ 0,\ 1\rbrace $ - 入力はすべて整数 ### Sample Explanation 1 $ 1 $ 番目のクエリに対する操作は次の通りです。 - $ j\ =\ 0 $ のとき、$ b_1b_0\ =\ 00,\ j'\ =\ 2 $ です。$ b_1\ \neq\ 1 $ であるので、加算の手順は行いません。 - $ j\ =\ 1 $ のとき、$ b_1b_0\ =\ 01,\ j'\ =\ 3 $ です。$ b_1\ \neq\ 1 $ であるので、加算の手順は行いません。 - $ j\ =\ 2 $ のとき、$ b_1b_0\ =\ 10,\ j'\ =\ 0 $ です。$ b_1\ =\ 1 $ であるので、$ A_0 $ に $ A_2 $ の値を加算します。その結果、$ A\ =\ (2,\ 1,\ 2,\ 3) $ となります。 - $ j\ =\ 3 $ のとき、$ b_1b_0\ =\ 11,\ j'\ =\ 1 $ です。$ b_1\ =\ 1 $ であるので、$ A_1 $ に $ A_3 $ の値を加算します。その結果、$ A\ =\ (2,\ 4,\ 2,\ 3) $ となります。 $ 2 $ 番目のクエリに対する操作は次の通りです。 - $ j\ =\ 0 $ のとき、$ b_1b_0\ =\ 00,\ j'\ =\ 1 $ です。$ b_0\ =\ 0 $ であるので、$ A_1 $ に $ A_0 $ の値を加算します。その結果、$ A\ =\ (2,\ 6,\ 2,\ 3) $ となります。 - $ j\ =\ 1 $ のとき、$ b_1b_0\ =\ 01,\ j'\ =\ 0 $ です。$ b_0\ \neq\ 0 $ であるので、加算の手順は行いません。 - $ j\ =\ 2 $ のとき、$ b_1b_0\ =\ 10,\ j'\ =\ 3 $ です。$ b_0\ =\ 0 $ であるので、$ A_3 $ に $ A_2 $ の値を加算します。その結果、$ A\ =\ (2,\ 6,\ 2,\ 5) $ となります。 - $ j\ =\ 3 $ のとき、$ b_1b_0\ =\ 11,\ j'\ =\ 2 $ です。$ b_0\ \neq\ 0 $ であるので、加算の手順は行いません。 以上より、すべてのクエリを実行した後の $ A $ は $ (2,\ 6,\ 2,\ 5) $ です。