@topcoder - SRM697D1L3@ ConnectedStates

@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可以过？

巴特西

@topcoder - SRM697D1L3@ ConnectedStates

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章