浅谈生成函数

时间:2023-01-28 18:07:36

首先对于函数\(F(x)\),在\(x_0\)处泰勒展开,\(F(x)=\sum\limits_{n=0}^{+\infin}\dfrac{F^{n}(x_0)}{n!}(x-x_0)^n\),这个\(x\)的取值是有一定范围的,当然我们也不关心

若在\(x_0=0\)处展开,即麦克劳林级数

\[(1-x)^{-1}=\sum\limits_{n=0}^{+\infty}x^n​ \\ (1-x)^{-m}=\sum\limits_{n=0}^{+\infty}\binom{n+m-1}{n}x^n​ \\ (1+x)^{m}=\sum\limits_{n=0}^{+\infty}\binom{m}{n}x^n​ \\ \ln(1-x)=-\sum\limits_{n=1}^{+\infty}\dfrac{x^n}{n}​ \\ \ln(1+x)=-\sum\limits_{n=1}^{+\infty}\dfrac{(-1)^{n}x^n}{n}​ \\ \exp x=\sum\limits_{n=0}^{+\infty}\dfrac{x^n}{n!}​ \]

OGF

对于数列\(f\),它的普通生成函数即为\(F(x)=\sum\limits_{n=0}^{+\infin}f_nx^n\),根据上式,对于任意数列都有一个函数对应

对于\(F(x)\),我们可以为其赋予一个组合意义

考虑集合\(F\)每个物品都有大小,对于\(f_nx^n\),\(f_n\)即为大小为\(n\)的物品(好像叫组合对象)

对于\(F(x)G(x)\),是考虑将\(FG\)这样拼接的方案,物品间不存在顺序

\(F=\{'A'\},G=\{'B'\}\),\(F(x)G(x)\)\(\{'A','B','AB'\}\)(考虑空点)

更形式化的,定义\(H\)\(G,F\)的笛卡尔积,\(H\)中为\(G,F\)元素的有序二元组

定义\(|(a,b)|=|a|+|b|\),则\(H(x)=F(x)G(x)\)


\(A\)为一些组合对象的集合,定义\(SEQ_A\)\(A\)中元素形成的\(n\)元笛卡尔积(类似于排列)

\(SEQ_A(x)=1+A(x)+A^2(x)+A^3(x).....=\dfrac{1}{1-A(x)}\)

其实就是\(A^p(x)\)考虑选\(p\)个元素对答案的贡献


\(OGF\)可以解决一类方案数背包问题

对于一个物品,容量为\(v_i\),数量为\(n_i\),定义\(A_i(x)=(1+x^{v_i}+x^{2v_i}...+x^{n_iv_i})=\dfrac{x^{(n_i+1)v_i}-1}{x^{v_u}-1}\)

对于容量\(V\)的方案\(A(x)=\prod\limits_{i=1}^n A_i(x)=\prod\limits_{i=1}^n \dfrac{x^{(n_i+1)v_i}-1}{x^{v_i}-1}\)


付公主的背包

这个背包最多可以装 \(10^5\) 大小的东西

付公主有 \(n\) 种商品,她要准备出摊了

每种商品体积为 \(v_i\),都有无限件

给定 \(m\),对于 \(s\in [1,m]\),请你回答用这些商品恰好装 \(s\) 体积的方案数

对于容量\(V\)的方案\(A(x)=\prod\limits_{i=1}^n A_i(x)=\prod\limits_{i=1}^n \dfrac{x^{(n_i+1)v_i}-1}{x^{v_u}-1}=\prod\limits_{i=1}^n \dfrac{1}{1-x^{v_i}}\)

同时去对数

\(\ln A(x)=\sum\limits_{i=1}^n\ln \dfrac{1}{1-x^{v_i}}=-\sum\limits_{i=1}^n\ln ({1-x^{v_i}})\)

根据上面的麦克劳林级数,即得\(\sum\limits_{i=1}^n\sum\limits_{j=0}^{+\infin}\dfrac{x^{v_ij}}{j}\)

由于只取前\(m+1\)项,则\(\ln A(x)=\sum\limits_{j=0}^{m}\dfrac{1}{j}\sum\limits_{i=1}^nx^{v_ij}(mod\ x^{m+1})\)

考虑统计每个容量物品的个数\(Num_i\)

\(\ln A(x)=\sum\limits_{j=0}^{m}\dfrac{1}{j}\sum\limits_{i=1}^mNum_ix^{ij}(mod\ x^{m+1})=\sum\limits_{j=0}^{m}\dfrac{1}{j}\sum\limits_{i=1}^{\lfloor\frac{m}{j}\rfloor}Num_ix^{ij}(mod\ x^{m+1})\)

直接枚举即可,调和级数得时间复杂度为\(\Theta(nlogn)\),最后\(Exp\)即可

分拆数就是物品权值为\(i\)的背包,直接套用即可

#include<bits/stdc++.h>
#define eps 1e-9
using namespace std;
const int MAXN=1e5+5;
const int MOD=998244353;
const int g=3;
const long double Pi=acos(-1.0);
const int p=32000;
int Rev[MAXN*4];
struct Cpx{
	long double a,b;
	Cpx(){
		a=0;
		b=0;
	} 
	Cpx(long double aa,long double bb){
		a=aa;
		b=bb;
	}
	Cpx operator*(const Cpx x)const{
		return Cpx(a*x.a-b*x.b,b*x.a+a*x.b);
	}
	Cpx operator+(const Cpx x)const{
		return Cpx(a+x.a,b+x.b);
	}
	Cpx operator-(const Cpx x)const{
		return Cpx(a-x.a,b-x.b);
	} 
};
int Pow(int a,int b,int pff){
	int res=1;
	int base=a;
	while(b)
	{
		if(b&1)
		{
			res=((long long)res*base)%pff;
		}
		base=((long long)base*base)%pff;
		b>>=1;
	}
	return res;
}
int inv(int a,int pff){
	return Pow(a,pff-2,pff);
}
struct Poly{
	vector<int>U;
	vector<Cpx>V;
	int size()
	{
		return U.size();
	}
	void push_back(int x)
	{
		U.push_back(x);
		return;
	}
	void clear()
	{
		U.clear();
		return;
	}
	void NTT(int Limit,int type)
	{
		int Len=(1<<Limit);
		for(int i=0;i<Len;i++)
		{
			Rev[i]=((Rev[i>>1]>>1)|((i&1)<<(Limit-1)));
		}
		
		while(U.size()<Len)
		{
			U.push_back(0);
		}
		for(int i=0;i<Len;i++)
		{
			if(i<Rev[i])
			{
				swap(U[i],U[Rev[i]]);
			}
		}
		for(int l=1;l<Len;l<<=1)
		{
			int Wn=Pow(g,(MOD-1)/(l<<1),MOD);
			if(type==-1)
			{
				Wn=inv(Wn,MOD);
			}
			for(int i=0;i<Len;i+=(l<<1))
			{
				int W=1;
				for(int j=i;j<i+l;j++,W=((long long)W*Wn)%MOD)
				{
					int Xc=U[j];
					int Yc=((long long)U[j+l]*W)%MOD;
					U[j]=((long long)Xc+Yc)%MOD;
					U[j+l]=((long long)Xc-Yc+MOD)%MOD;
				}
			}
		}
		if(type==-1)
		{
			int Liv=inv(Len,MOD); 
			for(int i=0;i<Len;i++)
			{
				U[i]=((long long)U[i]*Liv)%MOD;	
			}
		}
	}
};
Poly Mul_NTT(Poly A,Poly B){
	int N=A.U.size();
	int M=B.U.size();
	int nox=1;
	int Lm=0;
	while(nox<=(N+M-2))
	{
		nox<<=1;
		Lm++;
	 } 
	 A.NTT(Lm,1);
	 B.NTT(Lm,1);
	 for(int i=0;i<nox;i++)
	 {
	 	A.U[i]=((long long)A.U[i]*B.U[i])%MOD;
	 }
	 A.NTT(Lm,-1);
	 while(A.U.size()>(N+M-1))
	 {
	 	A.U.pop_back();
	 }
	 return A;
}
Poly Inverse(Poly A,int N){
	Poly Fn;
	Fn.U.clear();
	Fn.U.push_back(inv(A.U[0],MOD));
	if(N==1)
	{
		return Fn;
	}
	for(int l=2,Lm=1;(l>>1)<N;l<<=1,Lm++)
	{
		Poly H;
		H.U.clear();
		for(int j=0;j<l;j++)
		{
			if(j<A.U.size())
			{
				H.U.push_back(A.U[j]);
			}
			else
			{
				H.U.push_back(0);
			}
		}	
		H.NTT(Lm+1,1);
		Fn.NTT(Lm+1,1);
		
		for(int j=0;j<l*2;j++)
		{
			Fn.U[j]=((long long)Fn.U[j]*(2-((long long)Fn.U[j]*H.U[j])%MOD+MOD)%MOD)%MOD;
		}
		Fn.NTT(Lm+1,-1);
		while(Fn.U.size()>l)
		{
			Fn.U.pop_back();
		}
	}
	while(Fn.U.size()>N)
	{
		Fn.U.pop_back();
	}
	return Fn;
}
Poly Der(Poly x){
	Poly Nex;
	Nex.U.clear();
	for(int i=1;i<x.U.size();i++){
		Nex.U.push_back(((long long)i*x.U[i])%MOD);
	}
	return Nex;
}
Poly Ing(Poly x){
	Poly Nex;
	Nex.U.clear();
	Nex.U.push_back(0);
	for(int i=0;i<x.U.size();i++)
	{
		Nex.U.push_back(((long long)x.U[i]*inv(i+1,MOD))%MOD);
	}
	return Nex;
}
Poly Ln(Poly x,int N){
	Poly ex=Der(x);
	Poly ey=Inverse(x,N);
	ex=Mul_NTT(ex,ey);
	ex=Ing(ex);
	while(ex.U.size()>N)
	{
		ex.U.pop_back();
	}	
	return ex;
}
Poly Exp(Poly A,int N){
	Poly Fn;
	Fn.U.clear();
	Fn.U.push_back(1);
	if(N==1)
	{
		return Fn;
	}
	for(int l=2,Lm=1;(l>>1)<N;l<<=1,Lm++)
	{
		Poly H;
		H.U.clear();
		for(int j=0;j<l;j++)
		{
			if(j<A.U.size())
			{
				H.U.push_back(A.U[j]);
			}
			else
			{
				H.U.push_back(0);
			}
		}	
		Poly Fln=Ln(Fn,l);
		H.NTT(Lm+1,1);
		Fn.NTT(Lm+1,1);
		Fln.NTT(Lm+1,1);
		for(int j=0;j<l*2;j++)
		{
			Fn.U[j]=((long long)Fn.U[j]*(((long long)H.U[j]+1-Fln.U[j]+MOD)%MOD))%MOD;
		}
		Fn.NTT(Lm+1,-1);
		while(Fn.U.size()>l)
		{
			Fn.U.pop_back();
		}
	}
	while(Fn.U.size()>N)
	{
		Fn.U.pop_back();
	}
	return Fn;
}
int n;
int m;
int Num[MAXN];
int v;
signed main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&v);
		Num[v]++;
	}
	Poly A;
	A.clear();
	A.U.resize(m+1);
	for(int j=1;j<=m;j++)
	{
		int FUc=inv(j,MOD);
		for(int i=1;i<=(m/j);i++)
		{
			
			A.U[i*j]=((long long)A.U[i*j]+((long long)Num[i]*FUc)%MOD)%MOD;
		}
	}
	A=Exp(A,m+1);
	for(int i=1;i<=m;i++)
	{
		printf("%d\n",A.U[i]);
	}
}

EGF

对于数列\(f\),它的指数生成函数即为\(F(x)=\sum\limits_{n=0}^{+\infin}\dfrac{f_n}{n!}x^n\)

对于\(\dfrac{1}{n!}\),相对于\(OGF\),可以理解为物品间有顺序,可以给每个物品打上标号

相当于\(OGF\)考虑的是组合,\(EGF\)考虑的是排列

所以\(OGF\)又称为无标号计数,\(EGF\)称为有标号计数

\(EGF\)的卷积\(F(x)G(x)=\sum\limits_{i=0}\sum\limits_{j=0}\dfrac{f_i}{i!}x^i\dfrac{g_j}{j!}x^j=\sum\limits_{n=0}x^n\sum\limits_{i=0}\dfrac{f_i}{i!}\dfrac{g_{n-i}}{(n-i)!}=\sum\limits_{n=0}\dfrac{x^n}{n!}\sum\limits_{i=0}\dfrac{f_i}{i!}\dfrac{g_{n-i}}{(n-i)!}n!=\)

\(\sum\limits_{n=0}\dfrac{x^n}{n!}\sum\limits_{i=0}f_ig_{n-i}\binom{n}{i}\)

由此,\(EGF\)的卷积类似于有标号的计数的合并,又称为二次卷积

这里的合并不是两段序列接在一起,是在保持\(F,G\)原有先后顺序的前提下构成一个新的序列


\(A\)为带标号的组合对象集合,\(SEQ_A\)同样为\(n\)元笛卡尔积组成的集合

\(SEQ_A(x)=1+A(x)+A^2(x)+A^3(x).....=\dfrac{1}{1-A(x)}\)

\(SET_A\)\(n\)元笛卡尔积(不考虑顺序)组成的集合

\(SET_A(x)=1+A(x)+\dfrac{A^2(x)}{2!}+\dfrac{A^3(x)}{3!}+\dfrac{A^4(x)}{4!}....=e^{A(x)}\)

注意,对于\(SEQ\),笛卡尔积本身是有顺序的,\(EGF\)这样相当于合并时不同集合有先后,一般没有运用场景,而\(OGF\)的笛卡尔积是在\(A,B\)集合各选一个拼接,\(A,B\)内部是无顺序的

对于\(SET\),\(EGF\)就是合并\(A,B\)的元素然后重标号,\(OGF\)则相当于把集合\(A\)的大小扩展了,同样用不上


[集训队作业2013]城市规划

刚刚解决完电力网络的问题,阿狸又被领导的任务给难住了。

刚才说过,阿狸的国家有 \(n\) 个城市,现在国家需要在某些城市对之间建立一些贸易路线,使得整个国家的任意两个城市都直接或间接的连通。

为了省钱, 每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案,如果存在一个城市对,在两个方案中是否建立路线不一样,那么这两个方案就是不同的,否则就是相同的。现在你需要求出一共有多少不同的方案。

好了,这就是困扰阿狸的问题。换句话说,你需要求出 \(n\) 个点的简单 (无重边无自环) 有标号无向连通图数目。

由于这个数字可能非常大, 你只需要输出方案数对 \(1004535809\) ( \(479 \times 2 ^{21} + 1\) ) 即可。

考虑任意一个简单无向图与连通图的关系

带标号无向图实际上就是一些带标号连通图合并而成

\(F(x)\)为有\(n\)个点无向图的方案的指数生成函数,\(G(x)\)为有\(n\)个点连通图的方案的指数生成函数

\(F(x)=SET_G=exp(G(x))\)

\(G(x)=\ln(F(x))\)

考虑\(F(x)\)的构成

\(F(x)=\sum\limits_{n=0}2^{\binom{n}{2}}\dfrac{x^n}{n!}\)

\(\binom{n}{2}\)是边的总数,考虑先给点标号,然后边选或不选

注意模数不一样,\(g=3\),\(\binom{n}{2}\)不能直接取模

#include<bits/stdc++.h>
#define eps 1e-9
using namespace std;
const int MAXN=2e5+5;
const int MOD=1004535809;
const int g=3;
int Rev[MAXN*4];
int Pow(int a,int b,int pff){
	int res=1;
	int base=a;
	while(b)
	{
		if(b&1)
		{
			res=((long long)res*base)%pff;
		}
		base=((long long)base*base)%pff;
		b>>=1;
	}
	return res;
}
int inv(int a,int pff){
	return Pow(a,pff-2,pff);
}
struct Poly{
	vector<int>U;
	int size()
	{
		return U.size();
	}
	void push_back(int x)
	{
		U.push_back(x);
		return;
	}
	void clear()
	{
		U.clear();
		return;
	}
	void NTT(int Limit,int type)
	{
		int Len=(1<<Limit);
		for(int i=0;i<Len;i++)
		{
			Rev[i]=((Rev[i>>1]>>1)|((i&1)<<(Limit-1)));
		}
		
		while(U.size()<Len)
		{
			U.push_back(0);
		}
		for(int i=0;i<Len;i++)
		{
			if(i<Rev[i])
			{
				swap(U[i],U[Rev[i]]);
			}
		}
		for(int l=1;l<Len;l<<=1)
		{
			int Wn=Pow(g,(MOD-1)/(l<<1),MOD);
			if(type==-1)
			{
				Wn=inv(Wn,MOD);
			}
			for(int i=0;i<Len;i+=(l<<1))
			{
				int W=1;
				for(int j=i;j<i+l;j++,W=((long long)W*Wn)%MOD)
				{
					int Xc=U[j];
					int Yc=((long long)U[j+l]*W)%MOD;
					U[j]=((long long)Xc+Yc)%MOD;
					U[j+l]=((long long)Xc-Yc+MOD)%MOD;
				}
			}
		}
		if(type==-1)
		{
			int Liv=inv(Len,MOD); 
			for(int i=0;i<Len;i++)
			{
				U[i]=((long long)U[i]*Liv)%MOD;	
			}
		}
	}
};
Poly Mul_NTT(Poly A,Poly B){
	int N=A.U.size();
	int M=B.U.size();
	int nox=1;
	int Lm=0;
	while(nox<=(N+M-2))
	{
		nox<<=1;
		Lm++;
	 } 
	 A.NTT(Lm,1);
	 B.NTT(Lm,1);
	 for(int i=0;i<nox;i++)
	 {
	 	A.U[i]=((long long)A.U[i]*B.U[i])%MOD;
	 }
	 A.NTT(Lm,-1);
	 while(A.U.size()>(N+M-1))
	 {
	 	A.U.pop_back();
	 }
	 return A;
}
Poly Inverse(Poly A,int N){
	Poly Fn;
	Fn.U.clear();
	Fn.U.push_back(inv(A.U[0],MOD));
	if(N==1)
	{
		return Fn;
	}
	for(int l=2,Lm=1;(l>>1)<N;l<<=1,Lm++)
	{
		Poly H;
		H.U.clear();
		for(int j=0;j<l;j++)
		{
			if(j<A.U.size())
			{
				H.U.push_back(A.U[j]);
			}
			else
			{
				H.U.push_back(0);
			}
		}	
		H.NTT(Lm+1,1);
		Fn.NTT(Lm+1,1);
		
		for(int j=0;j<l*2;j++)
		{
			Fn.U[j]=((long long)Fn.U[j]*(2-((long long)Fn.U[j]*H.U[j])%MOD+MOD)%MOD)%MOD;
		}
		Fn.NTT(Lm+1,-1);
		while(Fn.U.size()>l)
		{
			Fn.U.pop_back();
		}
	}
	while(Fn.U.size()>N)
	{
		Fn.U.pop_back();
	}
	return Fn;
}
Poly Der(Poly x){
	Poly Nex;
	Nex.U.clear();
	for(int i=1;i<x.U.size();i++){
		Nex.U.push_back(((long long)i*x.U[i])%MOD);
	}
	return Nex;
}
Poly Ing(Poly x){
	Poly Nex;
	Nex.U.clear();
	Nex.U.push_back(0);
	for(int i=0;i<x.U.size();i++)
	{
		Nex.U.push_back(((long long)x.U[i]*inv(i+1,MOD))%MOD);
	}
	return Nex;
}
Poly Ln(Poly x,int N){
	Poly ex=Der(x);
	Poly ey=Inverse(x,N);
	ex=Mul_NTT(ex,ey);
	ex=Ing(ex);
	while(ex.U.size()>N)
	{
		ex.U.pop_back();
	}	
	return ex;
}
int n;
signed main(){
	scanf("%d",&n);
	int Mul=1;
	Poly F;
	F.clear();
	F.U.resize(n+1);
	for(int i=0;i<=n;i++)
	{
		if(i==0)
		{
			Mul=1;
		}	
		else
		{
			Mul=((long long)Mul*i)%MOD;
		}
		long long Kx=((long long)i*(i-1));
		Kx=((long long)Kx/2);
		Kx=Pow(2,(Kx%(MOD-1)),MOD);
		Kx=((long long)Kx*inv(Mul,MOD))%MOD;
		F.U[i]=Kx;
	}
	F=Ln(F,n+1);
	Mul=1;
	for(int i=0;i<F.size();i++)
	{
		if(i==0)
		{
			Mul=1;
		}	
		else
		{
			Mul=((long long)Mul*i)%MOD;
		}
		F.U[i]=((long long)F.U[i]*Mul)%MOD;
	}
	printf("%d\n",F.U[n]);
}

Bell数及相关的的第二类斯特林数

\(Bell\)数即将\(n\)个不同元素划分的方案数记为\(B_n\)

考虑现在有一个大小为\(m_1\)的只有一种标号方法的集合\(A_1\),和大小为\(m_2\)\(A_2\)

\(A_1(x)A_2(x)\)即为\(A_1\)中的元素划分在一起,\(A2\)的元素划分在一起,而\(A_1\)内部是无顺序的

由此\(Bell\)数为若干个子集合并而来,而子集内部不带顺序

考虑一个子集的\(EGF\),我们为了内部无顺序因此先钦定顺序

\(A(x)=x+\dfrac{x^2}{2}+\dfrac{x^3}{3!}+\dfrac{x^4}{4!}...=e^x-1\)

\(B(x)=1+A(x)+\dfrac{A(x)^2}{2}+\dfrac{A(x)^3}{3!}+\dfrac{A(x)^4}{4!}...=e^{e^x-1}\)

第二类斯特林数\(S(n,m)\)表示有\(n\)个不同的元素划分为\(m\)个不同的集合的方案

\(B(n)=\sum\limits_{i=1}^nS(n,i)\)

若给定\(m\),考虑\(\dfrac{A^m(x)}{m!}\)就相当于选取\(m\)个集合合并

\(S(n,m)\)给定\(m\)对应的生成函数即为\(\dfrac{(e^x-1)^m}{m!}\)(好像要用快速幂)

形式化的\(\sum\limits_{n=0}^{+\infin}S(n,m)\dfrac{x^n}{n!}=\dfrac{(e^x-1)^m}{m!}\)

考虑左式二项式展开

\(\dfrac{(e^x-1)^m}{m!}=\dfrac{1}{m!}\sum\limits_{k=0}^m\binom{m}{k}e^{kx}(-1)^{m-k}\)

\(S(n,m)=[x^n]F(x)n!\),\(e^{kx}=\sum\limits_{n=0}\dfrac{{(kx)}^n}{n!}\)

\(S(n,m)=\dfrac{1}{m!}\sum\limits_{k=0}^m\binom{m}{k}\dfrac{k^n}{n!}(-1)^{m-k}n!=\sum\limits_{k=0}^{m}\dfrac{(-1)^{m-k}}{(m-k)!}\times\dfrac{k^n}{k!}\)

注意到这是卷积的形式