生成函数相关
\(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(xG(x\,是考虑将\(FG\这样拼接的方案,物品间不存在顺序
\(F=\{'A'\},G=\{'B'\}\,\(F(xG(x\即\(\{'A','B','AB'\}\(考虑空点
\(H\为\(G,F\的笛卡尔积,\(H\中为\(G,F\元素的有序二元组
\(|(a,b|=|a|+|b|\,则\(H(x=F(xG(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+1v_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+1v_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+1v_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 xconst{
return Cpx(a*x.a-b*x.b,b*x.a+a*x.b;
}
Cpx operator+(const Cpx xconst{
return Cpx(a+x.a,b+x.b;
}
Cpx operator-(const Cpx xconst{
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 longres*base%pff;
}
base=((long longbase*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 longW*Wn%MOD
{
int Xc=U[j];
int Yc=((long longU[j+l]*W%MOD;
U[j]=((long longXc+Yc%MOD;
U[j+l]=((long longXc-Yc+MOD%MOD;
}
}
}
if(type==-1
{
int Liv=inv(Len,MOD;
for(int i=0;i<Len;i++
{
U[i]=((long longU[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 longA.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 longFn.U[j]*(2-((long longFn.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 longi*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 longx.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 longFn.U[j]*(((long longH.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 longA.U[i*j]+((long longNum[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(xG(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 longres*base%pff;
}
base=((long longbase*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 longW*Wn%MOD
{
int Xc=U[j];
int Yc=((long longU[j+l]*W%MOD;
U[j]=((long longXc+Yc%MOD;
U[j+l]=((long longXc-Yc+MOD%MOD;
}
}
}
if(type==-1
{
int Liv=inv(Len,MOD;
for(int i=0;i<Len;i++
{
U[i]=((long longU[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 longA.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 longFn.U[j]*(2-((long longFn.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 longi*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 longx.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 longMul*i%MOD;
}
long long Kx=((long longi*(i-1;
Kx=((long longKx/2;
Kx=Pow(2,(Kx%(MOD-1,MOD;
Kx=((long longKx*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 longMul*i%MOD;
}
F.U[i]=((long longF.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(xA_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(xn!\,\(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!}\
注意到这是卷积的形式