多项式ln/exp

其实这两个东西只是一个拓展,思想也是简单的思想,只不过由于$\ln$运算的乘方转乘法很好用,所以大部分套路都是先多项式$\ln$乱搞一通再多项式$\exp$回去

形式化地讲,我们就是要解决以下两个问题:
$$
\begin{aligned}
1)\quad G&= \ln F ~(\bmod~p)\\
2)\quad G&= e^{F} ~(\bmod~p)
\end{aligned}
$$

$1~\ln$

其实就是瞎jb记一下式子啦
$$
G’= F’\cdot \frac{1}{F}=\frac{F’}{F}
$$
……然后就先对F求个导+求个逆然后再不定积分回去就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int A[MAXN], B[MAXN] ;
void _Dev(int *f, int *g, int len){
int i ; g[len - 1] = 0 ;
for(i = 1 ; i < len ; ++ i) g[i - 1] = i * f[i] % P ;
}
void _Invdev(int *f, int *g, int len){
g[0] = 0 ; int i ;
for(i = 1 ; i < len ; ++ i) g[i] = f[i - 1] * expow(i, P - 2) % P ;
}
void _Ln(int *f, int *g, int len){
_Dev(f, A, len), _Inv(f, B, len) ; int i ;
int Len = 1, l = 0 ; while (Len < (len << 1)) Len <<= 1, ++ l ;
for (i = 0 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;
NTT(A, Len, 1), NTT(B, Len, 1) ; for (i = 0 ; i < Len ; ++ i) A[i] = 1ll * A[i] * B[i] % P ;
NTT(A, Len, -1), _Invdev(A, g, len) ; return ;
}

也算是小清新的多项式板子了,毕竟没有诡异的清空和鬼畜的码长。

$2~\exp$

$$
\begin{aligned}
G &= G_h - \frac{T(G_h)}{T’(G_h)}\\
\Longrightarrow G &= G_h-\frac{\ln G_h -F}{\frac{1}{G_h}}\\
\Longrightarrow G &=G_h-G_h\ln G_h+G_hF\\
\Longrightarrow G &=G_h(1-\ln G_h+F)\\
\end{aligned}
$$

然后需要的知识点就是牛顿迭代了,这玩意儿之前写过,懒得再叙述一遍了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void _Ln(int *f, int *g, int len){
int i, Len = 1, l = 0 ;
_Dev(f, A, len) ; _Inv(f, B, len) ;
while (Len < (len << 1)) Len <<= 1, ++ l ;
// for (i = 0 ; i <= Len ; ++ i) cout << A[i] << " " << B[i] << endl ;
for (i = 0 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << l - 1) ;
NTT(A, Len, 1), NTT(B, Len, 1) ; for (i = 0 ; i < Len ; ++ i) A[i] = A[i] * B[i] % P ;
NTT(A, Len, -1), _Invdev(A, g, len) ; memset(t, 0, sizeof(t)), memset(B, 0, sizeof(B)), memset(A, 0, sizeof(A)) ;
}
int C[MAXN], D[MAXN] ;
void _Exp(int *f, int *g, int len){
if(len == 1){ g[0] = 1 ; return ; }
_Exp(f, g, len + 1 >> 1) ; int Len = 1, l = 0, i ;
while (Len < (len << 1)) Len <<= 1, ++ l ;
for (i = 0 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << l - 1) ;
for (i = 0 ; i < (len << 1) ; ++ i) C[i] = D[i] = 0 ; _Ln(g, C, len) ;
for(i = 0 ; i < len ; ++ i) D[i] = f[i] ;
NTT(g, Len, 1), NTT(C, Len, 1), NTT(D, Len, 1) ;
for (i = 0 ; i < Len ; ++ i) g[i] = (1ll + D[i] - C[i] + P) * g[i] % P ;
NTT(g, Len, -1) ; for (i = len ; i <= Len ; ++ i) g[i] = 0 ;
}

比较重要的就是清空,由于$\exp$是迭代实现的,所以要进行多次$\ln$。。。