题解：P7431 [THUPC 2017] 小 L 的计算题 / ARIS0_0 - 5
ARIS0_0
·
·
题解
设
\begin{align*}
F(x) &= \sum_{j = 1}^{n} f_jx^j \\
&= \sum_{j = 1}^{n} \sum_{i = 1}^{n} a_i^jx^j \\
&= \sum_{i = 1}^{n} a_ix \sum_{j = 0}^{n - 1} a_i^jx_j \\
&= \sum_{i = 1}^{n} \dfrac{a_ix}{1 - a_ix} \\
&= \dfrac{\displaystyle\sum_{i = 1}^{n} a_ix\prod_{j \in [1, n] \wedge j \neq i} (1 - a_jx)}{\displaystyle\prod_{i = 1}^{n} (1 - a_ix)}
\end{align*}
设分子为 G(x)，分母为 H(x)。
考虑到
\begin{align*}
\left(\prod_{i = 1}^{n} (1 - a_ix)\right)' &= \sum_{i = 1}^{n} (1 - a_ix)'\prod_{j \in [1, n] \wedge j \neq i} (1 - a_jx) \\
&= -\sum_{i = 1}^{n} a_i\prod_{j \in [1, n] \wedge j \neq i} (1 - a_jx)
\end{align*}
则有 G(x) = H'(x)。
```cpp
#include <cstdio>
#include <vector>
#define bit_ceil(x) ((x) <= 1 ? 1 : (1 << (32 - __builtin_clz((x) - 1))))
typedef std::vector<int> poly;
namespace FastIn
{
const int S = 4e6 + 7;
char *p1, *p2, buf[S];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, S, stdin), p1 == p2) ? EOF : *p1++)
inline void read(int &x)
{
x = 0;
char c = gc();
while (c < '0' || c > '9')
c = gc();
for (; c >= '0' && c <= '9'; c = gc())
x = (x << 3) + (x << 1) + (c & 15);
}
#undef gc
}
using FastIn::read;
const int MAXN = 4e5 + 7, mod = 998244353;
inline int M(const int &x) { return x >= mod ? x - mod : x; }
inline int qpow(int a, int b)
{
int res = 1;
for (; b; a = (long long)(a) * a % mod, b >>= 1)
(b & 1) && (res = (long long)(res) * a % mod);
return res;
}
inline void NTT(poly &a, const int &rvs)
{
static std::vector<int> rev;
int n = a.size(); (int)(rev.size()) < n && (rev.resize(n), true);
for (int i = 0; i < n; ++i)
if (i < (rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (n >> 1))))
std::swap(a[i], a[rev[i]]);
for (int len = 1, W; len < n; len <<= 1)
{
W = qpow(rvs == 1 ? 3 : 332748118, (mod - 1) / (len << 1));
for (int i = 0; i < n; i += (len << 1))
for (int j = i, f0, f1, w = 1; j < i + len; ++j, w = (long long)(w) * W % mod)
f0 = a[j], f1 = (long long)(w) * a[j + len] % mod, a[j] = M(f0 + f1), a[j + len] = M(f0 + mod - f1);
}
if (rvs == -1)
for (int i = 0, invn = qpow(n, mod - 2); i < n; ++i)
a[i] = (long long)(a[i]) * invn % mod;
}
inline poly operator*(const poly &A, const poly &B)
{
int n = A.size() + B.size() - 1, len = bit_ceil(n);
poly a = A, b = B;
a.resize(len), b.resize(len), NTT(a, 1), NTT(b, 1);
for (int i = 0; i < len; ++i)
a[i] = (long long)(a[i]) * b[i] % mod;
return NTT(a, -1), a.resize(n), a;
}
inline poly operator*(poly a, const int &b)
{
for (int &i : a)
i = (long long)(i) * b % mod;
return a;
}
inline poly operator-(const poly &A, const poly &B)
{
poly a = A, b = B;
a.resize(std::max(A.size(), B.size())), b.resize(std::max(A.size(), B.size()));
for (int i = 0; i < (int)(a.size()); ++i)
a[i] = M(a[i] + mod - b[i]);
return a;
}
inline poly operator-(poly a)
{
for (int &i : a)
i = M(mod - i);
return a;
}
inline poly operator<<(const poly &a, const int &b)
{
poly res(a.size() + b);
for (int i = 0; i < (int)(a.size()); ++i)
res[i + b] = a[i];
return res;
}
inline poly dpoly(const poly &a)
{
poly b(a.size() - 1);
for (int i = 1; i < (int)(a.size()); ++i)
b[i - 1] = (long long)(a[i]) * i % mod;
return b;
}
inline poly polyinv(const poly &a, const int &n)
{
poly inv = (poly){qpow(a[0], mod - 2)};
for (int len = 1; len < n; len <<= 1)
{
poly f(a.begin(), a.begin() + std::min(len << 1, (int)(a.size()))), tmp = inv * inv * f;
inv.resize(len << 1), tmp.resize(len << 1), inv = inv * 2 - tmp;
}
return inv.resize(n), inv;
}
int T, n, ans, a[MAXN];
poly f;
poly dac(const int &l, const int &r)
{
if (l == r)
return (poly){1, M(mod - a[l])};
int mid = (l + r) >> 1;
return dac(l, mid) * dac(mid + 1, r);
}
inline void solve()
{
read(n), ans = 0;
for (int i = 1; i <= n; ++i)
read(a[i]), a[i] = M(a[i]);
f = dac(1, n), f = -(dpoly(f) << 1) * polyinv(f, n + 1);
for (int i = 1; i <= n; ++i)
ans ^= f[i];
printf("%d\n", ans);
}
int main()
{
for (read(T); T; --T)
solve();
return 0;
}
// 虚空的虚空，一切都将化为虚空，但我仍然相信在虚空的一个不起眼的角落，仍然有一朵默默无闻的蔷薇在以自己的方式盛放。
// 5
```