P4725-【模板】多项式对数函数（多项式 ln）
题目:
题目描述:
给出 $n-1$ 次多项式 $A(x)$，求一个 $\bmod{:x^n}$ 下的多项式 $B(x)$，满足 $B(x) \equiv \ln A(x)$.
在 $\text{mod } 998244353$ 下进行，且 $a_i \in [0, 998244353) \cap \mathbb{Z}$
输入格式:
第一行一个整数 $n$.
下一行有 $n$ 个整数，依次表示多项式的系数 $a_0, a_1, \cdots, a_{n-1}$.
保证 $a_0 = 1$.
输出格式:
输出 $n$ 个整数，表示答案多项式中的系数 $a_0, a_1, \cdots, a_{n-1}$.
样例:
样例输入 1:
1
2
| 6
1 927384623 878326372 3882 273455637 998233543
|
样例输出 1:
1
| 0 927384623 817976920 427326948 149643566 610586717
|
思路:
实现:
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #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 d[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;
}
void dao()
{
for (int i = 1; i < lim; i++)
d[i - 1] = d[i] * i % mod;
d[n - 1] = 0;
}
void jf()
{
for (int i = lim - 1; i >= 1; i--)
d[i] = d[i - 1] * ksm(i, mod - 2) % mod;
d[0] = 0;
}
int main()
{
yin >> n;
for (int i = 0; i < n; i++)
yin >> a[i];
for (int i = 0; i < n; i++)
d[i] = a[i];
lim = 1, l = 0;
while (lim <= (n))
lim <<= 1, ++l;
dao();
calc(lim, b);
lim = 1, l = 0;
while (lim < (n << 1))
lim <<= 1, ++l;
for (int i = 0; i < lim; i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
ntt(d, g);
ntt(b, g);
for (int i = 0; i < lim; i++)
d[i] = (d[i] * b[i]) % mod;
ntt(d, gi);
long long inv = ksm(lim, mod - 2);
for (int i = 0; i < lim; i++)
d[i] = (d[i] * inv) % mod;
jf();
for (int i = 0; i < n; i++)
yout << d[i] << " ";
yout << endl;
return 0;
}
|