【Topcoder SRM697 Hard】【JZOJ5180】ConnectedStates 题解
题目大意
![](/images/jzoj5180.png)
$n \le 2000,\ w_i \le 10^9$
题解
稍微有点妙啊。。。
与度数有关的无根树计数,考虑 prufer 序。
暴力可以直接 $O(n^3)$ dp 计算答案。
考虑优化。
假设第 $i$ 个数在 prufer 序的出现次数是 $a_i$,那么求的是:
其中与 $a$ 无关的是 $(n-2)!×\prod w_i$,去掉之后原式变成:
接着考虑拆开 $\prod (a_i+1)$,拆开后的每一项就相当于我选择一些 $a_i$ 乘起来。假设我选择的是 $a_{p_1},a_{p_2},…,a_{p_k}$,则有:
上面的 $a$ 会跟下面的阶乘约掉,那么我可以一开始就给这一部分 $a$ 减 $1$,然后乘上后面少了的 $w$,相当于:
注意到我只要枚举 $k$ 的话,前后两部分就独立了。前面是个背包,所以现在化简后面。
后面这个东西跟 EGF(指数型生成函数) 很像,相当于求 :
于是就。。做完了。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| #include<cstdio> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std;
typedef long long LL;
const int maxn=2005; const LL mo=1e9+7;
int n,w[maxn]; LL sumw,prow=1;
LL fac[maxn],ny[maxn],f[maxn][maxn]; LL mi(LL x,LL y) { LL re=1; for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo; return re; } void Pre() { fac[0]=ny[0]=1; fo(i,1,n) fac[i]=fac[i-1]*i%mo; ny[n]=mi(fac[n],mo-2); fd(i,n-1,1) ny[i]=ny[i+1]*(i+1)%mo; f[0][0]=1; fo(i,1,n) fo(j,0,i) { f[i][j]=f[i-1][j]; if (j) (f[i][j]+=f[i-1][j-1]*w[i])%=mo; } }
int main() { scanf("%d",&n); fo(i,1,n) { scanf("%d",&w[i]); if (!w[i]) {printf("0\n"); return 0;} (sumw+=w[i])%=mo; (prow*=w[i])%=mo; } Pre(); LL ans=0; fo(k,0,n-2) (ans+=f[n][k]*mi(sumw,n-2-k)%mo*ny[n-2-k])%=mo; printf("%lld\n",ans*prow%mo*fac[n-2]%mo); }
|