如此成绩，如何 noip？
A
题意：\(T\) 组询问，每次给出一个正整数 \(n = p^kq^k \le 10^{18}\)。
求非降序列 \(\{a_{m}\}\)（\(m > 1\)）的数量，满足 \(\prod a_i = n\)。
非降并不需要真正考虑每个数的顺序，这很不可做。
考虑 \(n\) 的每个因数在序列中的出现次数。
一个长为 \((k + 1)^2 - 2\) 的向量组 \([c_1, c_2 \cdots, c_i, \cdots]\) 可以唯一对应一个序列，这是一个双射。
转化到完全背包模型，\(f_{i, j}\) 表示乘到 \(p^iq^j\) 的方案数。枚举因子 \(p^{i}q^j\)，顺序更新 \(p^{x \ge i}q^{y \ge j}\)。
答案只与 \(k\) 有关，瓶颈在于如何快速找 \(k\)。（\(6^{24} > 10^{18}\)，所有 \(f\) 可以预处理）
枚举 \(k\)，直接调用 pow(1, 1./ k)，加 0.5 规避精度问题。
void init() {
f[0][0] = 1;
for(int i = 0; i <= 23; ++ i) {
for(int j = 0; j <= 23; ++ j) {
if(i || j)
for(int x = i; x <= 23; ++ x) {
for(int y = j; y <= 23; ++ y) {
f[x][y] += f[x - i][y - j];
}
}
}
}
}
void solve() {
cin >> n;
for(int i = 23; i >= 1; -- i) {
auto x = powl(n, 1./ i); ll y = x + 0.5;
if(fabsl(x - y) <= eps) {
cout << f[i][i] - 1 << '\n';
return;
}
}
}
B
题意：从时刻 \(0\) 遍历一棵树，每一时刻只能走一条边。每个点的代价为到达这个点的时刻，\(n \le 10^5\)。
钦定起点（选根），肯定是一棵子树遍历完了再去其他地方。
定义 \(f(i)\) 表示走完 \(i\) 这棵子树的最小代价。
考虑每个儿子 \(j\)，从 \(i\) 走到任意 \(j\) 子树内的点都会经过 \((i, j)\) 并使他的代价加 \(1\)，因此 \(i\) 对 \(j\) 的额外贡献等于 \(sz_j\)。
已经遍历完的子树 \(k\) 对 \(j\) 中每个点的额外贡献等于在 \(k\) 中经过的时间 \(2 sz_k\)。
\[f(i) \gets f(j) + sz_j (1+ 2\sum_{k} sz_k) \]\(sz_k\) 会对所有在他之后的子树产生额外贡献，这是不是意味着我们需要按照子树大小升序遍历呢？
不管怎么遍历，数对 \((j, k)\) 对答案的贡献都是 \(2sz_j\cdot sz_k\)，因此 \(f(i)\) 可以写成：
\[\sum_{j} \big(f(j) + sz_j\big) + 2\sum_{j, k} sz_j \cdot sz_k \]换根好像还挺好写的。
#include<bits/stdc++.h>
#define eb emplace_back
#define ep emplace
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;
int n, m, rt, sz[N]; ll f[N], g[N], tmp[N], sum[N], ans = 1e18;
vector<int> G[N];
void dfs(int x, int fa) {
f[x] = sz[x] = 0;
for(int y : G[x]) {
if(y == fa) continue;
dfs(y, x);
f[x] += sz[y] + f[y] + 2ll * sz[y] * sz[x];
sum[x] += f[y];
tmp[x] += 2ll * sz[y] * sz[x];
sz[x] += sz[y];
}
++ sz[x];
}
void dfs1(int x, int fa) {
ans = min(ans, g[x]);
for(int y : G[x]) {
if(y == fa) continue;
g[y] = sum[y] + n - 1;
g[y] += (g[x] - f[y] - sz[y] - 2ll * sz[y] * (n - sz[y] - 1));
tmp[y] += 2ll * (sz[y] - 1) * (n - sz[y]);
g[y] += tmp[y];
dfs1(y, x);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n - 1; ++ i) {
int u, v; cin >> u >> v;
G[u].eb(v);
G[v].eb(u);
}
dfs(1, 0);
g[1] = f[1], dfs1(1, 0);
cout << ans;
return 0;
}
C
题意：\((x_1, \cdots, x_m)\) 是好的，当且仅当对于 \(1 < j \le m\)，要么有 \(x_i = x_{i - 1} + 1\)，要么存在 \(k \le j < i\) 使得 \(x_i = x_kx_j\)。