多项式求逆

给定$F(x)$,求$G(x)$满足$G(x)\cdot F(x) \equiv1~(\bmod x^n)$.

不妨考虑$G’(x)\cdot F(x) =1~(\bmod x^{\frac{n}{2}})$

则有如下:
$$
\because G’\cdot F =1~(\bmod x^{\frac{n}{2}})\\ ~G\cdot F \equiv1~(\bmod x^{\frac{n}{2}})\\
\therefore G’ -G\equiv0~(\bmod x^{\frac{n}{2}})\\
\Longrightarrow G’^2+G^2-2G’G\equiv0~(\bmod x^{n})
$$

两端同时卷上一个$F(x)$则有:

$$
\because F\cdot G\equiv1~(\bmod x^n)\\
\therefore G\equiv 2G’-FG’^2~(\bmod x^n)
$$

以此为递推式即可递推出$G(x)$的值,时间复杂度$O(n\log^2 n)$.

$1~$

【模板】多项式求逆

就是板子,NTT一下就好= =

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
#include <cstdio>
#include <iostream>
#include <algorithm>

#define rr register
#define MAXN 300023
#define Mod 998244353

const int G = 3 ;
using namespace std ; int t[MAXN] ;
int N, base[MAXN], Ans[MAXN], rev[MAXN] ;

inline int expow(int x, int y){
int res = 1 ;
while (y)
res = ((y & 1) ? 1ll * res * x % Mod : res),
x = 1ll * x * x % Mod, y >>= 1 ;
return res % Mod ;
}
void NTT(int *J, int L, int flag){
rr int Gn, Gi = 1 ;
for (rr int i = 0 ; i < L ; ++ i)
if (i < rev[i]) J[i] ^= J[rev[i]] ^= J[i] ^= J[rev[i]] ;
for (rr int i = 1 ; i < L ; i <<= 1){
Gn = expow(G, (Mod - 1) / (i << 1)) ;
for (rr int j = 0 ; j < L ; Gi = 1, j += (i << 1)){
for (rr int k = 0 ; k < i ; ++ k, Gi = 1ll * Gi * Gn % Mod){
rr int real = J[j + k], iroot = 1ll * J[j + k + i] * Gi % Mod ;
J[j + k] = (real + iroot) % Mod, J[j + k + i] = (real - iroot + Mod) % Mod ;
}
}
}
if (flag > 0) return ;
int Inv = expow(L, Mod - 2) ; reverse(J + 1, J + L) ;
for (rr int i = 0 ; i < L ; ++ i) J[i] = 1ll * J[i] * Inv % Mod ;
}
void Inv_NTT(int Len, int *A, int *B){//递推
if (Len <= 1){ B[0] = expow(A[0], Mod - 2) ; return ; }
Inv_NTT((Len + 1) >> 1, A, B) ; rr int Lim = 1, len = 0 ;
while (Lim < (Len << 1)) Lim <<= 1, ++ len ; rr int i, j, k ;
for (i = 0 ; i < Lim ; ++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len-1)) ;
for (i = 0 ; i < Len ; ++ i) t[i] = A[i] ;
NTT(t, Lim, 1), NTT(B, Lim, 1) ; for (i = 0 ; i < Lim ; ++ i) B[i] = 1ll * (2ll - 1ll * t[i] * B[i] % Mod + Mod) % Mod * B[i] % Mod ;
NTT(B, Lim, -1) ; for (i = Len ; i <= Lim ; ++ i) B[i] = 0 ;
}
int main(){
cin >> N ; int i ;
for (i = 0 ; i < N ; ++ i) scanf("%d", &base[i]) ;
Inv_NTT(N, base, Ans) ; for (i = 0 ; i < N ; ++ i) printf("%d ", Ans[i]) ;
}

$2$

【模板】多项式求逆(加强版)

然而就是把模数换成了非NTT模数= =

于是就做一遍MTT就好了,这里写的是带有共轭优化的版本= =

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
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>

#define rr register
#define MAXN 300020
#define MAXM MAXN
#define Mod (1000000007)

const double Pi = acos(-1) ;
const int G = 3 ; int T[MAXN] ;
using namespace std ; int t[MAXN] ;
int N, base[MAXN], Ans[MAXN], rev[MAXN] ;

inline int expow(int x, int y){
int res = 1 ;
while (y)
res = ((y & 1) ? 1ll * res * x % Mod : res),
x = 1ll * x * x % Mod, y >>= 1 ;
return res ;
}
struct node{
long double r, i ;
}A[MAXM], B[MAXM], w[MAXM], t1[MAXM], t2[MAXM], qaq ; int L1, L2, P ;
inline node operator + (const node &J, const node & Q){ return (node){J.r + Q.r , J.i + Q.i} ; }
inline node operator - (const node &J, const node & Q){ return (node){J.r - Q.r , J.i - Q.i} ; }
inline node operator * (const node &J, const node & Q){ return (node){J.r * Q.r - J.i * Q.i , J.r * Q.i + J.i * Q.r} ; }

inline void FFT(node *J, const int &Lim, int flag){
for (rr int i = 0; i < Lim; i ++)
if(i < rev[i]) qaq = J[i], J[i] = J[rev[i]], J[rev[i]] = qaq ;
for (rr int j = 1; j < Lim; j <<= 1)
for(rr int k = 0; k < Lim ; k += (j << 1))
for(rr int l = 0 ; l < j ; ++ l){
rr node T = w[Lim / j * l] ; if (flag < 0) T.i *= -1 ;
rr node Nx = J[k + l], Ny = T * J[k + j + l] ; J[k + l] = Nx + Ny, J[k + j + l] = Nx - Ny ;
}
}
void MTT(int *J, int *K, int Length, int P, int Lim, int *ret){
rr node ia, ib, a1, a2, b1, b2 ; rr int t, k, q1, q2, q3 ;
for (rr int i = 0 ; i < (Length << 1) ; ++ i) A[i] = B[i] = (node){0, 0} ;
for (rr int i = 1 ; i < Lim ; i <<= 1) for(k = 0 ; k < i ; ++ k) w[Lim / i * k] = (node){cos(k * Pi / i) , sin(k * Pi / i)} ;
for (rr int i = 0 ; i <= Length ; ++ i) A[i].r = J[i] & 32767, A[i].i = J[i] >> 15, B[i].r = K[i] & 32767, B[i].i = K[i] >> 15 ;
FFT(A, Lim, 1), FFT(B, Lim, 1), t = Lim - 1 ;
for (rr int i = 0 ; i < Lim ; ++ i){
k = (Lim - i) & t ;
ia = (node){ A[k].r, -A[k].i }, ib = (node){ B[k].r, -B[k].i } ;
a1 = (ia + A[i]) * (node) {0.5, 0}, a2 = (A[i] - ia) * (node) {0, -0.5} ;
b1 = (ib + B[i]) * (node) {0.5, 0}, b2 = (B[i] - ib) * (node) {0, -0.5} ;
t1[i] = a1 * b1 + (a1 * b2 + b1 * a2) * (node){0, 1}, t2[i] = a2 * b2 ;
}
FFT(t1, Lim, -1), FFT(t2, Lim, -1) ;
for (rr int i = 0 ; i < Length ; ++ i){
q1 = (long long)(t1[i].r / Lim + 0.5) % P, q2 = (long long)(t1[i].i / Lim + 0.5) % P ;
q3 = (long long)(t2[i].r / Lim + 0.5) % P, ret[i] = ((1ll * q3 << 30) % P + (1ll * q2 << 15) % P + q1) % P ;
}
}
void Inv_MTT(int Len, int *A, int *B){
if (Len <= 1){
B[0] = expow(A[0], Mod - 2) ;
return ;
}
Inv_MTT(Len >> 1, A, B) ; rr int Lim, len = 0 ;
for (Lim = 1 ; Lim <= Len ; Lim <<= 1) ++ len ;
for (rr int i = 0 ; i < Lim ; ++ i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len-1)) ;
MTT(A, B, Len, Mod, Lim, T), MTT(T, B, Len, Mod, Lim, t) ;
for (rr int i = 0 ; i < Len ; ++ i) B[i] = 1ll * (2ll * B[i] - t[i] + Mod) % Mod ;
}
inline int qr(){
rr int k = 0 ; char c = getchar() ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) k = (k << 1) + (k << 3) + c - 48 ,c = getchar() ;
return k ;
}
int main(){
cin >> N ; rr int i, Np ;
for (Np = 1 ; Np < N ; Np <<= 1) ;
for (i = 0 ; i < N ; ++ i) base[i] = qr() ;
Inv_MTT(Np, base, Ans) ; for (i = 0 ; i < N ; ++ i) printf("%d ", Ans[i]) ;
}

开了一发O2发现快了三倍,woc…