問題一覧 > 通常問題

No.1503 Bitwise And Convolution Twisted

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 28
作問者 : noshi91 / テスター : beet
お気に入りにしたユーザー ProblemId : 5711 / 自分の提出
問題文最終更新日: 2021-04-10 00:59:46
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 294 (順位表) の他の問題:

Problem Statement

You are given integer sequences $A = (A_0, A_1, \dots, A_{2^N-1}), B = (B_0, B_1, \dots, B_{2^N-1})$ of length $2^N$. Compute the sequence $C = (C_0, C_1, \dots, C_{2^N-1})$ of length $2^N$ defined by $$\begin{aligned} C_k = \left( \sum_{i=0}^{2^N-1} A_i B_{i \& k} \right) \bmod 998244353 \end{aligned}$$ Here, $\&$ denotes bitwise and.

Constraints

  • $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$)

Input

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

Output

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

Print the elements of $C$ on a single line, separated by spaces. Print a newline at the end.

Sample

Sample 1
Input
2
2 3 4 4
5 3 2 4
Output
65 51 41 43

Sample 2
Input
0
4
1
Output
4

Sample 2
Input
1
1 998244352
998244352 1
Output
0 998244351

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