AT_arc106_f

记录一下自己第一次用 GF 推式子。

翻译一下就是这颗树每个点的度数 $m\le a_u$，并且要额外乘上 $a_u^{\underline m}$ 的权值，求所有树的权值之和。

由于是 $deg_u$ 的限制，所以考虑 prufer 序列。考虑枚举每个点的度数为 $deg_u$，变成 prufer 序列，则有 $ans=(n-2)!\sum\limits_{\sum deg_i=n\times2-2}\prod\limits_i\frac{a_i^{\underline{dep_i}}}{(deg_i-1)!}=(n-2)!\sum\limits_{\sum deg_i=n\times2-2}\prod\limits_i\binom{a_i}{deg_i}deg_i$。可以背包 dp $O(n^2)$ 解决。

但是 $O(n^2)$ 显然不够，不过背包很难优化。此时想到 GF（但是我一道 GF 都没做过是怎么想到的？？？）。设 $F_i(x)$ 为第 $i$ 个点对应的 GF，则有：

$F_i(x)=\sum_{j}\binom{a_i}{j}jx^j$

$=\sum_j\frac{a_i!}{(a_i-j)!j!}jx^j$

$=\sum_j\frac{a_i!}{(a_i-j)!(j-1)!}x^j$

$=a_i\sum_j\frac{(a_i-1)!}{(a_i-j)!(j-1)!}x^j$

$=a_i\sum_j\binom{a_i-1}{j-1}x^j$

注意到此时 $j-1$ 比较不好看，于是我们默认给每个点分配一个度数（事实上这也是必须要的），则限制变成 $\sum deg_i=n-2$，上式变成 $a_i\sum_j\binom{a_i-1}{j}x^j$。

要求的即为 $[x^{n-2}]\prod_iF_i(x)$。

将 $F_i(x)$ 转为封闭形式即为 $F_i(x)=m(1+x)^{m-1}$。

则 $\prod_iF_i(x)=(\prod a_i)(1+x)^{\sum a_i-n}$。

再转回形式幂级数为 $\prod_iF_i(x)=(\prod a_i)\sum\limits_{j}\binom{\sum a_i-n}{j}$。

则 $ans=(n-2)!(\prod a_i)\binom{\sum a_i-n}{n-2}$。$O(n)$ 解决。

code：

int n,m,a[N];
il int qpow(int x,int y){
	int ret=1;
	while(y){
		if(y&1){
			ret=1ll*ret*x%mod;
		}
		x=1ll*x*x%mod,y>>=1;
	}
	return ret;
}
il int binom(ll x,int y){
	if(x<0||y<0||x<y){
		return 0;
	}
	int a=1,b=1;
	for(ll i=x;i>=x-y+1;i--){
		a=1ll*a*(i%mod)%mod;
	}
	rep(i,1,y){
		b=1ll*b*i%mod;
	}
	return 1ll*a*qpow(b,mod-2)%mod;
}
void Yorushika(){
	read(n);
	int x=1;ll y=-n;
	rep(i,1,n){
		read(a[i]);
		x=1ll*x*a[i]%mod;
		y+=a[i];
	}
	int ans=1ll*x*binom(y,n-2)%mod;
	rep(i,1,n-2){
		ans=1ll*ans*i%mod;
	}
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}