「THUPC 2017」小 L 的计算题

发表于
https://loj.ac/problem/2409

题目链接

「THUPC 2017」小 L 的计算题」PATH

做法

$$
f(k) = \sum_k (\sum_{i = 1}^{n} a_i^k) x^k\\
= \sum_k \sum_{i = 1}^{n} (a_ix)^k\\
= \sum_{i = 1}^{n} \sum_k (a_ix)^k\\
= \sum_{i = 1}^{n} \frac{1}{1 - a_ix}\\
= \sum_{i = 1}^{n} (1 - \frac{-a_ix}{1-a_ix})\\
= n - \sum_{i = 1}^{n} \frac{-a_ix}{1-a_ix}\\
= n - x \sum_{i = 1}^{n} \ln’(1 - a_ix)\\
= n - x \ln’(\prod_{i = 1}^{n} (1 - a_ix))
$$

分治FFT + 多项式求 Ln 即可。 

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;
}