题目
分析
套上prufer序列，
对于一颗n个节点度数分别为(d_1、d_2...d_n)方案数为(dfrac{(n-2)!}{(d_1-1)!(d_2-1)!......(d_n-1)!})
所以答案为
[sum_{d_1+d_2+...+d_n=2n-2}dfrac{(n-2)!}{(d_1-1)!(d_2-1)!...(d_n-1)!}w_1^{d_1}w_2^{d_2}...w_n^{d_n}d_1d_2...d_n
]
使(d_i-1)
[w_1w_2...w_n(n-2)!sum_{d_1+d_2+...+d_n=n-2}dfrac{1}{d_1!d_2!...d_n!}w_1^{d_1}w_2^{d_2}...w_n^{d_n}(d_1+1)(d_2+1)...(d_n+1)
]
考虑处理
[sum_{d_1+d_2+...+d_n=n-2}dfrac{1}{d_1!d_2!...d_n!}w_1^{d_1}w_2^{d_2}...w_n^{d_n}(d_1+1)(d_2+1)...(d_n+1)
]
对于多项式((d_1+1)(d_2+1)...(d_n+1))，拆开后变成一个个形如(d_1d_2...d_k)的项
我们考虑(d_1d_2d_3)
[sum_{d_1+d_2+...+d_n=n-2}dfrac{1}{d_1!d_2!...d_n!}w_1^{d_1}w_2^{d_2}...w_n^{d_n}d_1d_2d_3
]
[w_1w_2w_3sum_{d_1+d_2+...+d_n=n-2-3}dfrac{1}{d_1!d_2!...d_n!}w_1^{d_1}w_2^{d_2}...w_n^{d_n}
]
[sum_{k=1}^{n-2}(sum_{1leq p_1<p_2<...<p_k leq n}Pi_{i=1}^{k}w_{p_i})dfrac{(sum_{i=1}^{n}w_i)^{n-2-k}}{(n-2-k)!}
]
//后面的内容我还不太理解，只能大概讲讲。如果讲错了，请大佬指出一下错误
现在解释一下最后一条式子
根据指数型生成函数的定义
[G(x)=sum g_idfrac{x^i}{i!}=dfrac{x^1}{1!}+dfrac{x^2}{2!}+dfrac{x^3}{3!}+..
]
当(g_i=1)时，(G(x)=e^x)
那么，$$sum_{d_1+d_2+...+d_n=n-2-k}dfrac{1}{d_1!d_2!...d_n!}w_1{d_1}w_2{d_2}...w_n^{d_n}$$
[=(dfrac{w_1^1}{1!}+dfrac{w_1^2}{2!}+..)(dfrac{w_2^1}{1!}+dfrac{w_2^2}{2!}+..)...(dfrac{w_n^1}{1!}+dfrac{w_n^2}{2!}+..)[其中总次方数为n-2-k]
]
[=G(w_1)G(w_2)...G(w_n)[其中总次方数为n-2-k]
]
[=e^{w_1+w_2+...+w_n}[其中总次方数为n-2-k]
]
[=G(w_1+w_2+...+w_n)=sum dfrac{(w_1+w_2+...+w_n)^i}{i!}
]
那么当(i=n-2-k)时，则就是(sum_{d_1+d_2+...+d_n=n-2-k}dfrac{1}{d_1!d_2!...d_n!}w_1^{d_1}w_2^{d_2}...w_n^{d_n})
即为$$dfrac{(sum_{i=1}{n}w_i){n-2-k}}{(n-2-k)!}$$
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
const int maxlongint=2147483647;
const long long mo=1e9+7;
const int N=2005;
using namespace std;
long long w[N],ans,f[N],sum,jc[N],ww;
int n;
long long mi(long long x,int y)
{
long long s=1;
for(;y;x=x*x%mo,y>>=1) s=y&1?s*x%mo:s;
return s;
}
int main()
{
scanf("%d",&n);
f[0]=jc[0]=ww=1;
for(int i=1;i<=n;i++)
{
scanf("%lld",&w[i]),sum=(sum+w[i])%mo,jc[i]=jc[i-1]*i%mo,ww=ww*w[i]%mo;
for(int j=i;j>=1;j--) f[j]=(f[j]+f[j-1]*w[i]%mo)%mo;
}
for(int k=0;k<=n-2;k++)
ans=(ans+f[k]*mi(sum,n-2-k)%mo*mi(jc[n-2-k],mo-2)%mo)%mo;
printf("%lld",ans*ww%mo*jc[n-2]%mo);
}