P4238-【模板】多项式乘法逆
题目:
题目描述:
给定一个多项式 $F(x)$ ，请求出一个多项式 $G(x)$， 满足 $F(x) * G(x) \equiv 1 ( \mathrm{mod:} x^n )$。系数对 $998244353$ 取模。
输入格式:
首先输入一个整数 $n$， 表示输入多项式的项数。
接着输入 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表 $F(x)$ 次数为 $i-1$ 的项的系数。
输出格式:
输出 $n$ 个数字，第 $i$ 个整数 $b_i$ 代表 $G(x)$ 次数为 $i-1$ 的项的系数。 保证有解。
样例:
样例输入 1:
样例输出 1:
1
| 1 998244347 33 998244169 1020
|
思路:
实现:
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
| #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=0;i<n;i++)yin>>a[i];
// 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;
}
|