# [题解] 2023 杭电多校 Expectation of Rank [计数 dp] # 题目大意 矩阵A∈Fpn×nA\in \Bbb{F}_p^{n\times n}A∈Fpn×n​，其中的每个元素取值为Fp\Bbb{F}_pFp​ 的均匀随机变量。 Fp\Bbb{F}_pFp​ 为ppp 阶有限域，其中ppp 为质数。 求矩阵AAA 的秩的期望E(rank A)\Bbb{E}(rank\ A)E(rank A)。 # 题解 题目有点唬人的，但实际上只用到了一个关键点： ppp 阶有限域下，秩为kkk 的向量组可以确定一个kkk...

# CF890 E PermuTree 题解 [背包 dp][二进制拆分] # 题目大意 给出一个以111 为根节点大小为NNN 的树。 给这个数确定一个长度为NNN 的排列ppp，分配给各节点作为权值。对于一个点对(u,v)(u,v)(u,v)，若满足au<alca(u,v)<ava_u\lt a_{lca(u,v)} \lt a_vau​<alca(u,v)​<av​，则产生111 个贡献。 求总贡献的最大值。 # 题解 首先对一个排列计算贡献的过程，实际上就是对于每一个点xxx，从它的一个子树中选一个点uuu...

# 点到线段的距离 # 两种情况 首先要判断点PPP 到直线ABABAB 的投影是否落在线段ABABAB 上。 若落在线段内，即∠A\angle A∠A 和∠B\angle B∠B 为锐角，则距离为点到直线ABABAB 的距离 若落在线段外，即∠A\angle A∠A 或∠B\angle B∠B 为钝角，则距离为点到线段ABABAB 的最近端点的距离 # 如何判断垂足是否落在线段上？ 有两种做法。 第一种根据角度判断，若∠A\angle A∠A、∠B\angle B∠B...

# H # e # l # l # o