生成函数相关
首先对于函数(F(x)),在(x_0)处泰勒展开,(F(x)=sumlimits_{n=0}^{+infin}dfrac{F^{n}(x_0)}{n!}(x-x_0)^n),这个(x)的取值是有一定范围的，当然我们也不关心
若在(x_0=0)处展开,即麦克劳林级数
OGF
对于数列(f),它的普通生成函数即为(F(x)=sumlimits_{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)=prodlimits_{i=1}^n A_i(x)=prodlimits_{i=1}^n dfrac{x^{(n_i+1)v_i}-1}{x^{v_i}-1})
付公主的背包
这个背包最多可以装 (10^5) 大小的东西
付公主有 (n) 种商品，她要准备出摊了
每种商品体积为 (v_i)，都有无限件
给定 (m)，对于 (sin [1,m])，请你回答用这些商品恰好装 (s) 体积的方案数
对于容量(V)的方案(A(x)=prodlimits_{i=1}^n A_i(x)=prodlimits_{i=1}^n dfrac{x^{(n_i+1)v_i}-1}{x^{v_u}-1}=prodlimits_{i=1}^n dfrac{1}{1-x^{v_i}})
同时去对数
(ln A(x)=sumlimits_{i=1}^nln dfrac{1}{1-x^{v_i}}=-sumlimits_{i=1}^nln ({1-x^{v_i}}))
根据上面的麦克劳林级数，即得(sumlimits_{i=1}^nsumlimits_{j=0}^{+infin}dfrac{x^{v_ij}}{j})
由于只取前(m+1)项,则(ln A(x)=sumlimits_{j=0}^{m}dfrac{1}{j}sumlimits_{i=1}^nx^{v_ij}(mod x^{m+1}))
考虑统计每个容量物品的个数(Num_i)
(ln A(x)=sumlimits_{j=0}^{m}dfrac{1}{j}sumlimits_{i=1}^mNum_ix^{ij}(mod x^{m+1})=sumlimits_{j=0}^{m}dfrac{1}{j}sumlimits_{i=1}^{lfloorfrac{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("%dn",A.U[i]); } } EGF
对于数列(f),它的指数生成函数即为(F(x)=sumlimits_{n=0}^{+infin}dfrac{f_n}{n!}x^n)
对于(dfrac{1}{n!})，相对于(OGF),可以理解为物品间有顺序,可以给每个物品打上标号
相当于(OGF)考虑的是组合,(EGF)考虑的是排列
所以(OGF)又称为无标号计数,(EGF)称为有标号计数
(EGF)的卷积(F(x)G(x)=sumlimits_{i=0}sumlimits_{j=0}dfrac{f_i}{i!}x^idfrac{g_j}{j!}x^j=sumlimits_{n=0}x^nsumlimits_{i=0}dfrac{f_i}{i!}dfrac{g_{n-i}}{(n-i)!}=sumlimits_{n=0}dfrac{x^n}{n!}sumlimits_{i=0}dfrac{f_i}{i!}dfrac{g_{n-i}}{(n-i)!}n!=)
(sumlimits_{n=0}dfrac{x^n}{n!}sumlimits_{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)=sumlimits_{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("%dn",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)=sumlimits_{i=1}^nS(n,i))
若给定(m),考虑(dfrac{A^m(x)}{m!})就相当于选取(m)个集合合并
则(S(n,m))给定(m)对应的生成函数即为(dfrac{(e^x-1)^m}{m!})(好像要用快速幂)
形式化的(sumlimits_{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!}sumlimits_{k=0}^mbinom{m}{k}e^{kx}(-1)^{m-k})
(S(n,m)=[x^n]F(x)n!),(e^{kx}=sumlimits_{n=0}dfrac{{(kx)}^n}{n!})
则(S(n,m)=dfrac{1}{m!}sumlimits_{k=0}^mbinom{m}{k}dfrac{k^n}{n!}(-1)^{m-k}n!=sumlimits_{k=0}^{m}dfrac{(-1)^{m-k}}{(m-k)!}timesdfrac{k^n}{k!})
注意到这是卷积的形式
