T20201118

Posted on Edited on In Word count in article: 1k Reading time ≈ 4 mins.
正睿18提高day7

T1

DupWSH.png

就是因为数据随机，还有充足的限制条件。

所以爆搜 + 可行性剪枝就可以过了。

T2

Dup2fe.png

首先，我们可以有约定如下：

  • 默认 \(1\) 作为根节点。

  • \(f_x\) 表示从 \(x\) 走到其父亲节点的期望步数。

  • \(g_x\) 表示从 \(x\) 的父亲走到 \(x\) 的期望步数。

  • \(d_x\) 表示 \(x\) 的度数。

那么就可以很轻松的得到： \[ \begin{aligned} f_x&=\frac1d\left(1+\sum_{son_x}\left(f_{son_x}+1+f_x\right)\right)\\ &=\frac1d\left(d+(d-1)f_x+\sum_{son_x}f_{son_x}\right)\\ &=\frac1d\left(d+\sum_{son_x}f_{son_x}\right)+\frac{d-1}df_x \end{aligned} \Leftrightarrow\begin{aligned} \frac1df_x&=\frac1d\left(d+\sum_{son_x}f_{son_x}\right)\\ f_x&=d+\sum_{son_x}f_{son_x} \end{aligned} \]

那么 \(f_x\) 就可以表示为子树内的所有点的度数之和，同理可得 \(g_x\) 就该是子树外的所有点的度数之和。

所以问题似乎变成了一个有点类似树的期望直径(乱叫的)的这么一个东西。

Code

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
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
	int x(0), t(1);
	char o (getchar());
	while (o < '0' || o > '9') {
		if (o == '-') t = -1;
		o = getchar();
	}
	for (; o >= '0' && o <= '9'; o = getchar()) {
		x = (x << 1) + (x << 3) + (o ^ 48);
	}
	return x * t;
}

int n, ans, cur, size[maxn];
int head[maxn], edge[maxn << 1], nxt[maxn << 1];
int f[maxn], g[maxn];
int up[maxn], dn[maxn];

inline void addedge(int u, int v)
{
	nxt[++cur] = head[u];
	head[u] = cur;
	edge[cur] = v;
}

inline void chmax(int &x, int y)
{
	if (y > x) x = y;
}

void dfs(int u, int fa)
{
	size[u] = 1;
	for (int i = head[u], v; i; i = nxt[i]) {
		if ((v = edge[i]) == fa) continue;
		dfs (v, u);
		size[u] += size[v];

		chmax (ans, max(up[u] + g[v] + dn[v], dn[u] + f[v] + up[v]));
		chmax (up[u], up[v] + f[v]);
		chmax (dn[u], dn[v] + g[v]);
	}

	f[u] = (size[u] << 1) - 1;
	g[u] = ((n - size[u]) << 1) - 1;
}

int main()
{
	n = __read();
	for (int i = 1, u, v; i < n; ++i) {
		u = __read(), v = __read();
		addedge(u, v), addedge(v, u);
	}

	dfs(1, 0);
	printf ("%d.00000", ans);
}

T3

DupgYD.png

对于一个有向图，它缩点之后一定是一个 \(\text{DAG}\)。

有如下约定：

  • \(h_i\) 表示 \(i\) 个点的竞赛图的个数，\(h_i=2^{\binom i2}\)
  • \(f_i\) 表示 \(i\) 个点的强连通竞赛图的个数，考虑用总方案减去不合法的方案数，枚举缩点后 \(\text{DAG}\) 尾部的强连通分量的大小，有：
  • \[ f_i=h_i-\sum_{j=1}^{i-1}\binom ijf_ih_{i-j} \]
  • \(g_i\) 表示有 \(i\) 个点时的答案。

那么考虑第 \(i\) 个询问，就考虑在尾部加入一个强连通分量，然后考虑 \(1\) 是否在末尾的强连通分量内： \[ g_i=\sum_{j=1}^if_j\left(\dbinom {i-1}{j-1}h_{i-j}d_j+\dbinom{i-1}{j}g_{i-j}\right) \] 那么这个就是表示的如果 \(i\) 在最后这个联通块中，那么就有 \(d_j\) 的贡献，如果不在最后一个联通块中，那么它一定在另外 \(i-j\) 个点中，然后预处理一下就是 \(O(n^2)\)。

Code

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
55
56
57
58
59
60
#include <bits/stdc++.h>

const int maxn = 3005;
const int mod = 998244353;

inline int Pow(int x, int y)
{
	int ans(1);
	while (y) {
		if (y & 1) ans = 1ll * ans * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return ans % mod;
}

int c[maxn][maxn];
int f[maxn], g[maxn], h[maxn], d[maxn];

inline int read()
{
	int x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

int main()
{
	int n = read();
	for (int i = 1; i <= n; ++i) d[i] = read();

	for (int i = 0; i <= n; ++i) {
		c[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
	}

	f[0] = h[0] = 1;

	
	for (int i = 1; i <= n; ++i)
		h[i] = Pow(2, i * (i - 1) / 2);

	for (int i = 1; i <= n; ++i) {
		f[i] = h[i];
		for (int j = 1; j < i; ++j)
			f[i] = ((f[i] - 1ll * c[i][j] * f[j] % mod * h[i - j] % mod) % mod + mod) % mod;
	}

	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j <= i; ++j)
			g[i] = (g[i] + 1ll * f[j] * (1ll * c[i - 1][j - 1] * h[i - j] % mod * d[j] % mod + 1ll * c[i - 1][j] * g[i - j] % mod)) % mod;
	
	for (int i = 1; i <= n; ++i)
		printf ("%lld\n", 1ll * g[i] * Pow(h[i], mod - 2) % mod);
}