P4721-【模板】分治 FFT
题目:
题目描述:
给定序列 $g_{1\dots n - 1}$，求序列 $f_{0\dots n - 1}$。
其中 $f_i=\sum_{j=1}^if_{i-j}g_j$，边界为 $f_0=1$。
答案对 $998244353$ 取模。
输入格式:
第一行一个整数 $n$ 。
第二行 $n-1$ 个整数 $g_{1\dots n - 1}$。
输出格式:
一行 $n$ 个整数，表示 $f_{0\dots n - 1}$ 对 $998244353$ 取模后的值。
样例:
样例输入 1:
样例输出 1:
样例输入 2:
1
2
| 10
2 456 32 13524543 998244352 0 1231 634544 51
|
样例输出 2:
1
| 1 2 460 1864 13738095 55389979 617768468 234028967 673827961 708520894
|
思路:
实现:
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
82
83
84
85
86
87
| #include "ybwhead/ios.h"
int n, lim, l;
const int maxn = 1e6 + 10;
long long a[maxn], b[maxn];
int r[maxn];
const int mod = 998244353;
long long c[maxn];
long long ksm(long long a, int n)
{
long long ans = 1;
while (n)
{
if (n & 1)
ans = ans * a % mod;
a = a * a % mod;
n >>= 1;
}
return ans;
}
const int g = 3, gi = 332748118;
void ntt(long long a[], long long x)
{
for (int i = 0; i < lim; i++)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int o = 2, k = 1; o <= lim; o <<= 1, k <<= 1)
{
long long wn = ksm(x, (mod - 1) / (o));
for (int i = 0; i < lim; i += o)
{
long long w = 1;
for (int j = 0; j < k; j++, w = w * wn % mod)
{
long long x = a[i + j], y = a[i + j + k] * w % mod;
a[j + i] = (x + y) % mod;
a[j + k + i] = (x - y + mod) % mod;
}
}
}
}
void calc(int n, long long b[])
{
if (n == 1)
{
b[0] = ksm(a[0], mod - 2);
// yout<<a[0]
return;
}
calc((n + 1) >> 1, b);
lim = 1;
l = 0;
while (lim < (n << 1))
lim <<= 1, ++l;
// yout<<lim<<" "<<a[1]<<endl;
for (int i = 0; i < lim; i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
for (int i = 0; i < n; i++)
c[i] = a[i];
for (int i = n; i < lim; i++)
c[i] = 0;
ntt(c, g);
ntt(b, g);
for (int i = 0; i < lim; i++)
{
b[i] = (2 - c[i] * b[i] % mod + mod) % mod * b[i] % mod;
// yout<<b[i]<<endl;
}
ntt(b, gi);
long long inv = ksm(lim, mod - 2);
for (int i = 0; i < n; i++)
b[i] = (b[i] * inv) % mod;
for (int i = n; i < lim; i++)
b[i] = 0;
}
int main()
{
yin >> n;
for (int i = 1; i < n; i++)
yin >> a[i], a[i] = mod - a[i];
a[0] = 1;
// while (lim<n)lim<<=1, l++;
calc(n, b);
for (int i = 0; i < n; i++)
yout << (b[i] + mod) % mod << " ";
yout << endl;
return 0;
}
|