题解

记 $F(x)=\prod_{i=1}^n(1-a_i x)=1+c_1x+\dots+c_nx^n$。因为

$$\ln F(x)=\sum_{i=1}^n \ln(1-a_i x) = -\sum_{k\ge1}\frac{f_k}{k}x^k, $$

其中 $f_k=\sum_i a_i^k$ 就是题目要的值。于是只要计算出 $\ln F(x)$ 在 $x^1 \dots x^n$ 的系数，乘上 $-k$ 就能得到每个 $f_k$。

实现流程：

1. 分治构造 $F(x)$：把所有线性因子 $1-a_i x$ 两两卷积，利用 NTT 可以在 $\mathcal{O}(n\log n)$ 时间内完成。
2. 用常规的多项式 $\ln$ 算法（先求逆再积分）得到 $\ln F(x)$ 的前 $n$ 项。同样需要大量卷积，因此也使用 NTT 并配合分治加速。
3. 把系数乘以 $-k$（注意模数是 $998244353$），得到 $f_k$；题目只要最终异或和，所以遍历一次累积 $\oplus$ 即可。

所有多项式运算都控制在 $\mathcal{O}(n\log n)$，整体复杂度满足要求。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, mod = 998244353, G = 3;
int fst(int a, int b = mod - 2) {
    int ret = 1;
    while (b) {
        if (b & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ret;
}
const int invG = fst(G);
int T, n, a[N], tr[1 << 20];
void NTT(vector<int> &f, int op, int n) {
    for (int i = 1; i < n; i++) if (tr[i] < i) swap(f[i], f[tr[i]]);
    for (int p = 2; p <= n; p <<= 1) {
        int delt = fst(op ? G : invG, (mod - 1) / p);
        for (int i = 0; i < n; i += p) {
            int buf = 1, len = p >> 1;
            for (int j = i; j < i + len; j++) {
                int tmp = 1ll * buf * f[j + len] % mod;
                f[j + len] = (f[j] + mod - tmp) % mod;
                f[j] = (f[j] + tmp) % mod;
                buf = 1ll * buf * delt % mod;
            }
        }
    }
}
vector<int> operator * (vector<int> a, vector<int> b) {
    int ln = a.size() + b.size() - 1, n = 1;
    while (n < ln) n <<= 1;
    a.resize(n), b.resize(n);
    for (int i = 1; i < n; i++) tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
    NTT(a, 1, n), NTT(b, 1, n); 
    for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * b[i] % mod;
    NTT(a, 0, n);
    int invn = fst(n);
    for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * invn % mod;
    while ((int) a.size() > ln) a.pop_back();
    return a;
}
vector<int> calc(int l, int r) {
    if (l == r) return {1, (mod - a[l]) % mod};
    int mid = (l + r) >> 1;
    return calc(l, mid) * calc(mid + 1, r);
}
vector<int> gx, fx;
void solve(int l, int r) {
    if (l == r) {
        if (l == 0) gx[l] = fst(fx[l]);
        else gx[l] = (mod - 1ll * fst(fx[0]) * gx[l] % mod) % mod;
        return;
    }
    int mid = (l + r) >> 1;
    solve(l, mid);
    vector<int> t1, t2;
    for (int i = l; i <= mid; i++) t1.emplace_back(gx[i]);
    for (int i = 0; i <= r - l; i++) t2.emplace_back(fx[i]);
    t1 = t1 * t2;
    for (int i = mid + 1; i <= r; i++) gx[i] = (gx[i] + t1[i - l]) % mod;
    solve(mid + 1, r);
}
vector<int> ln(vector<int> f) {
    fx = f;
    gx.clear(), gx.resize(f.size() + 1);
    
    solve(0, f.size());
    vector<int> ttx = gx * f;
    for (int i = 0; i < (int) f.size() - 1; i++) 
        f[i] = 1ll * (i + 1) * f[i + 1] % mod;
    f[(int)f.size() - 1] = 0;
    
    vector<int> tmp = gx * f;
    return tmp;
}
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= mod;
    }
    vector<int> G = calc(1, n);
    G = ln(G);
    for (auto &it : G) it = (mod - it) % mod;
    int ans = 0;
    for (int i = 1; i <= n; i++) ans ^= G[i - 1];
    cout << ans << endl;
}
signed main() {    
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--) solve();
    return 0;
}