P1272 重建道路 题解
P1272 重建道路 不妨在计算每个节点 $u$ 的答案时, 强制选择 $u$, 之后统计每个节点答案的最小值. 设对于节点 $u$, 目前选择前 $k$ 个子节点, 子树大小为 $s$ 的最小删边数为 $f[u][k][s]$ . 考虑转移. 其实就是找到每个子节点 $v$ 的一种分配方案, 子树大小为 $s_v$ , 删边数为 $h_v$ , 使得 $\sum s_v = s - 1$ , 且 $\sum h_v$ 最小. 这就相当于一个背包问题. 写出转移方程: $$ f[u][k][s] = \min (f[u][k - 1][s], f[u][k - 1][s - s_v] + f[v][s_v]) $$ 可以用滚动数组滚掉 $k$ 这一维. 初始 $f[u][1] = 0$ (只选择这个节点), 其余为正无穷. 注意统计答案时, 对于每个非根节点, 由于其与父节点的连边需要断开, 答案要 $+1$ .
费马小定理
费马小定理 定义 若 $p$ 为素数, $\gcd(a, p) = 1$ ,则 $a^{p - 1} \equiv 1 (\mod p)$ . 另一种形式: 对于任意整数 $a$ ,有 $a^p \equiv a (\mod p)$ . 题目 求 $3^{\sum_{i=1}^{2025} i \cdot i!} \mod 101$ . 做法 考虑用一招 移花接木 ,将 $\sum_{i=1}^{2025} i*i!$ 化成 $100n + p (p < 100)$ 的形式,有 $$3^{\sum_{i=1}^{2025} i \cdot i!} = 3^{100n} \cdot 3^p$$ . 由费马小定理,得 $$3^{100n} \equiv 1 (\mod 101)$$ . 故 $$3^{100n} \cdot 3^p \equiv 3^p$$ . 下求 $p$ ,即求 $\sum_{i=1}^{2025} i \cdot i! \mod 100$ . 因为 $$i \cdot i! = (i + 1 - 1) \cdot i! = (i + 1)! -...
北京大学2024强基计划
在 $\triangle ABC$ 中，角 $A, B, C$ 所对的边分别为 $a, b, c$ ，$BC$ 边上的高为 $\frac{a}{3}$ ，求 $\frac{(b + c)^2}{bc}$ 的取值范围. 首先有 $\frac{(b + c)^2}{bc} = \frac{b}{c} + \frac{c}{b} + 2 \geq 4$ ，当且仅当 $b = c$ 时取等. $S_{\triangle ABC} = \frac{1}{2} \cdot a \cdot \frac{a}{3} = \frac{1}{2} bc \sin{A}$ 又有 $b^2 + c^2 = a^2 + 2bc\cos{A}$ 故 $b^2 + c^2 = 2bc\cos{A} + 3bc\sin{A}$ 所以 $\begin{align}\frac{(b+c)^2}{bc} = \frac{b^2 + c^2}{bc} + 2 \ = 2\cos{A} + 3\sin{A} + 2 \ = \sqrt{13} \sin(A-\varphi) + 2 (\tan{\varphi} =...
Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick Start Create a new post $ hexo new "My New Post" More info: Writing Run server $ hexo server More info: Server Generate static files $ hexo generate More info: Generating Deploy to remote sites $ hexo deploy More info: Deployment