【JZOJ5180】【NOI2017模拟6.29】呵呵

题目

分析

套上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_3\sum_{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_{1\leq 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_i\dfrac{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);

}

巴特西

【JZOJ5180】【NOI2017模拟6.29】呵呵

题目

分析

最新文章

热门文章