6057：Kanade's convolution

题目描述

Give you two arrays $A[0..2^m-1]$ and $B[0..2^m-1]$.

Please calculate array $C[0..2^m-1]$：

$$C[k]=\sum_{i~and~j=k}A[i~xor~j]*B[i~or~j]$$

You just need to print $\sum_{i=0}^{2^m-1}C[i]*1526^i ~mod~998244353$

$m<=19$

$0\leq A[i],B[i]< 998244353$

输入解释

There is only one test case.

The first line consists of one integer $m$.

The second line consists of $2^m$ integers $A[0..2^m-1]$

The third line consists of $2^m$ integers $B[0..2^m-1]$

输出解释

Output only one integer means the answer.

输入样例

输出样例

568535691

来自杭电HDUOJ的附加信息

Recommend

liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2017 Multi-University Training Contest - Team 3

源链接： HDU-6057

最后修改于 2020-10-25T23:27:56+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
10000/5000MS(Java/Others)	524288/524288K(Java/Others)