問題一覧 > 通常問題

No.1503 Bitwise And Convolution Twisted

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 22
作問者 : noshi91noshi91 / テスター : beetbeet
4 ProblemId : 5711 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-04-10 00:59:46

問題文

長さ $2^N$ の整数列 $A = (A_0, A_1, \dots, A_{2^N-1}), B = (B_0, B_1, \dots, B_{2^N-1})$ が与えられます。 $$\begin{aligned} C_k = \left( \sum_{i=0}^{2^N-1} A_i B_{i \& k} \right) \bmod 998244353 \end{aligned}$$ により定義される長さ $2^N$ の数列 $C = (C_0, C_1, \dots, C_{2^N-1})$ を計算してください。 ただし $\&$ は bitwise and を表します。

制約

  • $0 \leqq N \leqq 20$
  • $0 \leqq A_i \lt 998244353\ \ $($0 \leqq i \lt 2^N$)
  • $0 \leqq B_i \lt 998244353\ \ $($0 \leqq i \lt 2^N$)

入力

$N$
$A_0\ \ A_1\ \ \cdots\ \ A_{2^N-1}$
$B_0\ \ B_1\ \ \cdots\ \ B_{2^N-1}$

出力

$C_0\ \ C_1\ \ \cdots\ \ C_{2^N-1}$

$C$ の各要素を一行に空白区切りで出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2
2 3 4 4
5 3 2 4
出力
65 51 41 43

サンプル2
入力
0
4
1
出力
4

サンプル2
入力
1
1 998244352
998244352 1
出力
0 998244351

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。