#P7457. [2017年杭电多校]Kanade's convolution

    ID: 7470 传统题 1000ms 256MiB 尝试: 5 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-FWT按子集大小分层卷积转化位计数乘法原理

[2017年杭电多校]Kanade's convolution

Kanade's convolution

Problem Description

Give you two arrays A[0..2m−1]A[0..2^m-1] and B[0..2m−1]B[0..2^m-1]. Please calculate array C[0..2m−1]C[0..2^m-1]£º

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

You just need to print ∑i=02m−1C[i]∗1526i mod 998244353\sum_{i=0}^{2^m-1}C[i]*1526^i ~mod~998244353 m<=19m<=19 0≤A[i],B[i]<9982443530\leq A[i],B[i]< 998244353

Input

There is only one test case. The first line consists of one integer mm. The second line consists of 2m2^m integers A[0..2m−1]A[0..2^m-1] The third line consists of 2m2^m integers B[0..2m−1]B[0..2^m-1]

Output

Output only one integer means the answer.

Sample Input

2
1 2 3 4
5 6 7 8

Sample Output

568535691

Source

2017 Multi-University Training Contest - Team 3

https://acm.hdu.edu.cn/showproblem.php?pid=6057