CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:生成函数_1 [2020/08/13 20:20]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:生成函数_1 [2020/08/21 20:48] (当前版本)
jxm2001
@@ 行 278: / 行 278: @@
 ==== 例题五 ====
+[[https://www.luogu.com.cn/problem/P4451|洛谷p4451]]
+=== 题意 ===
+求 $\sum\prod_{i=1}^mF_{a_i}$，其中
+  - $m\gt 0$
+  - $a_i\gt 0$
+  - $sum_{i=1}^m a_i=n$
+  - $F$ 为斐波那契数列，且 $F_0=0,F_1=1$
+答案对 $10^9+7$ 取模。
+=== 题解 ===
+先考虑 $m=1$ 的生成函数，有 $G(x)=\sum_{i=0}^n F_ix^i$。
+于是答案的生成函数为 $H(x)=\sum_{m=1}^{\infty} G^m(x)=\cfrac {G(x)}{1-G(x)}$，接下来考虑求解 $G(x)$。
+有 $G(x)-xG(x)-x^2G(x)=F_0+F_1x-F_0=x$，于是 $G(x)=\cfrac x{1+x+x^2}$，代入可得 $H(x)=\cfrac {x}{1-2x-x^2}$。
+于是有 $(1-2x-x^2)H(x)=x$，于是 $h_n=2h_{n-1}+h_{n-2}+[n==1]$。
+通过特征根求解得 $h_n=\cfrac {\sqrt 2}4(1+\sqrt 2)^n-\cfrac {\sqrt 2}4(1-\sqrt 2)^n$。
+<hidden 查看代码>
+<code cpp>
+const int MAXL=1e4+5,Mod=1e9+7,sqrt2=59713600,inv4=250000002;
+int quick_pow(int a,int b){
+	int ans=1;
+	while(b){
+		if(b&1)ans=1LL*ans*a%Mod;
+		a=1LL*a*a%Mod;
+		b>>=1;
+	}
+	return ans;
+}
+char buf[MAXL];
+int main()
+{
+	scanf("%s",buf);
+	int n=0,len=strlen(buf);
+	_for(i,0,len)
+	n=(10LL*n+buf[i]-'0')%(Mod-1);
+	int ans=1LL*(quick_pow(1+sqrt2,n)-quick_pow(1-sqrt2,n))*sqrt2%Mod*inv4%Mod;
+	enter((ans+Mod)%Mod);
+	return 0;
+}
+</code>
+</hidden>
+==== 例题六 ====
 [[https://ac.nowcoder.com/acm/contest/5670/C|牛客暑期多校(第五场) C 题]]
@@ 行 365: / 行 418: @@
 </hidden>
-==== 例题六 ====
+==== 例题七 ====
 [[https://www.luogu.com.cn/problem/CF923E|CF923E]]
@@ 行 381: / 行 434: @@
 考虑构造生成函数优化递推过程
-$$F_k(x)=\sum_{i=0}^n f_{k,i}$$
+$$
+\begin{equation}\begin{split}
+F_k(x)&=\sum_{i=0}^n f_{k,i}x^i\\
+&=\sum_{i=0}^n \sum_{j=i}^{n} \frac {f_{k-1,j}}{j+1}x^i\\
+&=\sum_{j=0}^n \frac {f_{k-1,j}}{j+1}\sum_{i=0}^j x^i\\
+&=\frac 1{x-1}\sum_{j=0}^n f_{k-1,j}\frac {x^{j+1}-1}{j+1}\\
+&=\frac 1{x-1}\sum_{j=0}^n f_{k-1,j}\int_1^x t^j \mathrm{d}t\\
+&=\frac 1{x-1}\int_1^x F_{k-1}(t)\mathrm{d}t
+\end{split}\end{equation}
+$$
+由于 $\frac 1{x-1}$ 和 $\int_1^x$ 不利于更进一步处理，于是考虑构造辅助函数 $G_k(x)=F_k(x+1)$
+$$
+\begin{equation}\begin{split}
+G_k(x)&=\frac 1x\int_1^{x+1} F_{k-1}(t)\mathrm{d}t\\
+&=\frac 1x\int_0^{x} F_{k-1}(t+1)\mathrm{d}t\\
+&=\frac 1x\int_0^{x} G_{k-1}(t)\mathrm{d}t\\
+&=\sum_{i=0}^n \frac {g_{k-1,i}}{i+1}x^i
+\end{split}\end{equation}
+$$
+于是有 $g_{k,i}=\frac {g_{k-1,i}}{i+1}$，所以 $g_{m,i}=\frac {g_{0,i}}{(i+1)^m}$。
+接下来考虑 $g_{k,i}$ 与 $f_{k,i}$ 之间的转化，简记 $g_i=g_{k,i},f_i=f_{k,i}$，于是有
+$$g_i=\sum_{j=i}^n {j\choose i}f_j=\sum_{j=i}^n \frac{j!}{i!(j-i)!}f_j=\frac 1{i!}\sum_{j=0}^{n-i}\frac {(i+j)!f_{i+j}}{j!}$$
+记 $a_i=\frac 1{i!},b_i=(n-i)!f_{n-i}$，于是有 $g_i=\sum_{j=0}^{n-i}a_ib_{n-i-j}$。
+直接 $\text{NTT}$ 可以由 $F_0(x)$ 求出 $G_0(x)$ 进而求出 $G_m(x)$。考虑对 $\sum_{i=0}^n \frac 1{i!}x^i$ 求逆再与 $G_m(x)$ 卷积即可求出 $F_m(x)$，总时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,Mod=998244353;
+int quick_pow(int a,int b){
+	int ans=1;
+	while(b){
+		if(b&1)
+		ans=1LL*ans*a%Mod;
+		a=1LL*a*a%Mod;
+		b>>=1;
+	}
+	return ans;
+}
+namespace Poly{
+	const int G=3;
+	int rev[MAXN<<2],Wn[30][2];
+	void init(){
+		int m=Mod-1,lg2=0;
+		while(m%2==0)m>>=1,lg2++;
+		Wn[lg2][1]=quick_pow(G,m);
+		Wn[lg2][0]=quick_pow(Wn[lg2][1],Mod-2);
+		while(lg2){
+			m<<=1,lg2--;
+			Wn[lg2][0]=1LL*Wn[lg2+1][0]*Wn[lg2+1][0]%Mod;
+			Wn[lg2][1]=1LL*Wn[lg2+1][1]*Wn[lg2+1][1]%Mod;
+		}
+	}
+	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=0;i<n;i<<=1,lg2++){
+			int w=Wn[lg2+1][type];
+			for(int j=0;j<n;j+=(i<<1)){
+				int cur=1;
+				_for(k,j,j+i){
+					t1=f[k],t2=1LL*cur*f[k+i]%Mod;
+					f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod;
+					cur=1LL*cur*w%Mod;
+				}
+			}
+		}
+		if(!type){
+			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;
+	}
+}
+int a[MAXN<<2],b[MAXN<<2],c[MAXN<<2],frac[MAXN],invfrac[MAXN];
+int main()
+{
+	Poly::init();
+	frac[0]=1;
+	_for(i,1,MAXN)frac[i]=1LL*frac[i-1]*i%Mod;
+	invfrac[MAXN-1]=quick_pow(frac[MAXN-1],Mod-2);
+	for(int i=MAXN-1;i;i--)invfrac[i-1]=1LL*invfrac[i]*i%Mod;
+	int n=read_int(),m=read_LL()%(Mod-1)*(Mod-2)%(Mod-1);
+	_rep(i,0,n)
+	a[n-i]=1LL*read_int()*frac[i]%Mod;
+	_rep(i,0,n)
+	b[i]=invfrac[i];
+	Poly::Mul(a,n+1,b,n+1);
+	_rep(i,0,n)
+	a[i]=1LL*a[i]*quick_pow(n-i+1,m)%Mod,b[i]=invfrac[i];
+	Poly::Inv(b,c,n+1);
+	Poly::Mul(a,n+1,c,n+1);
+	_rep(i,0,n)a[i]=1LL*a[i]*invfrac[n-i]%Mod;
+	reverse(a,a+n+1);
+	_rep(i,0,n)space(a[i]);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具