CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:生成函数_2 [2020/08/13 17:21]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:生成函数_2 [2020/08/21 18:02] (当前版本)
jxm2001
@@ 行 11: / 行 11: @@
 $$F(x)G(x)=\sum_{n=0}^{\infty}\sum_{i=0}^n a_ib_{n-i}\frac {x^n}{i!(n-i)!}=\sum_{n=0}^{\infty}\sum_{i=0}^n {n\choose i}a_ib_{n-i}\frac {x^n}{n!}$$
-$$\sum_{n=0}^{\infty}k^n\frac {x^n}{n!}=e^{kx}$$
+$$\sum_{n=0}^{\infty}k^n\frac {x^n}{n!}=e^{kx},\sum_{n=0}^{\infty}n^{\underline k}\frac {x^n}{n!}=x^ke^x$$
-$$\sum_{n=0}^{\infty}n^{\underline k}\frac {x^n}{n!}=x^ke^x$$
 ===== 算法例题 =====
@@ 行 163: / 行 161: @@
 [[https://www.luogu.com.cn/problem/P4841|洛谷p4841]]
-考虑对结果的解释，$e^x-1=\sum_{n=1}^{\infty}a_n\frac {x^n}{n!}(a_n=1)$ 可以理解为将所有 $n$ 个元素化为为一个集合的方案数 $a_n$ 的 $\text{EGF}$。
+考虑对结果的解释，$A(x)=e^x-1=\sum_{n=1}^{\infty}a_n\frac {x^n}{n!}(a_n=1)$ 可以理解为将所有 $n$ 个元素化为为一个集合的方案数 $a_n$ 的 $\text{EGF}$。
 $\exp (e^x-1)=\sum_{i=0}^{\infty} \cfrac {A^i(x)}{i!}$ 式子中 $\sum_{i=0}^{\infty}$ 可以理解为枚举最终划分的集合数 $i$。
@@ 行 315: / 行 313: @@
 即 $F_k(x)=\exp xF_{k-1}(x)$，边界条件 $F_1(x)=x$，时间复杂度 $O(nk\log n)$。
+==== 例题四 ====
+[[https://www.luogu.com.cn/problem/CF891E|CF891E]]
+=== 题意 ===
+给定 $n$ 个数 $a_1,a_2\cdots a_n$。
+接下来 $k$ 次操作。每次随机选取其中一个数 $x\in [1,n]$，将 $a_x$ 减一，同时得到 $\prod_{i\neq x}a_i$ 的分数。
+问最终得分的期望值，答案对 $10^9+7$ 取模。
+=== 题解 ===
+设势能函数为 $\prod_{i=1}^n a_i$，发现每次操作得分恰好等于势能函数减少量。
+不妨设 $c_i$ 表示 $k$ 次操作中 $x=i$ 的次数，则最终得分为 $\prod_{i=1}^n a_i-\prod_{i=1}^n (a_i-c_i)$。
+考虑计算每个方案的 $\prod_{i=1}^n (a_i-c_i)$ 的和，最后除以总方案数 $n^k$。
+对每种方案 $(c_1,c_2\cdots c_n)$，显然有 $\frac {k!}{c_1!c_2!\cdots c_n!}$ 个，发现这与 $\text{EGF}$ 卷积相似。
+构造生成函数 $F_i(x)=\sum_{j=0}^{\infty} (a_i-j)\frac {x^j}{j!}=\sum_{j=0}^{\infty} a_i\frac {x^j}{j!}-j\frac {x^j}{j!}=(a_i-x)e^x$，$F(x)=\prod_{i=1}^n F_i(x)=e^{nx}\prod_{i=1}^n (a_i-x)$。
+不难发现所有方案对应答案为 $[\frac {x^k}{k!}]F(x)$。
+考虑分治 $\text{FFT}$ 处理 $\prod_{i=1}^n (a_i-x)$，假设计算结果为 $b_0+b_1x+b_2x^2+\cdots +b_nx^n$。
+$$F(x)=\left(\sum_{i=0}^{\infty}\frac {n^ix^i}{i!}\right)\left(\sum_{i=0}^n b_ix^i\right)=\sum_{i=0}^{\infty} x^i\sum_{j=0}^i \frac{n^{i-j}b_j}{(i-j)!}=\sum_{i=0}^{\infty} \frac{x^i}{i!}\sum_{j=0}^{\min (i,n)} n^{i-j}i^{\underline j}b_j$$
+于是 $[\frac {x^k}{k!}]F(x)=n^k\sum_{i=0}^{\min (k,n)}\cfrac {k^{\underline i}b_i}{n^i}$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,mod=1e9+7,m=sqrt(mod)+0.5;
+const long double pi=acos(-1.0);
+int quick_pow(int x,int k){
+	int ans=1;
+	while(k){
+		if(k&1)ans=1LL*ans*x%mod;
+		x=1LL*x*x%mod;
+		k>>=1;
+	}
+	return ans;
+}
+struct complex{
+	long double x,y;
+	complex(long double x=0.0,long double y=0.0):x(x),y(y){}
+	complex operator + (const complex &b){
+		return complex(x+b.x,y+b.y);
+	}
+	complex operator - (const complex &b){
+		return complex(x-b.x,y-b.y);
+	}
+	complex operator * (const complex &b){
+		return complex(x*b.x-y*b.y,x*b.y+y*b.x);
+	}
+};
+int rev[MAXN<<2];
+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 FFT(complex *f,int n,int type){
+	_for(i,0,n)if(i<rev[i])
+	swap(f[i],f[rev[i]]);
+	complex t1,t2;
+	for(int i=1;i<n;i<<=1){
+		complex w(cos(pi/i),type*sin(pi/i));
+		for(int j=0;j<n;j+=(i<<1)){
+			complex cur(1.0,0.0);
+			_for(k,j,j+i){
+				t1=f[k],t2=cur*f[k+i];
+				f[k]=t1+t2,f[k+i]=t1-t2;
+				cur=cur*w;
+			}
+		}
+	}
+	if(type==-1)_for(i,0,n)
+	f[i].x/=n,f[i].y/=n;
+}
+void FFT2(complex *f1,complex *f2,int n){
+	FFT(f1,n,1);
+	f2[0].x=f1[0].x,f2[0].y=-f1[0].y;
+	_for(i,1,n)
+	f2[i].x=f1[n-i].x,f2[i].y=-f1[n-i].y;
+	complex t1,t2;
+	_for(i,0,n){
+		t1=f1[i],t2=f2[i];
+		f1[i]=complex((t1.x+t2.x)*0.5,(t1.y+t2.y)*0.5);
+		f2[i]=complex((t1.y-t2.y)*0.5,(t2.x-t1.x)*0.5);
+	}
+}
+LL getv(double x){
+	if(x>-0.5)return (LL)(x+0.5);
+	return (LL)(x-0.5);
+}
+complex f1[MAXN<<2],f2[MAXN<<2],g1[MAXN<<2],g2[MAXN<<2],temp[2][MAXN<<2];
+void MTT(int *f,int n1,int *g,int n2){
+	int n=build(n1+n2);
+	_rep(i,0,n1)f1[i].x=f[i]/m,f1[i].y=f[i]%m;_for(i,n1+1,n)f1[i].x=f1[i].y=0.0;
+	_rep(i,0,n2)g1[i].x=g[i]/m,g1[i].y=g[i]%m;_for(i,n2+1,n)g1[i].x=g1[i].y=0.0;
+	FFT2(f1,f2,n);FFT2(g1,g2,n);
+	complex I(0.0,1.0);
+	_for(i,0,n){
+		temp[0][i]=f1[i]*g1[i]+I*f2[i]*g1[i];
+		temp[1][i]=f1[i]*g2[i]+I*f2[i]*g2[i];
+	}
+	FFT(temp[0],n,-1);FFT(temp[1],n,-1);
+	LL a,b,c;
+	_rep(i,0,n1+n2){
+		a=getv(temp[0][i].x);b=getv(temp[0][i].y+temp[1][i].x);c=getv(temp[1][i].y);
+		f[i]=((a%mod*m%mod*m%mod+b%mod*m%mod+c%mod)%mod+mod)%mod;
+	}
+}
+int a[MAXN],b[MAXN<<3],c[MAXN];
+void solve(int *f,int lef,int rig){
+	int mid=lef+rig>>1;
+	if(lef==rig){
+		f[0]=a[mid],f[1]=-1;
+		return;
+	}
+	solve(f,lef,mid);solve(f+mid-lef+2,mid+1,rig);
+	MTT(f,mid-lef+1,f+mid-lef+2,rig-mid);
+}
+int main()
+{
+	int n=read_int(),k=read_int(),ans=1;
+	_rep(i,1,n)a[i]=read_int(),ans=1LL*ans*a[i]%mod;
+	solve(b,1,n);
+	int _n=min(n,k),divn=quick_pow(n,mod-2);
+	c[0]=1;
+	_for(i,0,_n)c[i+1]=1LL*c[i]*(k-i)%mod*divn%mod;
+	_rep(i,0,_n)ans=(ans-1LL*b[i]*c[i])%mod;
+	enter((ans+mod)%mod);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具