@topcoder - SRM697D1L3@ ConnectedStates

红太狼 2023-06-01 12:59 21阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

有n个城市，每个城市有个权值wi，任意两个城市i,j之间的道路数有wi∗wj条。  
对于每种生成树，设每个点的度数为di，其权值定义为∏di。  
问所有无根生成树的权值和。答案对1e9+7取模。

**Class:**  
ConnectedStates  
**Method:**  
getSum  
**Parameters:**  
int\[\]  
**Returns:**  
int  
**Constraints**  
n <= 2000

**Examples**  
0）  
\{"3, 10"\}  
Returns: 30  
1）  
\{"2, 2, 2"\}  
Returns: 96  
2）  
\{"1, 1, 1, 1"\}  
Returns: 60

## @solution@ ##

考虑如果固定了生成树的形态，对应的方案应该是所有树边条数的乘积。  
稍微变一变其实就是 \\(\\prod\_\{i=1\}^\{n\}w\_\{i\}^\{d\_i\}\\)，这样就只跟点的度数有关了。

根据我们的 prufer 定理，最终答案为：  
\\\[ans = (n-2)!\*\\sum\_\{(\\sum\_\{i=1\}^\{n\}d\_i) = 2\*n-2\}(\\prod\_\{i=1\}^\{n\}\\frac\{w\_\{i\}^\{d\_i\}\}\{(d\_i-1)!\}\*d\_i)\\\]

如果将 i 有关的项整理到一起然后 fft 一下的时间复杂度是 O(n^2\*logn)，但是我们可以做到更优。

优化的思路来源在于多项式的幂公式，即：  
\\\[(a\_1 + a\_2 + ... + a\_n)^k = k!\*\\sum\_\{(\\sum\_\{i=1\}^\{n\}b\_i) = k\}(\\prod\_\{i=1\}^\{n\}\\frac\{a\_\{i\}^\{b\_i\}\}\{ \{b\_i\}!\})\\\]

注意到下面这个公式和上面的答案表达式其实是很相像的，我们考虑进一步地变形：  
令 \\(a\_i = d\_i - 1\\)，得到：  
\\\[ans = (\\prod\_\{i=1\}^\{n\}w\_i)\*(n-2)!\*\\sum\_\{(\\sum\_\{i=1\}^\{n\}a\_i) = n-2\}(\\prod\_\{i=1\}^\{n\}\\frac\{w\_\{i\}^\{a\_i\}\}\{a\_i!\}\*(a\_i+1))\\\]

基本就是一样了，但还有一个 \\(\\prod\_\{i=1\}^\{n\}(a\_i + 1)\\) 阻碍我们。  
考虑将它拆开，依次考虑每一个单项式 \\(a\_\{p\_1\}\*a\_\{p\_2\}\*...\*a\_\{p\_m\} = \\prod\_\{j=1\}^\{m\}a\_\{p\_j\}\\) 的贡献，其中 \\(1 \\le p\_1 < p\_2 < ... < p\_m \\le n\\)。它的贡献为：  
\\\[\\sum\_\{(\\sum\_\{i=1\}^\{n\}a\_i) = n-2\}(\\prod\_\{i=1\}^\{n\}\\frac\{w\_\{i\}^\{a\_i\}\}\{a\_i!\}\* \\prod\_\{j=1\}^\{m\}a\_\{p\_j\})\\\]

考虑将这些 a 乘入阶乘中去，令得到的新的阶乘分别为 \\(c\_1, c\_2, ... c\_n\\)，再变一下形得到：  
\\\[\\prod\_\{j=1\}^\{m\}w\_\{p\_j\}\*\\sum\_\{(\\sum\_\{i=1\}^\{n\}c\_i) = n-2-m\}(\\prod\_\{i=1\}^\{n\}\\frac\{w\_\{i\}^\{c\_i\}\}\{c\_i!\}) = \\prod\_\{j=1\}^\{m\}w\_\{p\_j\}\*\\frac\{(\\sum\_\{i=1\}^\{n\}w\_i)^\{n-2-m\}\}\{(n-2-m)!\}\\\]

终于化成了我们想要的东西。  
再将上面那个套入我们的答案表达式中，即可得到：  
\\\[ans = \\sum\_\{m=0\}^\{n-2\}(\\sum\_\{1 \\le p\_1 < p\_2 < ... < p\_m \\le n\}\\prod\_\{j=1\}^\{m\}w\_\{p\_j\})\*\\frac\{(\\sum\_\{i=1\}^\{n\}w\_i)^\{n-2-m\}\}\{(n-2-m)!\}\\\]

中间那个看似很鬼畜的式子用 dp 处理一下就好啦。时间复杂度 O(n^2)。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 2000; const int MOD = int(1E9) + 7; class ConnectedStates{ public: int pow_mod(int b, int p) { int ret = 1; while( p ) { if( p & 1 ) ret = 1LL*ret*b%MOD; b = 1LL*b*b%MOD; p >>= 1; } return ret; } int dp[MAXN + 5], w[MAXN + 5], pro, n; int fct[MAXN + 5], ifct[MAXN + 5], pw[MAXN + 5]; void get_ready() { dp[0] = 1; for(int i=1;i<=n;i++) for(int j=n;j>=1;j--) dp[j] = (dp[j] + 1LL*dp[j-1]*w[i]%MOD)%MOD; pw[0] = 1, pw[1] = 0, pro = 1; for(int i=1;i<=n;i++) pw[1] = (pw[1] + w[i])%MOD, pro = 1LL*pro*w[i]%MOD; for(int i=2;i<=n;i++) pw[i] = 1LL*pw[i-1]*pw[1]%MOD; fct[0] = 1; for(int i=1;i<=n;i++) fct[i] = 1LL*fct[i-1]*i%MOD; ifct[n] = pow_mod(fct[n], MOD - 2); for(int i=n-1;i>=0;i--) ifct[i] = 1LL*ifct[i+1]*(i+1)%MOD; } int getSum(vector<int>vec) { n = vec.size(); for(int i=1;i<=n;i++) w[i] = vec[i-1]; get_ready(); int ret = 0; for(int i=0;i<=n-2;i++) ret = (ret + 1LL*dp[i]*pw[n-2-i]%MOD*ifct[n-2-i]%MOD)%MOD; return 1LL*ret*fct[n-2]%MOD*pro%MOD; } };

## @details@ ##

当我看到这个做法的瞬间：woc 这是什么神仙操作。  
果真人类智慧啊。  
但我觉得这个数据范围好像fft可以过？

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11363103.html