Responsive image

问题 B: Kanade's convolution

问题 B: Kanade's convolution

时间限制: 10 Sec  内存限制: 256 MB
提交: 6  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

Give you two arrays A[0..2m−1] and B[0..2m−1].

Please calculate array C[0..2m−1]： 

C[k]=∑i and j=kA[i xor j]∗B[i or j]


You just need to print ∑2m−1i=0C[i]∗1526i mod 998244353

m<=19

0≤A[i],B[i]<998244353

输入描述

There is only one test case.

The first line consists of one integer m.

The second line consists of 2m integers A[0..2m−1] 

The third line consists of 2m integers B[0..2m−1]

输出描述

Output only one integer means the answer.


样例输入

2

1 2 3 4

5 6 7 8

样例输出

568535691

提示

标程中 const int N=(1<<20); 改为const int N=(1<<19); 否则运行错误

[提交][状态]
ACM算法攻关部