模板 多项式求逆

传送门

题目大意

给定一个多项式$F(x)$,请求出一个多项式$G(x)$,满足$F(x)\times G(x) \equiv 1 (\bmod x^n)$。系数对$998244353$取模。

解析

转载自huhaoo的博客

国际惯例,先把多项式长度弄成$2^k$。

如果我们求出了:
$$
f’^{-1}f\equiv 1(\bmod x^\frac k2)
$$
那么可以得到:
$$
\begin{align*}
f^{-1}f&\equiv1(\bmod x^\frac k2)\\
f(f^{-1}-f’^{-1})&\equiv0(\bmod x^\frac k2)\\
(f^{-1}-f’^{-1})^2&\equiv0(\bmod x^k)\\
f^{-2}-2f^{-1}f’^{-1}-f’^{-2}&\equiv0(\bmod x^k)\\
f^{-1}-2f’{-1}-ff’^{-2}&\equiv0(\bmod x^k)\\
f^{-1}&\equiv f’^{-1}(2-ff’^{-1})(\bmod x^k)
\end{align*}
$$

边界给整数求逆即可。

Code

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
#define DREP(i, s, e) for(int i = s; i >= e ;i--)
#define REP(i, s, e) for(int i = s; i <= e ;i++)

#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)

#include <iostream>
#include <cstdio>

using namespace std;
const int maxn = 1e5 + 10, maxlen = 1 << 18, MOD = 998244353;

template <typename T> inline T read()
{
T ans(0), p(1);
char c = getchar();
while (!isdigit(c))
{
if (c == '-') p = -1;
c = getchar();
}
while (isdigit(c))
{
ans = ans * 10 + c - 48;
c = getchar();
}
return ans * p;
}

int power_pow(int base, int b)
{
int ans(1);
while (b)
{
if (b&1) ans = 1ll * ans * base % MOD;
base = 1ll * base * base % MOD;
b >>= 1;
}
return ans;
}
#define inv(x) power_pow(x, MOD - 2)

int n, f[maxlen], R[maxlen], len;

void NTT(int a[], int flag)
{
REP(i, 1, len-1) if (i < R[i]) swap(a[i], a[R[i]]);
for (int i = 1; i < len; i <<= 1)
{
int wn = power_pow(3, (MOD - 1) / (i << 1));
if (flag < 0) wn = inv(wn);
for (int k = 0; k < len; k += i << 1)
{
int w = 1;
for (int l = 0; l < i;l++, w = 1ll * w * wn % MOD)
{
int x(a[k + l]), y(1ll * w * a[k + l + i] % MOD);
a[k + l] = (x + y) % MOD;
a[k + l + i] = (x - y) % MOD;
}
}
}
if (flag < 0)
{
int invN = inv(len);
REP(i, 0, len - 1) a[i] = 1ll * a[i] * invN % MOD;
}
}

int Inv[maxlen], temp[maxlen];
void solve(int lim, int a[], int b[])
{
if (!lim) return b[0] = inv(a[0]), void();
solve(lim >> 1, a, b);
len = lim + lim;
REP(i, 1, len - 1) R[i] = (R[i >> 1] >> 1) | (i & 1 ? lim : 0);
copy(a, a + lim, temp);
NTT(temp, 1);NTT(b, 1);
REP(i, 0, len - 1) b[i] = 1ll * (2ll - 1ll * temp[i] * b[i] % MOD) % MOD * b[i] % MOD;
NTT(b, -1);
REP(i, lim, len - 1) b[i] = 0;
}

int main()
{
#ifdef CraZYali
freopen("4238.in", "r", stdin);
freopen("4238.out", "w", stdout);
#endif
cin >> n;
REP(i, 0, n - 1) f[i] = read<int>();
solve(1 << 17, f, Inv);
REP(i, 0, n - 1) printf("%d%c", (Inv[i] + MOD) % MOD, i == n - 1 ? '\n' : ' ');
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×