有 \(n\) 个点 , 第 \(i\) 个点上有 \(d_i\) 个插孔 ,每个插孔都是独一无二的,每条边可以连接任意两个点上的两个插孔,问有多少种不同的连边方法可以连出一棵树。
\(1\leq n\leq 2\cdot 10^5,1\leq d_i<998244353\)
首先,无根树,考虑 prufer 序列 .
考虑确定每个点的度数 \(a_i\) ,方案书是
\[(n-2)!\sum\limits_{a_1+a_2+\cdots+a_{n-1}=2n-2}\prod \frac{d_i^{\underline{a_i}}}{(a_i-1)!} \]这个式子看上去就非常不可做,考虑引入生成函数 .
\[\begin{align} f(x)&=\sum_{i=1}^{d_x} \frac{d_x^{\underline{i}}}{(i-1)!}x^i \end{align} \]答案如下,看上去很有前途的样子 .
\[(n-2)![2n-2]\prod f(i) \]考虑化简上面这个式子,
\[\begin{align} f(x)&=\sum_{i=1}^{d_x} \frac{d_x^{\underline{i}}}{(i-1)!}x^i\\ &=\sum_{i=1}^{d_x}\frac{d_x!}{(i-1)!(d_x-i)!}x^i\\ \end{align} \]发现这个差一点就可以凑成组合数了 . 此时,考虑把下表同意减一 . 此时,从 \(x^0\) 到 \(x^{d_x-1}\) 才符合比较标准的多项式 . 于是有
\[\begin{align} f(x)&=\sum\limits_{i=0}^{d_x-1}\frac{d_x^{\underline{i+1}}}{i!} x^i\\ &=\sum\limits_{i=0}^{d_x-1}\frac{d_x(d_x-1)^{\underline{i-1}}}{i!}x^i\\ &=d_x\sum\limits_{i=0}^{d_x-1}\frac{(d_x-1)!}{i!(d_x-i-1)!}x^i\\ &=d_x\sum\limits_{i=0}^{d_x-1}\dbinom{d_x-1}{i}x^i\\ &=d_x(x+1)^{d_x-1} \end{align} \]此时,就得到了一个非常非常棒的式子 . 接着化简答案 .
\[\begin{align} ans&=(n-2)![n-2]\prod{f(x)}\\ &=(n-2)![n-2]\prod{d_x(x+1)^{d_x-1}}\\ &=(n-2)![n-2](x+1)^{\sum d_x-1}\prod{d_x}\\ &=(n-2)!\dbinom{\sum{d_x-1}}{n-2}\prod{d_x}\\ &=(n-2)!(\sum d_x-1)!\prod d_x \end{align} \]最后划得一个很简短的式子,真的很神奇 .
用最后一个式子和倒数第二个式子都能算出答案 ,我用的是倒数第二个 .
感觉好奇妙 ( 然而没有做出来 ) ,可能是我第一次想推柿子的题目罢 .
时间复杂度 : \(O(n\log d)\)
空间复杂度 : \(O(n)\)
#include<bits/stdc++.h> using namespace std; const int mod=998244353; int n; int d[200010]; inline int ksm(int x,int k){ if(k==0)return 1; int res=ksm(x,k>>1); res=1ll*res*res%mod; if(k&1)res=1ll*res*x%mod; return res; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>n; for(int i=0;i<n;i++)cin>>d[i]; int ans=1; for(int i=1;i<=n-2;i++)ans=1ll*ans*i%mod; for(int i=0;i<n;i++)ans=1ll*ans*d[i]%mod; int sum=0; for(int i=0;i<n;i++)sum=(d[i]-1+sum)%mod; for(int i=0;i<n-2;i++)ans=1ll*(sum-i+mod)%mod*ans%mod; for(int i=1;i<=n-2;i++)ans=1ll*ans*ksm(i,mod-2)%mod; cout<<ans<<endl; return 0; } /*inline? ll or int? size? min max?*/