首先对于函数\(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\)处展开,即麦克劳林级数
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!}\)
注意到这是卷积的形式