多项式ln,exp学习小计

主要作为一个模板和总结

多项式ln

• 求$G(x)=ln(F(x))$G(x)=ln(F(x))
• 两边求导
• $G'(x)=\frac{F'(x)}{F(x)}$G′(x)=F(x)F′(x)​，注意这是复合函数求导。
• 多项式求逆，求导，乘法即可求出$G'(x)$G′(x)
• 再积分回去就是$G(x)$G(x)
• 一般会钦定常数项为1，否则ln的时候先求导再积分（这里是不定积分）你会发现常数项丢失了，得到的结果并不是原来的多项式，而是在每一项的基础上除以了常数项。

多项式exp

牛顿迭代

• 用于求函数的零点，在某些情况下可以应用，但是在一些奇怪的情况下永远逼近不了解。
• 做法：随便选择一个起点$x_0$x0​，作$f(x)$f(x)在$x_0$x0​上的切线，交$x$x轴与$x_1$x1​，$x_1$x1​相比$x_0$x0​比零点更近，不断迭代即可求得一个逼近零点的点。
• 作切线根据导数的知识可以知道：
  $f'(x_0)(x_0-x_1)=f(x_0)$f′(x0​)(x0​−x1​)=f(x0​)
  $x_1=x_0-\frac{f(x_0)}{f'(x_0)}$x1​=x0​−f′(x0​)f(x0​)​

从实数到多项式的伟大扩展

• 相当于求$G(F(x))=0\ (mod\ x^n)$G(F(x))=0 (mod xn)
• 考虑倍增（实际上就是一个精度不断提升的过程）。
  $G(F_0(x))=0\ (mod\ x^{n/2})$G(F0​(x))=0 (mod xn/2)
• 根据泰勒展开，在$F_0(x)$F0​(x)求得：
  $G(F(x))=G(F_0(x))+\frac{G'(F_0(x))}{1!}(F(x)-F_0(x))+\frac{G''(F_0(x))}{1!}(F(x)-F_0(x))^2+...$G(F(x))=G(F0​(x))+1!G′(F0​(x))​(F(x)−F0​(x))+1!G′′(F0​(x))​(F(x)−F0​(x))2+...
• 因为$F(x)$F(x)和$F(x_0)$F(x0​)是在$mod\ x^{n/2}$mod xn/2下的，所以平方之后在$mod\ x^n$mod xn下就为0了，所以只有前两项有意义。
• 实际这就是泰勒展开的式子，每一次的精度翻倍。
  $G(F(x))=G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))$G(F(x))=G(F0​(x))+G′(F0​(x))(F(x)−F0​(x))

利用牛顿迭代

• 要求$B(x)=e^{A(x)}$B(x)=eA(x)
• $ln\ B(x)=A(x)$ln B(x)=A(x)
• $F(B(x))=ln\ B(x)-A(x)=0$F(B(x))=ln B(x)−A(x)=0
• 求零点$B(x)$B(x)，$A(x)$A(x)视作常数。
• 所以$F'(B(x))=\frac{1}{B(x)}$F′(B(x))=B(x)1​
• 假设已经求出了$B_0(x)$B0​(x)为$x^{n/2}$xn/2下的零点，则：
• $B(x)=B_0(x)-\frac{F(B_0(x))}{F'(B_0(x))}$B(x)=B0​(x)−F′(B0​(x))F(B0​(x))​
• $B(x)=B_0(x)(1-ln\ B_0(x)+A(x))(mod\ x^n)$B(x)=B0​(x)(1−ln B0​(x)+A(x))(mod xn)
• 倍增，利用多项式ln和多项式乘法即可。

关于值域的选择

• 求$lim$lim下ln的时候是2个$lim$lim下的多项式的乘法，记得开两倍长度去乘。
• 求exp时也要注意是当前长度的两倍。实际上迭代次数越多就越准确，没有规定的次数，在一定次数之后再进行迭代在有限位置的系数就不会改变了，乘上的ln的值域也没有限定的要求，但是总的长度一定要开到有值的位置最大长度的和。
• 无关的位置要清空。

多项式快速幂

• ln再乘指数再exp回去。注意ln之后常数项的贡献被除掉了，这个部分要单独再快速幂。

JZOJ6712

• 多项式ln，exp，求逆，快速幂模板

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 524288
#define ll long long 
#define mo 998244353
using namespace std;

ll n,m,T,S,a[maxn],b[maxn],c[maxn];
ll w[maxn+5],inv[maxn+5];
int bt[maxn];

ll ksm(ll x,ll y){
	ll s=1;
	for(;y;y/=2,x=x*x%mo) if (y&1)
		s=s*x%mo;
	return s;
}

void clear(ll *a,int n){memset(a,0,sizeof(ll)*n);}

void prepare(){
	inv[0]=inv[1]=1;
	for(int i=2;i<=maxn;i++) inv[i]=(mo-mo/i)*inv[mo%i]%mo;
	w[0]=1,w[1]=ksm(3,(mo-1)/maxn);
	for(int i=2;i<=maxn;i++) 
		w[i]=w[i-1]*w[1]%mo;
}

void getbt(int n){for(int i=1;i<n;i++)bt[i]=(bt[i>>1]>>1)|((i&1)?n>>1:0);}
int getlim(int n){int lim=1;while (lim<=n) lim<<=1;return lim;}

void dft(ll *a,int sig,int lim){
	for(int i=0;i<lim;i++) if (i<bt[i]) swap(a[i],a[bt[i]]);
	for(int mid=1;mid<lim;mid<<=1){
		int d=sig*maxn/(mid<<1),s=(sig<0)?maxn:0;
		for(int j=0;j<lim;j+=mid<<1){
			for(int k=0,p=s;k<mid;k++,p+=d){
				ll x=a[j+k],y=a[j+k+mid]*w[p];
				a[j+k]=(x+y)%mo,a[j+k+mid]=(x-y)%mo;
			}
		}
	}
}

void getinv(ll *a,ll *b,int lim){
	static ll A[maxn],B[maxn],C[maxn];
	clear(b,lim);
	b[0]=ksm(a[0],mo-2);
	for(int len=2;len<=lim;len<<=1){
		int L=len<<1;getbt(L);
		clear(A,L),clear(B,L);
		for(int i=0;i<len;i++) A[i]=a[i];
		for(int i=0;i<len;i++) B[i]=b[i];
		dft(A,1,L),dft(B,1,L);
		for(int i=0;i<L;i++) C[i]=A[i]*B[i]%mo*B[i]%mo;
		dft(C,-1,L);for(int i=0;i<L;i++) C[i]=C[i]*inv[L]%mo;
		for(int i=0;i<len;i++) b[i]=(b[i]*2-C[i])%mo;
	}
}

void multi(ll *a,ll *b,ll *c,int lim){
	getbt(lim);
	dft(a,1,lim),dft(b,1,lim);
	for(int i=0;i<lim;i++) c[i]=a[i]*b[i]%mo;
	dft(c,-1,lim);
	for(int i=0;i<lim;i++) c[i]=c[i]*inv[lim]%mo;
}

void getln(ll *a,ll *b,int lim){
	static ll A[maxn],B[maxn];
	clear(A,lim<<1),clear(B,lim<<1);
	for(int i=0;i<lim-1;i++) A[i]=a[i+1]*(i+1)%mo;
	getinv(a,B,lim);
	for(int i=lim;i<lim<<1;i++) A[i]=B[i]=0;
	multi(A,B,b,lim<<1);
	for(int i=lim-1;i>=0;i--) b[i+1]=b[i]*inv[i+1]%mo;b[0]=0;
	for(int i=lim;i<lim<<1;i++) b[i]=0;
}

void getexp(ll *a,ll *b,int lim){
	static ll G[maxn],F[maxn],H[maxn];
	clear(G,lim<<1),clear(F,lim<<1),clear(H,lim<<1);
	G[0]=1;
	for(int len=2;len<=lim;len<<=1){
		getln(G,F,len);
		for(int i=0;i<len;i++) F[i]=((i==0)-F[i]+a[i])%mo;
		multi(G,F,H,len<<1);
		for(int i=0;i<len;i++) G[i]=H[i];
		for(int i=len;i<len<<1;i++) G[i]=0;
	}
	for(int i=0;i<lim;i++) b[i]=G[i];
}

int main(){
	freopen("ceshi.in","r",stdin);
//	freopen("sum.in","r",stdin);
//	freopen("sum.out","w",stdout);
	prepare();
	scanf("%lld%lld%lld%lld",&S,&T,&n,&m);
	ll C=1;
	for(int i=0;i<=min(m-n,S-n*T);i++) 	
		a[i]=C,C=C*inv[i+1]%mo*((S-n*T-i)%mo)%mo;
	C=T;
	for(int i=0;i<=min(m-n,T);i++) 
		b[i]=C,C=C*inv[i+2]%mo*((T-i-1)%mo)%mo;
	ll k=b[0],invk=ksm(k,mo-2);
	for(int i=0;i<=m-n;i++) b[i]=b[i]*invk%mo;
	int lim=getlim(m-n);
	getln(b,c,lim);
	for(int i=0;i<lim;i++) b[i]=c[i]*(n%mo)%mo;
	getexp(b,c,lim);
	multi(c,a,b,lim<<1);
	printf("%lld",(b[m-n]*ksm(k,n)%mo+mo)%mo);
}