5309: I love max and multiply
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：13
解决：4
题目描述
Mr.I has two sequence Ai and Bi of length n,(0≤i≤n−1).
Define an array C of length n, where Ck=max{AiBj}, satisfying (i&j≥k).
& is the button under binary Bitwise AND operation.
Please calculate the value of ∑n−1i=0Ci, modulo 998244353.
Define an array C of length n, where Ck=max{AiBj}, satisfying (i&j≥k).
& is the button under binary Bitwise AND operation.
Please calculate the value of ∑n−1i=0Ci, modulo 998244353.
输入
The first line contains an integer T . Then T test cases follow.
Each test case contains three lines.
The first one contains an integer n(1≤n≤218) — length of the array a.
The second one contains n integers A0,A1,A2,...,An−1(|Ai|≤109)
The third one contains n integers B0,B1,B2,...,Bn−1(|Bi|≤109)
∑n≤219
Each test case contains three lines.
The first one contains an integer n(1≤n≤218) — length of the array a.
The second one contains n integers A0,A1,A2,...,An−1(|Ai|≤109)
The third one contains n integers B0,B1,B2,...,Bn−1(|Bi|≤109)
∑n≤219
输出
For each test case, output a single integer ans,where ans=∑n−1i=0Ci modulo 998244353.
样例输入 复制
1
4
9 1 4 1
5 4 1 1
样例输出 复制
54