期望: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 打表找到 然后高精
更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝