P1272 重建道路 题解
P1272 重建道路 不妨在计算每个节点 uuu 的答案时, 强制选择 uuu, 之后统计每个节点答案的最小值. 设对于节点 uuu, 目前选择前 kkk 个子节点, 子树大小为 sss 的最小删边数为 f[u][k][s]f[u][k][s]f[u][k][s] . 考虑转移. 其实就是找到每个子节点 vvv 的一种分配方案, 子树大小为 svs_vsv , 删边数为 hvh_vhv , 使得 ∑sv=s−1\sum s_v = s - 1∑sv=s−1 , 且 ∑hv\sum h_v∑hv 最小. 这就相当于一个背包问题. 写出转移方程: f[u][k][s]=min(f[u][k−1][s],f[u][k−1][s−sv]+f[v][sv])f[u][k][s] = \min (f[u][k - 1][s], f[u][k - 1][s - s_v] + f[v][s_v]) f[u][k][s]=min(f[u][k−1][s],f[u][k−1][s−sv]+f[v][sv]) 可以用滚动数组滚掉 kkk 这一维. 初始...
费马小定理
费马小定理 定义 若 ppp 为素数, gcd(a,p)=1\gcd(a, p) = 1gcd(a,p)=1 ,则 a^{p - 1} \equiv 1 (\mod p) . 另一种形式: 对于任意整数 aaa ,有 a^p \equiv a (\mod p) . 题目 求 3^{\sum_{i=1}^{2025} i \cdot i!} \mod 101 . 做法 考虑用一招移花接木,将 ∑i=12025i∗i!\sum_{i=1}^{2025} i*i!∑i=12025i∗i! 化成 100n+p(p<100)100n + p (p < 100)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!...
北京大学2024强基计划
在 △ABC\triangle ABC△ABC 中，角 A,B,CA, B, CA,B,C 所对的边分别为 a,b,ca, b, ca,b,c ，BCBCBC 边上的高为 a3\frac{a}{3}3a ，求 (b+c)2bc\frac{(b + c)^2}{bc}bc(b+c)2 的取值范围. 首先有 (b+c)2bc=bc+cb+2≥4\frac{(b + c)^2}{bc} = \frac{b}{c} + \frac{c}{b} + 2 \geq 4bc(b+c)2=cb+bc+2≥4 ，当且仅当 b=cb = cb=c 时取等. S△ABC=12⋅a⋅a3=12bcsinAS_{\triangle ABC} = \frac{1}{2} \cdot a \cdot \frac{a}{3} = \frac{1}{2} bc \sin{A}S△ABC=21⋅a⋅3a=21bcsinA 又有 b2+c2=a2+2bccosAb^2 + c^2 = a^2 +...
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