多项式全家桶（三）：多项式的ln，exp

$\ \ \ \ \ \ \,$      对数和指数是很重要的东西了，复杂的多项式都和他们有关系，所以说掌握很重要，这里不建议光背板子，因为这两个板子都有致命的限制，而在实际操作的时候，可以通过一些方法绕过这个限制直接求解，这个就很重要了。

---

1. 多项式的$ln$ln

$\ \ \ \ \ \ \,$      P4725 【模板】多项式对数函数

$\ \ \ \ \ \ \,$      公式先走起咯：

$\ln(A)=\int \frac{A'}{A}dx$ln(A)=∫AA′​dx

$\ \ \ \ \ \ \,$      观察公式，一句话解决：

$\ \ \ \ \ \ \,$      导卷逆的积：

$\ \ \ \ \ \ \,$      看上去很模板，当然模板也是很短的：

inline Polynomial Logarithmic(const Polynomial &a){
	Polynomial ln_a=Derivation(a)*Inverse(a);
  	ln_a.resize(a.size());
  	//这里resize一下，因为卷积后会倍增，防止变长爆掉
  	return Integral(ln_a);
}

$\ \ \ \ \ \ \,$      还有一个值得注意的问题，一般求对数的多项式，是需要要求常数项为 $1$1 的，因为我们知道：

$e^0=1$e0=1

$\ \ \ \ \ \ \,$      也就是：

$ln(1)=0$ln(1)=0

$\ \ \ \ \ \ \,$      这样算出来的 $ln$ln 常数项是 $0$0，而我们追后一步在算积的时候，是默认把常数项补上 $0$0 的，这样就没有问题。可要是原多项式常数项不为 $1$1 呢？

$\ \ \ \ \ \ \,$      显然应该算积的时候在常数项补上 $ln(C)$ln(C) （C为常数项），不过这个数在模的意义下应该是多少呢？这个问题周道确实不能解决了，所以说，模板题的话，会给出这个常数项为 $1$1的条件的。

$\ \ \ \ \ \ \,$      否认常数项不等于$1$1，完全不能求 $ln$ln 的说法。

---

2. 多项式的$exp$exp

P4726 【模板】多项式指数函数

$\ \ \ \ \ \ \,$      这玩意说简单也简单，说复杂也挺复杂的，我们得引入一个新玩意，【牛顿迭代】，是求函数零点的玩意，收敛速度非常理想，我在这里有简略的讲过：【导数和牛顿迭代】，我也在洛谷出过一个牛顿迭代的裸题，感兴趣可以去体验一下牛顿迭代的神奇：【P4986 逃离】。

$\ \ \ \ \ \ \,$      说远了，现在我们来康康怎么求指数函数。

$\ \ \ \ \ \ \,$      令我们要求的是 $A$A 的指数函数 $B$B，既是：

$B=e^A$B=eA

$\ \ \ \ \ \ \,$      变形得：

$\ln(B)-A=0$ln(B)−A=0

$\ \ \ \ \ \ \,$      咦？$0$0 ?，我们把多项式当做函数值看看？

$\ \ \ \ \ \ \,$      哇，函数零点！马上牛顿迭代呀！

$\ \ \ \ \ \ \,$      设$F(B)=\ln (B)-A$F(B)=ln(B)−A，我们要求 $F$F的零点，根据牛顿迭代的公式可得（注意这里B后面的括号的迭代版本的意思，不是多项式的项）：

$B(x)=B(x-1)-\frac{F\left(B(x-1)\right)}{F'\left(B(x-1)\right)}$B(x)=B(x−1)−F′(B(x−1))F(B(x−1))​

$\ \ \ \ \ \ \,$      而根据导数的定义，$F'(B)=\frac{1}{B}$F′(B)=B1​，（【导数和牛顿迭代】里面有提到过一点，这里是把$A$A当做常数舍去了）

$\ \ \ \ \ \ \,$      那我们现在把牛顿迭代的公式化简：

$\begin{aligned} B(x)& =B(x-1)-F\left(B(x-1)\right)\times B(x-1)\\& =B(x-1)-B(x-1)\times F\left(B(x-1)\right)\\& =B(x-1)-B(x-1)\times \left(\ln \left(B(x-1)\right)-A\right)\\& =B(x-1)\times \left(1-\ln \left(B(x-1)\right)+A \right) \end{aligned}$B(x)​=B(x−1)−F(B(x−1))×B(x−1)=B(x−1)−B(x−1)×F(B(x−1))=B(x−1)−B(x−1)×(ln(B(x−1))−A)=B(x−1)×(1−ln(B(x−1))+A)​

$\ \ \ \ \ \ \,$      再次强调B后面的括号的迭代版本的意思，不是多项式的项。

$\ \ \ \ \ \ \,$      现在看似分治可做，我们用两个容器相互装版本。每次老版本一卷，新版本长度就会倍增，所以说我们做 $\log n$logn 次迭代就好。我们的操作相当于把式子拆了求收敛值，所以不会有精度的问题，求出来就好了。

$\ \ \ \ \ \ \,$      那么现在的问题是，第一个版本是怎么样，洛咕模板给的是保证 $A_0=0$A0​=0，因为$e^0=1$e0=1，也就是$exp(0)=1$exp(0)=1，所以说 $B_0=1$B0​=1，也就是常数项为 $1$1。

$\ \ \ \ \ \ \,$      当然了，同理，他一般会保证$A_0=0$A0​=0，我们不方便找到其他$exp(A_0)$exp(A0​)模的意义下的值。如果可以算的话，可以在模板里面传入 $Constant$Constant 也就是 $exp(A_0)$exp(A0​) 的值。

$\ \ \ \ \ \ \,$      否认$A_0$A0​不等于$0$0，完全不能求 $exp$exp 的说法。

inline Polynomial Exponential(const Polynomial &a,int Constant=1){
	Polynomial ret,D;int ed=a.size();
	ret.resize(1);ret[0]=Constant;
	for(int len=2;len<=ed;len<<=1){
	  	D=Logarithmic(ret);D.resize(len);
	  	D[0]=(1ll*a[0]+1ll-D[0]+mod)%mod;
	  	for(int i=1;i<len;++i) D[i]=(1ll*a[i]-D[i]+mod)%mod;
		int n=Prepare_Transformation(len<<1);
	  	ret.resize(n);D.resize(n);
	  	NTT(ret,1);NTT(D,1);
	  	for(int i=0;i<n;i++)ret[i]=1ll*ret[i]*D[i]%mod;
	  	NTT(ret,-1);
	  	for(int i=len;i<(len<<1);++i)ret[i]=D[i]=0;
	}
	ret.resize(ed);
	return ret;
}