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
| namespace Poly {
const int N = ::N * 4;
const int g = 3, ig = qp(g);
int len, r[N];
void Init(int n) {
int L = 0; len = 1;
while (len <= n) len <<= 1, ++L;
for (int i = 1; i < len; ++i)
r[i] = r[i >> 1] >> 1 | (i & 1) << L - 1;
}
void NTT(LL *A, int opt) {
for (int i = 0; i < len; ++i)
if (i > r[i]) std::swap(A[i], A[r[i]]);
for (int i = 1; i < len; i <<= 1) {
int wn = qp(~opt ? g : ig, (Mod - 1) / (i << 1));
for (int j = 0; j < len; j += i << 1) {
LL w = 1;
for (int k = j; k < j + i; ++k, (w *= wn) %= Mod) {
LL x = A[k], y = A[k + i] * w % Mod;
A[k] = (x + y) % Mod;
A[k + i] = (x + Mod - y) % Mod;
}
}
}
if (opt == -1) {
LL iv = qp(len);
for (int i = 0; i < len; ++i)
(A[i] *= iv) %= Mod;
}
}
void Conv(LL *A, int n, LL *B, int m, LL *C) {
Init(n + m);
for (int i = n + 1; i < len; ++i) A[i] = 0;
for (int i = m + 1; i < len; ++i) B[i] = 0;
NTT(A, 1), NTT(B, 1);
for (int i = 0; i < len; ++i) C[i] = A[i] * B[i] % Mod;
NTT(C, -1);
}
void Inv(LL *A, int n, LL *B) {
if (n == 1)
return B[0] = qp(A[0]), void();
static LL tA[N];
int m = (n + 1) / 2;
Inv(A, m, B);
Init(2 * n);
for (int i = m; i < len; ++i) B[i] = 0;
for (int i = 0; i < len; ++i) tA[i] = i < n ? A[i] : 0;
NTT(tA, 1), NTT(B, 1);
for (int i = 0; i < len; ++i)
B[i] = (2 + Mod - tA[i] * B[i] % Mod) * B[i] % Mod;
NTT(B, -1);
}
void Ln(LL *A, int n, LL *B) {
static LL tA[N], tB[N];
Inv(A, n, tA);
tB[n - 1] = 0;
for (int i = 1; i < n; ++i) tB[i - 1] = A[i] * i % Mod;
Conv(tA, n - 1, tB, n - 1, tB);
B[0] = 0;
for (int i = 1; i < n; ++i) B[i] = tB[i - 1] * qp(i) % Mod;
}
void Exp(LL *A, int n, LL *B) {
if (n == 1) return B[0] = 1, void();
static LL tA[N];
int m = (n + 1) / 2;
Exp(A, m, B);
for (int i = m; i < n; ++i) B[i] = 0;
Ln(B, n, tA);
for (int i = 0; i < n; ++i)
tA[i] = ((i == 0) + Mod - tA[i] + A[i]) % Mod;
Conv(B, n - 1, tA, n - 1, B);
}
}
|