多项式整理（upd:2022.1.6）

多项式

by AmanoKumiko

1.求逆

需要\([x^0]f(x)≠0\)

2.ln

需要\([x^0]f(x)=1\)

3.Exp

需要\([x^0]f(x)=0\)

4.积化和

即将乘积先取对数再\(Exp\)

利用\(-ln(1-x)=\sum_{i=1}^{+∞}\frac{x^i}{i}\)求解

Problems：

【LuoguP4389】付公主的背包

【LuoguP5850】calc加强版

5.和化积

利用\(ln\)相关导数和\([f(x)±g(x)]'=f'(x)±g'(x)\)将和化为积

Problems:

【LuoguP4705】玩游戏

6.板子

#include
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define N 500010
#define mo 998244353

vectorIs;

int rev[N],G1[N],G2[N],fac[N],ifac[N],inv[N];

int mod(int x){return x>=mo?x-mo:x;}

int mi(int x,int y){
	if(y==1)return x;
	return y%2?1ll*x*mi(1ll*x*x%mo,y/2)%mo:mi(1ll*x*x%mo,y/2);
}

void init(){
	Is.push_back(1);
	fac[0]=ifac[0]=1;
	F(i,1,N-10)fac[i]=1ll*fac[i-1]*i%mo,inv[i]=(i==1?1:1ll*mo/i*mod(mo-1ll*inv[mo%i]%mo)%mo);
	ifac[N-10]=mi(fac[N-10],mo-2);
	Fd(i,N-11,1)ifac[i]=1ll*ifac[i+1]*(i+1)%mo;
	for(int l=1;l<=N-10;l<<=1)G1[l]=mi(3,(mo-1)/(l*2)),G2[l]=mi(G1[l],mo-2);
}

void BRT(int x){F(i,0,x-1)rev[i]=(rev[i>>1]>>1)|((i&1)?(x>>1):0);}

struct poly{
	vectorval;
	void clear(){vector().swap(val);}
	int sz(){return val.size();}
	void rsz(int x){val.resize(x);}
	void shrink(){for(;sz()&&!val.back();val.pop_back());}
	poly modxn(int x){
		if(val.size()<=x)return (poly){val};
		else return (poly){vector(val.begin(),val.begin()+x)};
	}
	poly I(){return (poly){Is};}
	int operator[](int x)const{
		if(x<0||x>=val.size())return 0;
		return val[x];
	}
	void NTT(int x){
		F(i,0,sz()-1)if(rev[i]y.sz())swap(x,y);
			poly ret;
			ret.rsz(x.sz()+y.sz());
			F(i,0,ret.sz()-1){
				for(int j=0;j<=i&&j=sz()?0:val[i+1])*(i+1)%mo;
		g=inver(Len);
		g*=f;
		g.modxn(Len);
		Fd(i,Len-1,1)g.val[i]=1ll*g[i-1]*inv[i]%mo;
		g.val[0]=0;
		return g.modxn(Len);
	}
	poly Exp(int Len){
		poly f;
		f.clear();
		f.val.push_back(1);
		for(int i=2;i