首页 Tests

期望：100 + 0 + 0
实际： 0 + 0 + 0
又 boom 0 了

T1 没调出来 + 暴力写挂
传世经典

# Solutions:

# A

考虑合并两棵树 x,yx,y 对答案的影响，设第一棵树的大小为 sizusiz_u ，原答案为 ansuans_u 。

设合并点为 a,ba,b 路径长度为 vv.

那合并后的答案就是：

ans_x+ans_y+v\times siz_x\times siz_y + sum(x, a) \times siz_y+ sum(y, b)\times siz_x$$。 现在我们有两个急需解决的问题，一是如何开下空间，二是计算一棵树内所有点到一个点的距离。 有一个比较聪明的办法是，像线段树一样记录每条边两边连着的子树等信息，然后分治计算距离，这样可以把空间压到边数级别。 为了更快，我们使用一个记忆化。 有一个比较麻烦的地方是，点数是 $2^{64}$ 级别的，如果你直接记录的话一乘就爆，模的话大小关系就丢失了，所以你可以开两个 $siz$ or 使用 `__int128`
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int M = 66;
const int Mod = 1e9 + 7;
#define int __int128
inline int Add (int x, int y) {
	return (x + y) >= Mod ? (x + y - Mod) : (x + y);
}
inline int Mul (int x, int y) {
	return (1ll * x * y >= Mod) ? (1ll * x * y % Mod) : (x * y);
}
#define ll long long
struct Tree {
	ll a, b, v;
	ll ans, lid, rid;
	ll siz;
} tr[100];
#define lsiz tr[tr[id].lid].siz

map < pair<ll, pii> , ll> mckc;

int Dis (int id, int u, int v) {
	if (u == v) return 0;
	if (id == 0) return 0;
	if (u > v) swap(u, v);
	if (mckc[mp(id, mp(u, v))]) return mckc[mp(id, mp(u, v))]; 
	if (v <= lsiz) return mckc[mp(id, mp(u, v))] = Dis(tr[id].lid, u, v);
	if (u > lsiz) return mckc[mp(id, mp(u, v))] = Dis(tr[id].rid, u - lsiz, v - lsiz);
	return mckc[mp(id, mp(u, v))] = Add(Add(Dis(tr[id].lid, tr[id].a, u), tr[id].v), Dis(tr[id].rid, tr[id].b - lsiz, v - lsiz)); 
} 

map < pii, ll > mck;

int sum (int id, int x) {
	if (mck[mp(id, x)]) return mck[mp(id, x)] ;
	if (id == 0) return 0;
	if (x <= lsiz) {
		int res = sum(tr[id].rid, tr[id].b - lsiz);
		res = Add(res, Mul(tr[tr[id].rid].siz, tr[id].v));
		res = Add(res, Mul(tr[tr[id].rid].siz, Dis(tr[id].lid, tr[id].a, x)));
		return mck[mp(id, x)] = Add(res, sum(tr[id].lid, x));
	}
	else {
		int res = sum(tr[id].lid, tr[id].a);
		res = Add(res, Mul(tr[tr[id].lid].siz, tr[id].v));
		res = Add(res, Mul(tr[tr[id].lid].siz, Dis(tr[id].rid, tr[id].b - lsiz, x - lsiz)));
		return mck[mp(id, x)] = Add(res, sum(tr[id].rid, x - lsiz)); 
	}
}

inline void write(int x){
	if (x < 0) x = ~x + 1, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

inline void merge (int id, int id1, int a, int id2, int b, int v) {
	tr[id].ans = Add(tr[id1].ans, tr[id2].ans);
	tr[id].ans = Add(tr[id].ans, Mul(tr[id1].siz, sum(id2, b)));
	tr[id].ans = Add(tr[id].ans, Mul(tr[id2].siz, sum(id1, a)));
	tr[id].ans = Add(tr[id].ans, Mul(tr[id1].siz, Mul(tr[id2].siz, v)));
	tr[id].siz = tr[id1].siz + tr[id2].siz;
	tr[id].a = a, tr[id].b = b + tr[id1].siz;
	tr[id].v = v;
	tr[id].lid = id1, tr[id].rid = id2;
	write(tr[id].ans); putchar('\n'); 
}

signed main() {
	int cases; read(cases);
	while (cases--) {
		int m; read(m);
		tr[0].siz = 1;
		For (i, 1, m) {
			int a, b, c, d, v;
			read(a); read(b); read(c); read(d); read(v);
			c++, d++; 
			merge(i, a, c, b, d, v);   
		}
		mck.clear();
		mckc.clear(); 
		For (i, 0, m) tr[i].siz = tr[i].a = tr[i].b = tr[i].lid = tr[i].rid = tr[i].v = 0;
	}
}

### B 考虑一个排列，把原问题转化为第 $i$ 次可删掉第 $i$ 个点，然后把 $i+1\~ n$ 用 $p$ 的概率鲨掉。 可以发现这两个问题等价 于是设 $dp_{i,j}$ 为当前正在决策第 $i$ 个点删不删，然后 $i\to n$ 面临被鲨掉的风险了 $j$ 次。 于是有转移方程： $$dp_{i,j}=dp_{i-1,j-1}\times (1-p)^{j-1} + dp_{i-1,j}\times (1-(1-p)^j)$$. 前一半的意思是 $i-1$ 个决策把 $i-1$ 删掉了，后面承受了一次被鲨掉的风险；后面是第 $i-1$ 个是被鲨掉的。。
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
const int Mod = 258280327;
inline int Mul (int x, int y) {
	return (1ll * x * y) >= Mod ? (1ll * x * y % Mod) : (x * y);
}
inline int Add (int x, int y) {
	return (x + y) >= Mod ? (x + y - Mod) : (x + y);
}
int qpow (int a, int b) {
	int base = a, ans = 1;
	while (b) {
		if (b & 1) ans = Mul(base, ans);
		base = Mul(base, base);
		b >>= 1;
	}
	return ans;
}
const int N = 3010;
int Inv (int a) { return qpow(a, Mod - 2); }
int n, x, y, pw[N];
int dp[N][N], Ans[N];
int main() {
	int cases; read(cases);
	while (cases--) {
		read(n); read(x); read(y);
		int p = Mul(x, Inv(y));
		pw[0] = 1;
		For (i, 1, n) pw[i] = Mul(pw[i - 1], (1 - p + Mod));
		memset (dp, 0, sizeof dp);
		memset (Ans, 0, sizeof Ans); 
		dp[0][0] = 1;
		int invn = Inv(n); 
		For (i, 1, n) For (j, 1, i) 
			dp[i][j] = Add(Mul(dp[i - 1][j - 1], pw[j - 1]), Mul(dp[i - 1][j], (1 - pw[j] + Mod)));
		For (i, 0, n - 1) {
			For (j, i, n - 1) Ans[i] = Add(Ans[i], Mul(dp[j][i], pw[i]));
		}
		For (i, 0, n - 1)
			printf ("%d ", Mul(Ans[i], invn));
		puts("");
	}
}

### C 结论题 可用 kmp 打表找到 然后高精