首先對於函數\(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\)處展開,即麥克勞林級數
對於數列\(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]);
}
}
對於數列\(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\)的大小擴充套件了,同樣用不上
剛剛解決完電力網路的問題，阿狸又被領導的任務給難住了。
剛才說過，阿狸的國家有 \(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\)數即將\(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!}\)
注意到這是折積的形式