2023.9.22
期望得分：\(100+100+50+0\)
实际得分：\(100+100+50+0\)
A. 整数
我们把每一个实数转化成分数。因为小数位不超过 \(9\) 位，所以实数乘上 \(10^9\) 一定变成了一个实数，可以将一个实数 \(x\) 表示成 \(\dfrac{x \times 10^9}{x}\)。
我们记 \(p_x,q_x\) 分别表示 \(x\) 中 \(2\) 和 \(5\) 的因子数量（可以是负数，表示缺多少个因子才能变成正数）。那么两个实数 \(A,B\) 若要满足 \(A\times B\) 是个整数，一定有 \(\min{(p_A+p_B,q_A+q_B)} \geq 0\)。假设当前的数是 \(B\)，那么符合条件的数 \(A\) 一定满足 \(p_A \geq -p_B\) 且 \(q_A \geq -q_B\)，这是个很经典的二维数点问题，同时 \(p_A,q_A\) 都是 \(log\) 级别的，显然可以套二维树状数组。
时间复杂度 \(O(nlog^2A)\)
B. 取子串
用哈希预处理每一个位置 \(i\) 在它之前离它最近的一个 \(T\) 串的首字母的位置 \(p_i\)。
定义 \(f_i\) 表示当前在考虑第 \(i\) 个位置。如果这个位置不选，那么就是 \(f_{i-1}\) 种方案；如果这个位置选，那么将它与它之前离它最近的一个 \(T\) 串捆绑成一组，可以由 \(p_i\) 以前的任意一个位置转移，而它与它后面 \(T\) 串捆绑的方案在它后面一个位置 \(k\) 选择了 \(i\) 前的一个位置转移时统计过了，所以有 $$ f_i = f_{i - 1} + \sum\limits_{i=1}^{p_i-1}a_i$$
转移可以用前缀和优化，最后答案是 \(f_n-1\)，因为要减去空集的情况，时间复杂度 \(O(n)\)
C. 彷徨
code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int kmax = 3e5 + 3;
const int Mod = 998244353;
int n, m;
set<int> st[kmax];
long long res = 1;
int main() {
freopen("university.in", "r", stdin);
freopen("university.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
if(x > y) swap(x, y);
st[x].insert(y);
}
for(int x = 1; x <= n; x++) {
res = res * (n - st[x].size()) % Mod;
if(!st[x].size()) continue;
int y = *st[x].begin();
st[x].erase(y);
if(st[x].size() > st[y].size()) swap(st[x], st[y]); // 启发式合并
for(int it : st[x]) {
st[y].insert(it);
}
}
cout << res << '\n';
return 0;
}
D. 名额限制
设 \(f_x\) 表示当前在 \(x\) 点，经过子树里面一些操作使得 \(x\) 点被经过两次并且回到父亲（过程中不经过父亲）的概率。枚举第一步走到 \(x\) 的一个儿子 \(y\)，第二步可以往 \(y\) 的子树走，也可以回到 \(x\) 点，则：$$f_x = \sum_{y \in son_x} \dfrac{f_y}{\vert G(x)\vert[\vert G(x)\vert-1]} + \dfrac{1}{\vert G(x)\vert^2 G(y)}$$特别地，若 \(x\) 是叶子节点，有 \(f_x = 0\)。
我们令 \(g_{x,0/1}\) 表示刚从 \(x\) 的父亲节点 \(p_x\) 到 \(x\)，且 \(x\) 的父亲经过了 \(1/2\) 次的概率。为了方便，让 \(1\) 无终生爹，边界状态 \(g_{1,1} = 1\)。此外再设 \(h_x\) 表示 \(p_x\) 走到 \(x\)，\(x\) 回到 \(p_x\)，再回到 \(x\) 的概率。有如下转移：
\( g_{x,1} = \dfrac{h_{p_x}}{\vert G(p_x)\vert - 1} + \sum_{y \in son_{p_x}, y \neq x} \dfrac{g_{p_x,0}f_y}{\vert G(p_x) \vert [\vert G(p_x) \vert - 1]} + \dfrac{g_{p_x,0}}{\vert G(p_x) \vert^2\vert G(y) \vert} + \dfrac{g_{p_x,1}f_y}{[\vert G(p_x)\vert - 1][\vert G(p_x) \vert - 2]} + \dfrac{g_{p_x,1}}{[\vert G(p_x) \vert - 1]^2 G(y)} \)
然后考虑统计答案。对于叶子结点 \(x\)，只要当前在它且父亲两次了就行，概率为 \(h_x + g_{x,1}\)。对于儿子个数大于 \(1\) 的结点，它不可能是一次演出的终点。对于儿子个数等于 \(1\) 的点 \(x\)，设它的儿子为 \(y\)，概率是 \(g_{x,1}f_y\)。
逆元提前处理，时间复杂度 \(O(n)\)
code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int kmax = 1e6 + 3;
const int Mod = 1e9 + 7;
struct E {
int p, y;
} e[kmax << 1];
int n, a[kmax], d[kmax];
int hd[kmax], ec;
int p[kmax], son[kmax];
long long f[kmax], g[kmax][2], h[kmax], res;
long long inv[kmax];
void Addedge(int x, int y) {
e[++ec] = {hd[x], y};
hd[x] = ec;
}
void Dfs(int x, int fa) {
p[x] = fa;
for(int i = hd[x]; i; i = e[i].p) {
int y = e[i].y;
if(y == fa) continue;
Dfs(y, x);
son[x]++;
f[x] = (f[x] + f[y] * inv[d[x]] % Mod * inv[d[x] - 1] % Mod + inv[d[x]] * inv[d[x]] % Mod * inv[d[y]] % Mod) % Mod;
}
}
void Dfss(int x) {
h[x] = (g[p[x]][0] * inv[d[p[x]]] % Mod * inv[d[p[x]]] % Mod * inv[d[x]] % Mod + g[p[x]][1] * inv[d[p[x]] - 1] % Mod * inv[d[p[x]] - 1] % Mod * inv[d[x]] % Mod) % Mod;
g[x][0] = (g[p[x]][0] * inv[d[p[x]]] % Mod + g[p[x]][1] * inv[d[p[x]] - 1] % Mod) % Mod;
g[x][1] = h[p[x]] * inv[d[p[x]] - 1] % Mod;
for(int i = hd[p[x]]; i; i = e[i].p) {
int y = e[i].y;
if(y == p[p[x]]) continue;
if(y == x) continue;
g[x][1] = (g[x][1] + g[p[x]][0] * f[y] % Mod * inv[d[p[x]]] % Mod * inv[d[p[x]] - 1] % Mod) % Mod;
g[x][1] = (g[x][1] + g[p[x]][0] * inv[d[p[x]]] % Mod * inv[d[p[x]]] % Mod * inv[d[y]] % Mod) % Mod;
g[x][1] = (g[x][1] + g[p[x]][1] * f[y] % Mod * inv[d[p[x]] - 1] % Mod * inv[d[p[x]] - 2] % Mod) % Mod;
g[x][1] = (g[x][1] + g[p[x]][1] * inv[d[p[x]] - 1] % Mod * inv[d[p[x]] - 1] % Mod * inv[d[y]] % Mod) % Mod;
}
for(int i = hd[x]; i; i = e[i].p) {
int y = e[i].y;
if(y == p[x]) continue;
Dfss(y);
}
}
void Init() {
inv[0] = inv[1] = 1;
for(int i = 2; i < kmax; i++) {
inv[i] = inv[Mod % i] * (Mod - Mod / i) % Mod;
}
}
int main() {
freopen("rap.in", "r", stdin);
freopen("rap.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
Init();
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1, x, y; i < n; i++) {
cin >> x >> y;
Addedge(x, y);
Addedge(y, x);
d[x]++, d[y]++;
}
Addedge(1, 0);
d[1]++;
Dfs(1, 0);
g[1][1] = 1;
for(int i = hd[1]; i; i = e[i].p) {
int y = e[i].y;
if(y == p[1]) continue;
Dfss(y);
}
for(int x = 1; x <= n; x++) {
// cout << "x = " << x << '\n';
// cout << son[x] << ' ' << f[x] << ' ' << g[x][0] << ' ' << g[x][1] << ' ' << h[x] << '\n';
if(!son[x]) {
res = (res + (h[x] + g[x][1]) % Mod * a[x] % Mod) % Mod;
} else if(son[x] == 1) {
for(int i = hd[x]; i; i = e[i].p) {
int y = e[i].y;
if(y == p[x]) continue;
res = (res + f[y] * g[x][1] % Mod * a[x] % Mod) % Mod;
}
}
}
cout << res << '\n';
return 0;
}