题意
给定一个长为 (n) 的序列 ({a_i}) 对于 (k in [1, n]) 求
[f_k = sum_{i = 1}^{n} a_i^k pmod {998244353}
]
(n le 2 imes 10^5)
题解
不会牛顿恒等式TAT，参考了这位大佬的博客。
我们令 (F(x)) 为 (f_k) 的生成函数，我们有
[egin{aligned}
F(x)
&= sum_{k} (sum_{i = 1}^{n} a_i^k) x^k\
&=sum_{i = 1}^n sum_k a_i^kx^k\
&=sum_{i = 1}^{n} frac{1}{1 - a_ix}\
end{aligned}
]
这几步都比较基础，但看起来还是挺不可做的，我们用一些神奇的操作。
[egin{aligned}
F(x)
&= sum_{i = 1}^{n} (1 + frac{a_ix}{1 - a_ix})\
&= n - x sum_{i= 1}^{n} frac{-a_i}{1 - a_ix}\
&= n - x sum_{i = 1}^{n} ln'(1 - a_ix)\
&= n - x ln'(prod_{i = 1}^n(1 - a_ix))
end{aligned}
]
我们先分治求出 (prod_{i = 1}^{n}(1 - a_ix)) 然后套 (ln) 的板子即可。(mathcal O(n log^2 n))
代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = int(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = int(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
typedef vector<int> VI;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("2409.in", "r", stdin);
freopen ("2409.out", "w", stdout);
#endif
}
const int Mod = 998244353;
inline int fpm(int x, int power) {
int res(1);
for (; power; power >>= 1, x = 1ll * x * x % Mod)
if (power & 1) res = 1ll * res * x % Mod;
return res;
}
int findlen(int l) {
int res = 1; while (res <= l) res <<= 1; return res;
}
template<int Maxn>
struct Poly {
const int g = 3, invg = fpm(g, Mod - 2);
int rev[Maxn], W[Maxn], len;
void NTT(int *P, int opt) {
Rep (i, len) if (i < rev[i]) swap(P[i], P[rev[i]]);
for (int i = 2, p; p = i >> 1, i <= len; i <<= 1) {
W[0] = 1; W[1] = fpm(~opt ? g : invg, (Mod - 1) / i);
For (k, 2, p - 1) W[k] = 1ll * W[k - 1] * W[1] % Mod;
for (int j = 0; j < len; j += i) Rep (k, p) {
int u = P[j + k], v = 1ll * P[j + k + p] * W[k] % Mod;
P[j + k] = (u + v) % Mod; P[j + k + p] = (u - v + Mod) % Mod;
}
}
if (!~opt) {
int invn = fpm(len, Mod - 2);
Rep (i, len) P[i] = 1ll * P[i] * invn % Mod;
}
}
void Prepare(int lc) {
int cnt = -1;
for (len = 1; len <= lc; len <<= 1) ++ cnt;
Rep (i, len) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << cnt);
}
int A[Maxn], B[Maxn], C[Maxn];
void Mult(int *a, int *b, int *c, int la, int lb) {
int lc = la + lb; Prepare(lc);
if (lc <= 400) {
static int tmp[410] = {0};
For (i, 0, la) if (a[i]) For (j, 0, lb)
tmp[i + j] = (tmp[i + j] + 1ll * a[i] * b[j]) % Mod;
For (i, 0, lc) c[i] = tmp[i], tmp[i] = 0; return;
}
Rep (i, len) A[i] = i <= la ? a[i] : 0; NTT(A, 1);
Rep (i, len) B[i] = i <= lb ? b[i] : 0; NTT(B, 1);
Rep (i, len) C[i] = 1ll * A[i] * B[i] % Mod; NTT(C, -1);
For (i, 0, lc) c[i] = C[i];
}
VI Mult(VI a, VI b) {
static int ta[Maxn], tb[Maxn], tc[Maxn]; VI c;
Rep (i, a.size()) ta[i] = a[i];
Rep (i, b.size()) tb[i] = b[i];
Mult(ta, tb, tc, a.size() - 1, b.size() - 1);
Rep (i, a.size() + b.size() - 1) c.push_back(tc[i]); return c;
}
void Inv(int *f, int *g, int lf) {
if (lf == 1) return void(g[0] = fpm(f[0], Mod - 2));
Inv(f, g, lf >> 1); Prepare(lf << 1);
Rep (i, len) A[i] = i < lf ? f[i] : 0; NTT(A, 1);
Rep (i, len) B[i] = i < lf ? g[i] : 0; NTT(B, 1);
Rep (i, len) C[i] = 1ll * A[i] * B[i] % Mod * B[i] % Mod; NTT(C, -1);
Rep (i, lf) g[i] = (g[i] * 2ll + Mod - C[i]) % Mod;
}
int inv[Maxn];
Poly() {
inv[1] = 1;
For (i, 2, Maxn - 1)
inv[i] = 1ll * inv[Mod % i] * (Mod - Mod / i) % Mod;
}
void Der(int *f, int *g, int lf) {
For (i, 1, lf) g[i - 1] = 1ll * i * f[i] % Mod; g[lf] = 0;
}
void Int(int *f, int *g, int lf) {
g[0] = 0;
For (i, 1, lf + 1)
g[i] = 1ll * f[i - 1] * inv[i] % Mod;
}
void Ln(int *f, int *g, int lf) {
static int der[Maxn], tmp[Maxn];
Der(f, der, lf); Inv(f, tmp, lf);
Mult(der, tmp, tmp, lf, lf); Int(tmp, g, lf);
}
};
const int N = 1 << 20;
Poly<N> T;
int n, a[N], f[N], g[N], ans[N];
VI Solve(int l, int r) {
if (l == r) return {1, Mod - a[l]};
int mid = (l + r) >> 1;
return T.Mult(Solve(l, mid), Solve(mid + 1, r));
}
int main () {
File();
int cases = read();
while (cases --) {
For (i, 1, n = read()) a[i] = read() % Mod;
VI res = Solve(1, n);
For (i, 0, n) f[i] = res[i];
T.Ln(f, g, findlen(n)); T.Der(g, f, n);
ans[0] = n; For (i, 1, n) ans[i] = Mod - f[i - 1];
int Ans = 0;
For (i, 1, n) Ans ^= ans[i];
printf ("%d
", Ans);
}
return 0;
}