题目连接：
http://acm.hdu.edu.cn/showproblem.php?pid=6589
题解连接：
https://www.cnblogs.com/xusirui/p/11229450.html
https://www.cnblogs.com/FST-stay-night/p/11227505.html
NTT来自：
https://www.cnblogs.com/Sakits/p/8416918.html
题解1说，要先暴力模拟看看规律。
一个很明显的直觉是可以看看最终的序列由哪些a[i]贡献而成。但是我连暴力都不会写啊。
还不如手推：
当x为1时：
观察求前缀和的过程
0次： a[0], a[1], a[2], a[3]
1次： a[0], a[1]+a[0], a[2]+a[1]+a[0], a[3]+a[2]+a[1]+a[0]
2次： a[0], a[1]+2a[0], a[2]+2a[1]+3a[0], a[3]+2a[2]+3a[1]+4a[0]
3次： a[0], a[1]+3a[0], a[2]+3a[1]+6a[0], a[3]+3a[2]+6a[1]+10a[0]
4次： a[0], a[1]+4a[0], a[2]+4a[1]+10a[0], a[3]+4a[2]+10a[1]+20a[0]
每一项前面的系数看起来有什么规律？
0次的时候就跳过吧……
1次的时候，各个都是1？其实是 C(i,0) 。
2次的时候，是从1开始递增的。其实是 C(i+1,1) 。
3次的时候，第i项的系数看起来像 C(i+2,2) 。
4次的时候，第i项的系数看起来像 C(i+3,3) 。
所以第m次时候，系数应该是c[i]=C(m-1+i,m-1)。
m次： c[0]a[0], c[0]a[1]+c[1]a[0], c[0]a[2]+c[1]a[1]+c[2]a[0], c[0]a[3]+c[1]a[2]+c[2]a[1]+c[3]a[0]
那么其实就是数组：
a[0],a[1],a[2],a[3],a[4]...
和
c[0],c[1],c[2],c[3],c[4]...
做卷积的结果。
所以就预处理组合数一波，然后直接NTT。
然后其实x=2和x=3是对几个数组分开求这个前缀和。
标程给出一个更方便的做法。直接跳着赋值，例如在x=2的时候，赋值c'[0]=c[0],c'[1]=0,c'[2]=c[1],c'[3]=0,c'[4]=c[2],c'[5]=0
那么直接卷积就是：
m次： c[0]a[0], c[0]a[1], c[0]a[2]+c[1]a[0], c[0]a[3]+c[1]a[1], c[0]a[4]+c[1]a[2]+c[2]a[0]
从标程瞎改的快一倍的AC代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e6, mod = 998244353;
inline int pow_mod(ll x, int n) {
ll res;
for(res = 1; n; n >>= 1, x = x * x % mod)
if(n & 1)
res = res * x % mod;
return res;
}
inline int add_mod(int x, int y) {
x += y;
return x >= mod ? x - mod : x;
}
inline int sub_mod(int x, int y) {
x -= y;
return x < 0 ? x + mod : x;
}
void NTT(int a[], int n, int op) {
for(int i = 1, j = n >> 1; i < n - 1; ++i) {
if(i < j)
swap(a[i], a[j]);
int k = n >> 1;
while(k <= j) {
j -= k;
k >>= 1;
}
j += k;
}
for(int len = 2; len <= n; len <<= 1) {
int g = pow_mod(3, (mod - 1) / len);
for(int i = 0; i < n; i += len) {
int w = 1;
for(int j = i; j < i + (len >> 1); ++j) {
int u = a[j], t = 1ll * a[j + (len >> 1)] * w % mod;
a[j] = add_mod(u, t), a[j + (len >> 1)] = sub_mod(u, t);
w = 1ll * w * g % mod;
}
}
}
if(op == -1) {
reverse(a + 1, a + n);
int inv = pow_mod(n, mod - 2);
for(int i = 0; i < n; ++i)
a[i] = 1ll * a[i] * inv % mod;
}
}
int A[MAXN + 5], B[MAXN + 5];
int Asize, Bsize;
int pow2(int x) {
int res = 1;
while(res < x)
res <<= 1;
return res;
}
void convolution(int A[], int B[], int Asize, int Bsize) {
int n = pow2(Asize + Bsize - 1);
for(int i = Asize; i < n; ++i)
A[i] = 0;
for(int i = Bsize; i < n; ++i)
B[i] = 0;
NTT(A, n, 1);
NTT(B, n, 1);
for(int i = 0; i < n; ++i)
A[i] = 1ll * A[i] * B[i] % mod;
NTT(A, n, -1);
return;
}
const int MAXM = 2e6;
int fact[MAXM + 5], ifact[MAXM + 5];
int C(int n, int m) {
return m <= n ? (ll)fact[n] * ifact[m] % mod * ifact[n - m] % mod : 0;
}
void init_C() {
fact[0] = 1;
for(int i = 1; i <= MAXM; ++i)
fact[i] = 1ll * fact[i - 1] * i % mod;
ifact[MAXM] = pow_mod(fact[MAXM], mod - 2);
for(int i = MAXM - 1; i >= 0; --i)
ifact[i] = 1ll * ifact[i + 1] * (i + 1) % mod;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
init_C();
int T;
scanf("%d", &T);
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i) {
scanf("%d", &A[i]);
}
int cnt[] = {0, 0, 0, 0};
for(int i = 1; i <= m; ++i) {
int x;
scanf("%d", &x);
cnt[x]++;
}
for(int c = 1; c <= 3; ++c) {
if(cnt[c]) {
memset(B, 0, sizeof(B[0])*n);
for(int i = 0; i * c < n; ++i) {
B[i * c] = C(cnt[c] - 1 + i, i);
}
convolution(A, B, n, n);
}
}
ll ans = 0;
for(int i = 0; i < n; ++i)
ans ^= 1ll * (i + 1) * A[i];
printf("%lld\n", ans);
}
return 0;
}