您的位置: 首页  >  IT文章  >  多项式学习笔记

多项式学习笔记

分类: IT文章 • 2023-11-27 18:46:42

P5349 幂 [分治(fft)]

设(f(n)=sumlimits_i a_i x^i)，考虑求(F(x)=sumlimits_{n=0}^{infty} n^x r^n)，其中(F(0)=frac{1}{1-r})

[(1-r)F(x)=sumlimits_{n=0}^{infty} n^x r^n-sumlimits_{n=0}^{infty} n^x r^{n+1}=sumlimits_{n=0}^{infty} n^x r^n-sumlimits_{n=1}^{infty} (n-1)^x r^{n} ]

[(r-1)F(x)=sumlimits_{n=1}^{infty} r^n ((n-1)^x-n^x)=sumlimits_{n=1}^{infty} r^n sumlimits_{i=0}^{x-1} C_{x}^{i} (-1)^{x-i} n^i=sumlimits_{i=0}^{x-1} C_{x}^{i} (-1)^{x-i} sumlimits_{n=1}^{infty} n^i r^n ]

我们发现(sumlimits_{n=1}^{infty} n^i r^n)几乎就是(F(i))，只是在(i=0)时它是(F(0)-1)，考虑先将(F(0))减一。

[(r-1)F(x)=sumlimits_{i=0}^{x-1} C_{x}^{i} (-1)^{x-i} F(i)=sumlimits_{i=0}^{x-1} frac{x!}{i!(x-i)!} (-1)^{x-i} F(i) ]

[frac{F(x)}{x!}=sumlimits_{i=0}^{x-1} frac{1}{r-1} frac{(-1)^{x-i}}{(x-i)!} frac{F(i)}{i!} ]

分治(fft)即可，最后(F(0))要加一，答案即为(sumlimits_{i=0}^m a_iF(i)i!)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int mod=998244353;
const int G=3;
const int iG=(mod+1)/3;
const int inv2=(mod+1)/2;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
inline int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=res*x%mod;
		x=x*x%mod;y>>=1;
	}
	return res;
}
int tr[maxn];
int n,p,ans,a[maxn],b[maxn];
inline void ntt(int *f,int len,int flag){
    for(int i=0;i<len;i++)
        if(i<tr[i])swap(f[i],f[tr[i]]);
    for(int i=2;i<=len;i<<=1){
        int w=ksm(flag?G:iG,(mod-1)/i);
        for(int j=0,p=i>>1;j<len;j+=i){
            int wi=1;
            for(int k=j;k<j+p;k++){
                int tt=1ll*wi*f[k+p]%mod;
                f[k+p]=(f[k]-tt+mod)%mod;
                f[k]=(f[k]+tt)%mod;
                wi=wi*w%mod;
            }
        }
    }
    if(flag==0){
        int iv=ksm(len,mod-2);
        for(int i=0;i<len;i++)
            f[i]=f[i]*iv%mod;
    }
}
int f[maxn],g[maxn];
inline void cdqfft(int l,int r){
	if(l+1>=r)return;
	int mid=(l+r)>>1,len=r-l;
	cdqfft(l,mid);
	for(int i=0;i<len;i++)g[i]=a[i];
	for(int i=l;i<mid;i++)f[i-l]=b[i];
	for(int i=mid;i<r;i++)f[i-l]=0;
	for(int i=0;i<len;i++)
		tr[i]=(tr[i>>1]>>1)|((i&1)?len>>1:0);
	ntt(g,len,1),ntt(f,len,1);
	for(int i=0;i<len;i++)
		f[i]=g[i]*f[i]%mod;
	ntt(f,len,0);
	for(int i=mid;i<r;i++)
		b[i]=(b[i]+f[i-l])%mod;
	cdqfft(mid,r);
}
int inv[maxn],ifc[maxn],fac[maxn];
signed main(){
	n=read()+1,p=read();
	inv[1]=ifc[0]=fac[0]=1;
	for(int i=2;i<=n;i++)
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<=n;i++)
		ifc[i]=ifc[i-1]*inv[i]%mod;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%mod;
	int iv=ksm(p-1,mod-2);
	for(int i=1;i<n;i++)
		a[i]=(i&1?mod-ifc[i]:ifc[i])*iv%mod;
	int len=1;for(;len<n;len<<=1);
	b[0]=ksm(1+mod-p,mod-2)-1;cdqfft(0,len);b[0]++;
	for(int i=0;i<n;i++){
		int x=read();
		ans=(ans+x*b[i]%mod*fac[i]%mod)%mod;
	}
	printf("%lld",ans);
	return 0;
}

P4841 [集训队作业2013]城市规划 [多项式ln]

结论：(n)元的命题(x)( ightarrow)随意划分(n)后每一个子集的命题(x)，则后者是前者的( ext{exp})

套用结论，(n)点无向连通图个数的( ext{exp})为(n)点无向图个数。

而显然后者的个数是(2^{C_{n}^2})，那么多项式( ext{ln})一下即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int mod=1004535809;
const int G=3;
const int iG=(mod+1)/3;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
inline int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=res*x%mod;
		x=x*x%mod;y>>=1;
	}
	return res;
}
int tr[maxn],inv[maxn];
int n,a[maxn],b[maxn],c[maxn];
inline void ntt(int *f,int len,int flag){
    for(int i=0;i<len;i++)
        if(i<tr[i])swap(f[i],f[tr[i]]);
    for(int i=2;i<=len;i<<=1){
        int w=ksm(flag?G:iG,(mod-1)/i);
        for(int j=0,p=i>>1;j<len;j+=i){
            int wi=1;
            for(int k=j;k<j+p;k++){
                int tt=1ll*wi*f[k+p]%mod;
                f[k+p]=(f[k]-tt+mod)%mod;
                f[k]=(f[k]+tt)%mod;
                wi=wi*w%mod;
            }
        }
    }
    if(flag==0){
        int iv=ksm(len,mod-2);
        for(int i=0;i<len;i++)
            f[i]=f[i]*iv%mod;
    }
}
inline void workinv(int deg,int *a,int *b){
	if(deg==1)return void(b[0]=ksm(a[0],mod-2));
	workinv((deg+1)>>1,a,b);
	int len=1;for(;len<=(deg<<1);len<<=1);
	for(int i=0;i<len;i++)
		tr[i]=(tr[i>>1]>>1)|((i&1)?len>>1:0);
	for(int i=0;i<deg;i++)c[i]=a[i];
	for(int i=deg;i<len;i++)c[i]=0;
	ntt(c,len,1);ntt(b,len,1);
	for(int i=0;i<len;i++)
		b[i]=b[i]*(2-b[i]*c[i]%mod+mod)%mod;
	ntt(b,len,0);
	for(int i=deg;i<len;i++)b[i]=0;
}
inline void dif(int *a,int *b,int len){
	for(int i=0;i<len;i++)
		a[i]=b[i+1]*(i+1)%mod;
}
inline void iit(int *a,int *b,int len){
	inv[1]=1;a[0]=0;
	for(int i=2;i<=len;i++)
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<len;i++)
		a[i]=b[i-1]*inv[i]%mod;
}
inline void mul(int *a,int *b,int n){
	int len=1;for(;len<=(n<<1);len<<=1);
	for(int i=0;i<len;i++)
		tr[i]=(tr[i>>1]>>1)|((i&1)?len>>1:0);
	ntt(a,len,1);ntt(b,len,1);
	for(int i=0;i<len;i++)a[i]=a[i]*b[i]%mod;
	ntt(a,len,0);
}
int f[maxn],fac[maxn];
signed main(){
	n=read()+1;
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%mod;
	for(int i=0;i<n;i++)
		a[i]=ksm(2,i*(i-1)/2)*ksm(fac[i],mod-2)%mod;
	dif(f,a,n);
	workinv(n,a,b);
	mul(f,b,n);
	iit(a,f,n);
	printf("%lld
",a[n-1]*fac[n-1]%mod);
	return 0;
}

CF438E The Child and Binary Tree [多项式开根，多项式求逆]

设(a_i)代表(i)是否在(c)中出现过，(f_i)代表和为(i)的二叉树个数，(f_0=1)。

[f_i=sumlimits_{j=1}^i a_j sumlimits_{k=0}^{i-j} f_k f_{i-j-k} ]

这几乎就是卷积形式，但可惜(i=0)时不符合，但没关系，多项式是可以单独加上尾项的系数的。

[f=a*(f*f)+1=af^2+1 ]

[f=frac{1pm sqrt{1-4a}}{2a}=frac{2}{1mp sqrt{1-4a}} ]

经验证，(f=frac{2}{1+sqrt{1-4a}})，多项式开根然后求逆即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int mod=998244353;
const int G=3;
const int iG=(mod+1)/3;
const int inv2=(mod+1)/2;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
inline int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=res*x%mod;
		x=x*x%mod;y>>=1;
	}
	return res;
}
int tr[maxn];
int n,m,a[maxn],b[maxn],c[maxn];
inline void ntt(int *f,int len,int flag){
    for(int i=0;i<len;i++)
        if(i<tr[i])swap(f[i],f[tr[i]]);
    for(int i=2;i<=len;i<<=1){
        int w=ksm(flag?G:iG,(mod-1)/i);
        for(int j=0,p=i>>1;j<len;j+=i){
            int wi=1;
            for(int k=j;k<j+p;k++){
                int tt=1ll*wi*f[k+p]%mod;
                f[k+p]=(f[k]-tt+mod)%mod;
                f[k]=(f[k]+tt)%mod;
                wi=wi*w%mod;
            }
        }
    }
    if(flag==0){
        int iv=ksm(len,mod-2);
        for(int i=0;i<len;i++)
            f[i]=f[i]*iv%mod;
    }
}
inline void workinv(int deg,int *a,int *b){
	if(deg==1)return void(b[0]=ksm(a[0],mod-2));
	workinv((deg+1)>>1,a,b);
	int len=1;for(;len<=(deg<<1);len<<=1);
	for(int i=0;i<len;i++)
		tr[i]=(tr[i>>1]>>1)|((i&1)?len>>1:0);
	for(int i=0;i<deg;i++)c[i]=a[i];
	for(int i=deg;i<len;i++)c[i]=0;
	ntt(c,len,1);ntt(b,len,1);
	for(int i=0;i<len;i++)
		b[i]=b[i]*(2-b[i]*c[i]%mod+mod)%mod;
	ntt(b,len,0);
	for(int i=deg;i<len;i++)b[i]=0;
}
int f[maxn],g[maxn];
inline void worksqrt(int deg,int *a,int *b){
	if(deg==1)return void(b[0]=1);
	worksqrt((deg+1)>>1,a,b);
	int len=1;for(;len<=(deg<<1);len<<=1);
	for(int i=0;i<len;i++)f[i]=g[i]=0;
	for(int i=0;i<deg;i++)f[i]=a[i];
	workinv(deg,b,g);
	ntt(b,len,1);ntt(f,len,1);ntt(g,len,1);
	for(int i=0;i<len;i++)
		b[i]=inv2*g[i]%mod*(f[i]+b[i]*b[i]%mod)%mod;
	ntt(b,len,0);
	for(int i=deg;i<len;i++)b[i]=0;
}
signed main(){
	n=read(),m=read()+1;
	int x;
	for(int i=0;i<n;i++)
		x=read(),a[x]=1;
	a[0]=1;
	for(int i=1;i<m;i++)
		if(a[i])a[i]=mod-4;
	worksqrt(m,a,b);b[0]++;
	for(int i=0;i<m<<1;i++)
		a[i]=b[i],b[i]=0;
	workinv(m,a,b);
	for(int i=1;i<m;i++)
		printf("%lld ",2*b[i]%mod);
	return 0;
}

P3723 [AH2017/HNOI2017]礼物 [ntt]

(val=sum (a_i-b_i+c)^2=sum (a_i^2+b_i^2)+nc^2+2csum (a_i-b_i)+sum a_ib_i)

容易发现除了最后一项其他都可以线性求出最值，(sum a_ib_i)直接套路地(ntt)即可。

之前的做法是枚举的(c)，匆匆改过来导致代码有点乱，体谅一下。

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=1e6+10;
const int mod=998244353;
const int G=3;
const int iG=(mod+1)/3;
int n,m,len=1,tr[maxn],a[maxn],b[maxn];
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
inline int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=1ll*res*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return res;
}
inline void ntt(int *f,int len,int flag){
	for(int i=0;i<len;i++)
		if(i<tr[i])swap(f[i],f[tr[i]]);
	for(int p=2;p<=len;p<<=1){
		int l=p>>1,w=ksm(flag?G:iG,(mod-1)/p);
		for(int i=0;i<len;i+=p){
			int wi=1;
			for(int j=i;j<i+l;j++){
				int t=1ll*wi*f[j+l]%mod;
				f[j+l]=(f[j]-t+mod)%mod;
				f[j]=(f[j]+t)%mod;
				wi=1ll*w*wi%mod;
			}
		}
	}
	if(!flag){
		int iv=ksm(len,mod-2);
		for(int i=0;i<len;i++)
			f[i]=1ll*f[i]*iv%mod;
	}
}
int f[maxn],g[maxn],ans=inf,base=inf;
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	for(;len<=(n<<2);len<<=1);
	for(int i=0;i<len;i++)
		tr[i]=(tr[i>>1]>>1)|((i&1)?len>>1:0);
	int s2=0,s1=0;
	for(int i=1;i<=n;i++)
		s2+=a[i]*a[i]+b[i]*b[i],s1+=a[i]-b[i];
	//printf("s1=%d s2=%d
",s1,s2);
	for(int i=-m;i<=m;i++)
		base=min(base,s2+2*s1*i+n*i*i);
	//printf("base=%d
",base);
	for(int c=0;c<=0;c++){
		for(int i=0;i<len;i++)f[i]=g[i]=0;
		for(int i=1;i<=n;i++)f[n-i]=(a[i]+c+mod)%mod;
		for(int i=0;i<n;i++)g[i+n]=g[i]=b[i+1];
		//int base=0;for(int i=0;i<n;i++)base+=1ll*f[i]*f[i]%mod+g[i]*g[i];
		ntt(f,len,1),ntt(g,len,1);
		for(int i=0;i<len;i++)f[i]=1ll*f[i]*g[i]%mod;
		ntt(f,len,0);
		for(int i=n-1;i<=2*n-2;i++)
			ans=min(ans,(base-2*f[i]%mod+mod)%mod);
	}
	printf("%d
",ans);
	return 0;
}

CF891E Lust [EGF]

发现操作的顺序无影响，故套路地设第(i)个被减了(b_i)次，稍加推导发现结果即为(prod a_i-prod (a_i-b_i))。

即最终答案为(prod a_i -frac{1}{n^k} sum frac{k!}{prod b_i!} prod (a_i-b_i))(*)，漂亮的( ext{EGF})式子，可惜我到这就不会了。

考虑单个的生成函数(f_p=sum frac{a_p-i}{i!} x^i)，发现可以化简，(f_p=(a_p-x)e^x)，整体即为(F=e^{nx}prod (a_i-x))

注意到这一坨(prod (a_i-x))的最大次数只有(n)，可以(n^2)递推出来系数，不妨设为({c_i})，即(sum c_i x^i)

根据(e)的定义，(e^{nx}=sum frac{(nx)^i}{i!})，则([x^k]F=sumlimits_{i=0}^n c_i frac{n^{k-i}}{(k-i)!})，带入*式即为(c_0-sumlimits_{i=0}^nfrac{c_i k!}{n^i (k-i)!})

暴力计算答案即可，时间复杂度为(Theta(n))

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
const int mod=1e9+7;
int n,k,f[maxn],a[maxn],ans,inv;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
inline int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=res*x%mod;
		x=x*x%mod;y>>=1;
	}
	return res;
}
signed main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	f[0]=1;inv=ksm(n,mod-2);
	for(int i=1;i<=n;i++){
		for(int j=i;j;--j)
			f[j]=(a[i]*f[j]%mod-f[j-1]+mod)%mod;
		f[0]=f[0]*a[i]%mod;
	}
	for(int i=0,tmp=1;i<=n&&i<=k;i++){
		ans=(ans+f[i]*tmp%mod)%mod;
		tmp=tmp*(k-i)%mod*inv%mod;
	}
	printf("%lld
",(f[0]-ans+mod)%mod);
	return 0;
}

相关推荐