差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:lgwza:生成函数理论_5_一些例子 [2021/02/21 21:00]
lgwza
+++ 2020-2021:teams:legal_string:lgwza:生成函数理论_5_一些例子 [2021/02/21 21:08] (当前版本)
lgwza
@@ 行 161: / 行 161: @@
 $$ 因此 $$
 B_n=\frac{1}{e}\sum_{k=0}^{\infty}\frac{k^n}{k!}.
+$$ $\Box$
+==== 例 3 ====
+=== 题意 ===
+[[https://www.luogu.com.cn/problem/P4451|P4451 [国家集训队]整数的lqp拆分]]
+=== 题解 ===
+Fibonacci 数的生成函数是这个（基础知识）： $$
+F(x)=\frac{x}{1-x-x^2}
+$$ 当拆分为恰好 $k$ 个数时，答案的生成函数是 $F(x)^k$，那么答案的生成函数即为 $$
+\begin{align}
+G(x)&=\sum_{i=0}^{\infty}F(x)^i\\
+&=\frac{1}{1-F(x)}\\
+&=\frac{1-x-x^2}{1-2x-x^2}\\
+&=1+\frac{x}{1-2x-x^2}\\
+&=1+\frac{\sqrt 2}{4}(\frac{1}{1-(1+\sqrt 2)x}-\frac{1}{1-(1-\sqrt 2)x})\\
+&=1+\frac{\sqrt 2}{4}\sum_{n=0}^{\infty}[(1+\sqrt 2)^n-(1-\sqrt 2)^n]x^n
+\end{align}
+$$ 所以通项公式为 $$
+a_n\equiv \frac{\sqrt 2}{4}[(1+\sqrt 2)^n-(1-\sqrt 2)^n]\pmod{1e9+7}
+$$ 需要用二次剩余解出 $x^2\equiv 2\pmod{1e9+7}$
+=== 评价 ===
+对于理解生成函数和公式推导有一定的帮助
+=== 代码 ===
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+const ll mod=1e9+7;
+const ll two=59713600;
+ll ksm(ll x,ll y){
+    ll ret=1;
+    for(;y;y>>=1,x=x*x%mod)
+        if(y&1) ret=ret*x%mod;
+    return ret;
+}
+int main(){
+    string s;
+    cin>>s;
+    ll n=0;
+    int len=s.length();
+    for(int i=0;i<len;i++){
+        n=(n*10+s[i]-'0')%(mod-1);
+    }
+    n=(n+(mod-1))%mod;
+    n++;
+    ll ans=(ksm(1+two,n)-ksm((1-two+mod)%mod,n)+mod)%mod*two/4%mod;
+    printf("%lld",ans);
+    return 0;
+}
+// sqrt(2):59713600
+</code>
+</hidden>
+=== 拓展 ===
+令 $a_n$ 表示在一个 n-集合上完成某个任务的方法数，$a_0=0$。对于 $n\ge 1$，令 $b_n$ 表示将集合 $[n]$ 划分成任意的连续、非空区间段，然后在这些非空区间段上完成前面任务的方法数，$b_0=1$。设 $\{a_n\}_{n=0}^{\infty}$ 和 $\{b_n\}_{n=0}^{\infty}$ 的普通生成函数分别为 $f(x)$ 和 $g(x)$，则对任意固定的正整数 $i$，将 $[n]$ 划分成 $i$ 个非空子区间时，所对应的方法数的普通生成函数为 $f^i(x)$，且有 $$
+g(x)=\frac{1}{1-f(x)}.
 $$
+==== 例 4 ====
+=== 题意 ===
+[[https://www.luogu.com.cn/problem/P4841|P4841 [集训队作业2013]城市规划]]
+求出 $n$ 个点的简单（无重边无自环）有标号无向连通图数目。
+=== 题解 ===
+令 $\{a_n\}_{n=0}^{\infty}$ 为答案，$\{b_n\}_{n=0}^{\infty}$ 为 $n$ 个点的无向图的数目，显然 $b_n=2^{\binom{n}{2}}$，设 $1$ 号点所在连通块大小为 $k$，则有 $$
+\begin{align}
+b_n&=\sum_{k=1}^{n}\binom{n-1}{k-1}a_kb_{n-k}\\
+&=\sum_{k=0}^{n-1}\binom{n-1}{k}a_{k+1}b_{n-k-1}\\
+b_{n+1}&=\sum_{k=0}^{n}\binom{n}{k}a_{k+1}b_{n-k}
+\end{align}
+$$ 令 $c_k=a_{k+1}$，$A(x),B(x),C(x)$ 分别为 $\{a_n\}_{n=0}^{\infty},\{b_n\}_{n=0}^{\infty},\{c_n\}_{n=0}^{\infty}$ 的指数型生成函数，则 $$
+b_{n+1}=\sum_{k=0}^n\binom{n}{k}c_kb_{n-k}
+$$ 从而 $$
+B'(x)=C(x)B(x)=A'(x)B(x)
+$$ 解得 $$
+A(x)=\ln B(x)
+$$ 所以套用多项式求对数的模板即可求解 $a_n$。
+=== 代码 ===
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+#define _for(i,a,b) for(int i=(a);i<(b);++i)
+#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
+using namespace std;
+const int MAXN=1.3e5+5,Mod=1004535809;
+int n;
+int a[MAXN<<2],b[MAXN<<2];
+int quick_pow(int x,int y){
+	int ret=1;
+	for(;y;y>>=1,x=1ll*x*x%Mod)
+		if(y&1) ret=1ll*ret*x%Mod;
+	return ret;
+}
+namespace Poly{
+	const int G=3;
+	int rev[MAXN<<2],Pool[MAXN<<3],*Wn[30];
+	void init(){
+		int lg2=0,*pos=Pool,n,w;
+		while((1<<lg2)<MAXN*2)lg2++;
+		n=1<<lg2,w=quick_pow(G,(Mod-1)/(1<<lg2));
+		while(~lg2){
+		Wn[lg2]=pos,pos+=n;
+		Wn[lg2][0]=1;
+		_for(i,1,n)Wn[lg2][i]=1LL*Wn[lg2][i-1]*w%Mod;
+		w=1LL*w*w%Mod;
+		lg2--;n>>=1;
+	}
+	}
+	int build(int k){
+		int n,pos=0;
+		while((1<<pos)<=k)pos++;
+		n=1<<pos;
+		_for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
+		return n;
+	}
+	void NTT(int *f,int n,bool type){
+		_for(i,0,n)if(i<rev[i])
+		swap(f[i],f[rev[i]]);
+		int t1,t2;
+		for(int i=1,lg2=1;i<n;i<<=1,lg2++){
+			for(int j=0;j<n;j+=(i<<1)){
+				_for(k,j,j+i){
+				t1=f[k],t2=1LL*Wn[lg2][k-j]*f[k+i]%Mod;
+				f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod;
+				}
+			}
+		}
+		if(!type){
+		reverse(f+1,f+n);
+		int div=quick_pow(n,Mod-2);
+		_for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod;
+		}
+	}
+	void Mul(int *f,int _n,int *g,int _m,int xmod=0){
+		int n=build(_n+_m-2);
+		_for(i,_n,n)f[i]=0;_for(i,_m,n)g[i]=0;
+		NTT(f,n,true);NTT(g,n,true);
+		_for(i,0,n)f[i]=1LL*f[i]*g[i]%Mod;
+		NTT(f,n,false);
+		if(xmod)_for(i,xmod,n)f[i]=0;
+	}
+	void Inv(const int *f,int *g,int _n){
+		static int temp[MAXN<<2];
+		if(_n==1)return g[0]=quick_pow(f[0],Mod-2),void();
+		Inv(f,g,(_n+1)>>1);
+		int n=build((_n-1)<<1);
+		_for(i,(_n+1)>>1,n)g[i]=0;
+		_for(i,0,_n)temp[i]=f[i];_for(i,_n,n)temp[i]=0;
+		NTT(g,n,true);NTT(temp,n,true);
+		_for(i,0,n)g[i]=(2-1LL*temp[i]*g[i]%Mod)*g[i]%Mod;
+		NTT(g,n,false);
+		_for(i,_n,n)g[i]=0;
+	}
+	void Div(const int *f,int _n,const int *g,int _m,int *q,int *r){
+		static int temp[MAXN<<2];
+		if(_n<_m){
+			_rep(i,0,n)r[i]=f[i];
+			return;
+		}
+		_rep(i,0,_m)temp[i]=g[_m-i];
+		Inv(temp,q,_n-_m+1);
+		_rep(i,0,_n)temp[i]=f[_n-i];
+		Mul(q,_n-_m+1,temp,_n+1,_n-_m+1);
+		for(int i=0,j=_n-_m;i<j;i++,j--)swap(q[i],q[j]);
+		int __m=min(_n-_m+1,_m);
+		_for(i,0,_m)r[i]=g[i];_for(i,0,__m)temp[i]=q[i];
+		Mul(r,_m,temp,__m,_m);
+		_for(i,0,_m)r[i]=(f[i]+Mod-r[i])%Mod;
+	}
+	void Ln(const int *f,int *g,int _n){
+		static int temp[MAXN<<2];
+		Inv(f,g,_n);
+		_for(i,1,_n)temp[i-1]=1LL*f[i]*i%Mod;
+		temp[_n-1]=0;
+		Mul(g,_n,temp,_n-1,_n);
+		for(int i=_n-1;i;i--)g[i]=1LL*g[i-1]*quick_pow(i,Mod-2)%Mod;
+		g[0]=0;
+	}
+	void Exp(const int *f,int *g,int _n){
+		static int temp[MAXN<<2];
+		if(_n==1)return g[0]=1,void();
+		Exp(f,g,(_n+1)>>1);
+		_for(i,(_n+1)>>1,_n)g[i]=0;
+		Ln(g,temp,_n);
+		temp[0]=(1+f[0]-temp[0])%Mod;
+		_for(i,1,_n)temp[i]=(f[i]-temp[i])%Mod;
+		Mul(g,(_n+1)>>1,temp,_n,_n);
+	}
+	void Pow(const int *f,int *g,int _n,int k1,int k2){
+		static int temp[MAXN<<2];
+		int pos=0,posv;
+		while(!f[pos]&&pos<_n)pos++;
+		if(1LL*pos*k2>=_n){
+			_for(i,0,_n)g[i]=0;
+			return;
+		}
+		posv=quick_pow(f[pos],Mod-2);
+		_for(i,pos,_n)g[i-pos]=1LL*f[i]*posv%Mod;
+		_for(i,_n-pos,_n)g[i]=0;
+		Ln(g,temp,_n);
+		_for(i,0,_n)temp[i]=1LL*temp[i]*k1%Mod;
+		Exp(temp,g,_n);
+		pos=pos*k2,posv=quick_pow(posv,1LL*k2*(Mod-2)%(Mod-1));
+		for(int i=_n-1;i>=pos;i--)g[i]=1LL*g[i-pos]*posv%Mod;
+		_for(i,0,pos)g[i]=0;
+	}
+}
+int fact[MAXN<<2];
+int invfact[MAXN<<2];
+int main(){
+	scanf("%d",&n);
+	b[0]=1;
+	fact[0]=1;
+	for(int i=1;i<=n;i++){
+		fact[i]=1ll*fact[i-1]*i%Mod;
+	}
+	invfact[n]=quick_pow(fact[n],Mod-2);
+	for(int i=n;i>=1;i--)
+		invfact[i-1]=1ll*invfact[i]*i%Mod;
+	for(int i=0;i<=n;i++)
+		b[i]=1ll*quick_pow(2,1ll*i*(i-1)/2%(Mod-1))*invfact[i]%Mod;
+	Poly::init();
+	Poly::Ln(b,a,n+1);
+	printf("%d",1ll*a[n]*fact[n]%Mod);
+	return 0;
+}
+</code>
+</hidden>
+=== 拓展 ===
+令 $a_n$ 表示在一个 n-集合上完成某个任务的方法数，$a_0=0$。对于 $n\ge 1$，令 $b_n$ 表示将集合 $[n]$ 划分成任意的非空子集，然后在这些非空子集上完成前面任务的方法数，$b_0=1$。设 $\{a_n\}_{n=0}^{\infty}$ 和 $\{b_n\}_{n=0}^{\infty}$ 的指数型生成函数分别为 $f(x)$ 和 $g(x)$，则对任意固定的正整数 $i$，将 $[n]$ 划分成 $i$ 个非空子集时，所对应的方法数的指数型生成函数为 $f^i(x)/i!$，且有 $$
+g(x)=e^{f(x)}.
+$$
+==== 例 5 ====
+=== 题意 ===
+[[https://www.luogu.com.cn/problem/CF438E|CF438E The Child and Binary Tree]]
+给定一个含有 $n$ 个互异正整数的数列 $c_1,c_2,\cdots,c_n$，如果一棵带点权的有根二叉树满足其所有顶点的权值都在集合 $\{c_1,c_2,\cdots,c_n\}$ 中，则称之为好树，一棵带点权的树的权值是其所有顶点权值的总和。给出一个正整数 $m$，对任意的 $s,1\leq s\leq m$，计算出权值为 $s$ 的好树个数。
+=== 题解 ===
+设 $f_i$ 表示点权和为 $i$ 的符合条件的二叉树的个数，$g_i$ 表示权值 $i$ 是否在 $c_i$ 中。 $$
+f_0=1\\
+f_n=\sum_{i=1}^ng_i\sum_{j=1}^{n-i}f_jf_{n-i-j}~~(n>0)
+$$ 这个式子的意思是枚举根结点的权值 $i$，然后枚举根结点左右子树的权值，容易发现这是三个多项式的卷积。用 $F(x),G(x)$ 分别表示数列 $\{f_n\}_{n=0}^{\infty},\{g_n\}_{n=0}^{\infty}$ 的普通生成函数。则有 $$
+F(x)=G(x)F^2(x)+1
+$$ 解得 $$
+F(x)=\frac{2}{1+\sqrt{1-4G(x)}}
+$$ 所以套用多项式开根+求逆即可
+=== 代码 ===
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+#define _for(i,a,b) for(int i=(a);i<(b);++i)
+#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
+using namespace std;
+const int MAXN=1e5+5,Mod=998244353;
+int n;
+int g[MAXN<<2],f[MAXN<<2];
+int h[MAXN<<2];
+int quick_pow(int x,int y){
+	int ret=1;
+	for(;y;y>>=1,x=1ll*x*x%Mod)
+		if(y&1) ret=1ll*ret*x%Mod;
+	return ret;
+}
+unordered_map<int,int>H;
+int bsgs(int a,int b){
+	H.clear();
+	int m=sqrt(Mod)+1,t=b,base;
+	for(int i=1;i<=m;i++){
+		t=1ll*t*a%Mod;
+		H[t]=i;
+	}
+	t=1,base=quick_pow(a,m);
+	for(int i=1;i<=m;i++){
+		t=1ll*t*base%Mod;
+		if(H[t]) return m*i-H[t];
+	}
+	return -1;
+}
+namespace Poly{
+	const int G=3;
+	int rev[MAXN<<2],Pool[MAXN<<3],*Wn[30];
+	void init(){
+		int lg2=0,*pos=Pool,n,w;
+		while((1<<lg2)<MAXN*2)lg2++;
+		n=1<<lg2,w=quick_pow(G,(Mod-1)/(1<<lg2));
+		while(~lg2){
+		Wn[lg2]=pos,pos+=n;
+		Wn[lg2][0]=1;
+		_for(i,1,n)Wn[lg2][i]=1LL*Wn[lg2][i-1]*w%Mod;
+		w=1LL*w*w%Mod;
+		lg2--;n>>=1;
+	}
+	}
+	int build(int k){
+		int n,pos=0;
+		while((1<<pos)<=k)pos++;
+		n=1<<pos;
+		_for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
+		return n;
+	}
+	void NTT(int *f,int n,bool type){
+		_for(i,0,n)if(i<rev[i])
+		swap(f[i],f[rev[i]]);
+		int t1,t2;
+		for(int i=1,lg2=1;i<n;i<<=1,lg2++){
+			for(int j=0;j<n;j+=(i<<1)){
+				_for(k,j,j+i){
+				t1=f[k],t2=1LL*Wn[lg2][k-j]*f[k+i]%Mod;
+				f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod;
+				}
+			}
+		}
+		if(!type){
+		reverse(f+1,f+n);
+		int div=quick_pow(n,Mod-2);
+		_for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod;
+		}
+	}
+	void Mul(int *f,int _n,int *g,int _m,int xmod=0){
+		int n=build(_n+_m-2);
+		_for(i,_n,n)f[i]=0;_for(i,_m,n)g[i]=0;
+		NTT(f,n,true);NTT(g,n,true);
+		_for(i,0,n)f[i]=1LL*f[i]*g[i]%Mod;
+		NTT(f,n,false);
+		if(xmod)_for(i,xmod,n)f[i]=0;
+	}
+	void Inv(const int *f,int *g,int _n){
+		static int temp[MAXN<<2];
+		if(_n==1)return g[0]=quick_pow(f[0],Mod-2),void();
+		Inv(f,g,(_n+1)>>1);
+		int n=build((_n-1)<<1);
+		_for(i,(_n+1)>>1,n)g[i]=0;
+		_for(i,0,_n)temp[i]=f[i];_for(i,_n,n)temp[i]=0;
+		NTT(g,n,true);NTT(temp,n,true);
+		_for(i,0,n)g[i]=(2-1LL*temp[i]*g[i]%Mod)*g[i]%Mod;
+		NTT(g,n,false);
+		_for(i,_n,n)g[i]=0;
+	}
+	void Div(const int *f,int _n,const int *g,int _m,int *q,int *r){
+		static int temp[MAXN<<2];
+		if(_n<_m){
+			_rep(i,0,n)r[i]=f[i];
+			return;
+		}
+		_rep(i,0,_m)temp[i]=g[_m-i];
+		Inv(temp,q,_n-_m+1);
+		_rep(i,0,_n)temp[i]=f[_n-i];
+		Mul(q,_n-_m+1,temp,_n+1,_n-_m+1);
+		for(int i=0,j=_n-_m;i<j;i++,j--)swap(q[i],q[j]);
+		int __m=min(_n-_m+1,_m);
+		_for(i,0,_m)r[i]=g[i];_for(i,0,__m)temp[i]=q[i];
+		Mul(r,_m,temp,__m,_m);
+		_for(i,0,_m)r[i]=(f[i]+Mod-r[i])%Mod;
+	}
+	void Ln(const int *f,int *g,int _n){
+		static int temp[MAXN<<2];
+		Inv(f,g,_n);
+		_for(i,1,_n)temp[i-1]=1LL*f[i]*i%Mod;
+		temp[_n-1]=0;
+		Mul(g,_n,temp,_n-1,_n);
+		for(int i=_n-1;i;i--)g[i]=1LL*g[i-1]*quick_pow(i,Mod-2)%Mod;
+		g[0]=0;
+	}
+	void Exp(const int *f,int *g,int _n){
+		static int temp[MAXN<<2];
+		if(_n==1)return g[0]=1,void();
+		Exp(f,g,(_n+1)>>1);
+		_for(i,(_n+1)>>1,_n)g[i]=0;
+		Ln(g,temp,_n);
+		temp[0]=(1+f[0]-temp[0])%Mod;
+		_for(i,1,_n)temp[i]=(f[i]-temp[i])%Mod;
+		Mul(g,(_n+1)>>1,temp,_n,_n);
+	}
+	void Pow(const int *f,int *g,int _n,int k1,int k2){
+		static int temp[MAXN<<2];
+		int pos=0,posv;
+		while(!f[pos]&&pos<_n)pos++;
+		if(1LL*pos*k2>=_n){
+			_for(i,0,_n)g[i]=0;
+			return;
+		}
+		posv=quick_pow(f[pos],Mod-2);
+		_for(i,pos,_n)g[i-pos]=1LL*f[i]*posv%Mod;
+		_for(i,_n-pos,_n)g[i]=0;
+		Ln(g,temp,_n);
+		_for(i,0,_n)temp[i]=1LL*temp[i]*k1%Mod;
+		Exp(temp,g,_n);
+		pos=pos*k2,posv=quick_pow(posv,1LL*k2*(Mod-2)%(Mod-1));
+		for(int i=_n-1;i>=pos;i--)g[i]=1LL*g[i-pos]*posv%Mod;
+		_for(i,0,pos)g[i]=0;
+	}
+	void Sqrt(const int *f,int *g,int _n){
+		static int temp1[MAXN<<2],temp2[MAXN<<2];
+		if(_n==1) return g[0]=quick_pow(G,bsgs(3,f[0])/2),void();
+		Sqrt(f,g,(_n+1)>>1);
+		_for(i,(_n+1)>>1,_n) g[i]=0;
+		_for(i,0,_n) temp1[i]=f[i];
+		Inv(g,temp2,_n);
+		Mul(temp1,_n,temp2,_n);
+		int div2=quick_pow(2,Mod-2);
+		_for(i,0,_n) g[i]=1LL*(g[i]+temp1[i])*div2%Mod;
+	}
+}
+int main(){
+	int n,m;
+	scanf("%d%d",&n,&m);
+	for(int i=1;i<=n;i++){
+		int x;
+		scanf("%d",&x);
+		g[x]=(Mod-4)%Mod;
+	}
+	g[0]=1;
+	Poly::init();
+	Poly::Sqrt(g,h,m+1);
+	h[0]=(h[0]+1)%Mod;
+	Poly::Inv(h,f,m+1);
+	for(int i=1;i<=m;i++) printf("%d\n",1ll*f[i]*2%Mod);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具