3847: Sequence
内存限制:256 MB
时间限制:3.000 S
评测方式:文本比较
命题人:
提交:3
解决:1
题目描述
Tom gets an integer sequence a indexed from 1 with length n from Jerry and he wants to apply k kinds of operations to this sequence.
For a type k operation, he calculates bi=∑_(j=i−k⋅x)a_j(0≤x,1≤j≤i) for every i ranged from 1 to n and then replaces each ai with bi mod 998244353.
He wonders what the final sequence looks like after m operations.
For a type k operation, he calculates bi=∑_(j=i−k⋅x)a_j(0≤x,1≤j≤i) for every i ranged from 1 to n and then replaces each ai with bi mod 998244353.
He wonders what the final sequence looks like after m operations.
输入
The first line contains an integer T(T≤10), denoting the number of testcases.
For each test case, the first line contains two integers n and m(1≤n≤10^5,1≤m≤10^6), representing the length of sequence a and the number of operations.
The following line contains n integers denoting the sequence a(1≤ai≤10^9).
The last line contains m integers representing the sequence of operations. Let ci be the ith number in this sequence, it means the type of ith operation is ci(1≤ci≤3).
It is guaranteed that ∑n≤2.1×10^5,∑m≤2.1×10^6.
For each test case, the first line contains two integers n and m(1≤n≤10^5,1≤m≤10^6), representing the length of sequence a and the number of operations.
The following line contains n integers denoting the sequence a(1≤ai≤10^9).
The last line contains m integers representing the sequence of operations. Let ci be the ith number in this sequence, it means the type of ith operation is ci(1≤ci≤3).
It is guaranteed that ∑n≤2.1×10^5,∑m≤2.1×10^6.
输出
For each test case, output one line containing an integer ans.
ans=(1⋅a1)⊕(2⋅a2)⊕...⊕(n⋅an), ai is the ith element of sequence a after m operations, ⊕ means bitwise exclusive OR operation.
ans=(1⋅a1)⊕(2⋅a2)⊕...⊕(n⋅an), ai is the ith element of sequence a after m operations, ⊕ means bitwise exclusive OR operation.
样例输入 复制
2
5 2
2 4 2 1 1
1 1
5 2
3 2 2 4 1
2 2
样例输出 复制
233
121