1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
using namespace std;
typedef long long ll;
const int mod = 998244353;
inline int add(const int &x, const int &y) { return x + y < mod ? x + y : x + y - mod; }
inline int sub(const int &x, const int &y) { return x - y < 0 ? x - y + mod : x - y; }
inline int mul(const int &x, const int &y) { return (int)((ll)x * y % mod); }
inline int ksm(int x, int y = mod - 2) {
int w = 1; for(; y; y >>= 1, x = mul(x, x)) if(y & 1) w = mul(w, x); return w;
}
namespace Poly {
inline int Get(int x) { int w = 1; for(; w <= x; w <<= 1); return w; }
void ntt(vector<int> &A, int lmt, int opt) {
A.resize(lmt + 5);
for(int i = 0, j = 0; i < lmt; i++) {
if(i > j) swap(A[i], A[j]);
for(int k = lmt >> 1; (j ^= k) < k; k >>= 1);
}
vector<int> w(lmt >> 1);
for(int mid = 1; mid < lmt; mid <<= 1) {
w[0] = 1;
int w0 = ksm(opt == 1 ? 3 : (mod + 1) / 3, (mod - 1) / mid / 2);
for(int i = 1; i < mid; i++) w[i] = mul(w[i - 1], w0);
for(int R = mid << 1, j = 0; j < lmt; j += R)
for(int k = 0; k < mid; k++) {
int x = A[j + k], y = mul(w[k], A[j + mid + k]);
A[j + k] = add(x, y), A[j + mid + k] = sub(x, y);
}
}
if(opt == -1)
for(int mu = ksm(lmt), i = 0; i < lmt; i++) A[i] = mul(A[i], mu);
}
vector<int> Mul(const vector<int> &a, const vector<int> &b) {
vector<int> A = a, B = b; int lmt = Get(a.size() + b.size() - 2);
ntt(A, lmt, 1), ntt(B, lmt, 1);
for(int i = 0; i < lmt; i++) A[i] = mul(A[i], B[i]);
ntt(A, lmt, -1); return A.resize(a.size() + b.size() - 1), A;
}
vector<int> Inv(const vector<int> &a, int sz = -1) {
if(sz == -1) sz = a.size();
vector<int> res; if(sz == 1) return res.pb(ksm(a[0])), res;
res = Inv(a, (sz + 1) / 2);
vector<int> tmp(a.begin(), a.begin() + sz);
int lmt = Get(sz * 2 - 2);
ntt(tmp, lmt, 1), ntt(res, lmt, 1);
for(int i = 0; i < lmt; i++) res[i] = mul(sub(2, mul(res[i], tmp[i])), res[i]);
ntt(res, lmt, -1); return res.resize(sz), res;
}
vector<int> Ln(const vector<int> &a) {
vector<int> f, g = Inv(a); f.resize(a.size());
for(int i = 1; i < f.size(); i++) f[i - 1] = mul(i, a[i]);
f[f.size() - 1] = 0, f = Mul(f, g), f.resize(a.size());
for(int i = f.size() - 1; i > 0; i--) f[i] = mul(f[i - 1], ksm(i));
f[0] = 0; return f;
}
}
const int N = 200010;
int T, n, a[N], ans;
vector<int> f, g;
vector<int> solve(int l, int r) {
vector<int> res; if(l >= r) return res.pb(1), res.pb(sub(0, a[l])), res;
int mid = (l + r) >> 1; return Poly::Mul(solve(l, mid), solve(mid + 1, r));
}
int main() {
for(scanf("%d", &T); T; --T) {
scanf("%d", &n); rep(i, 1, n) scanf("%d", &a[i]), a[i] %= mod;
f = Poly::Ln(solve(1, n));
for(int i = 1, ed = f.size(); i < ed; i++) f[i - 1] = mul(i, f[i]);
per(i, n, 1) f[i] = f[i - 1];
rep(i, 0, n) f[i] = sub(0, f[i]);
f[0] = add(f[0], n), ans = 0;
rep(i, 1, n) ans ^= f[i]; printf("%d\n", ans);
}
return 0;
}
|