No.1503 Bitwise And Convolution Twisted
問題文最終更新日: 2021-04-10 00:59:46
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
noshi91
beet