用户工具

站点工具


2022-2023:teams:kunkunkun:2022-nowcoder-6

这是本文档旧的修订版!


2022 牛客暑期多校训练营6

F-Hash

设树的根节点为 $1$,其 $Hash$ 值为 $\displaystyle\sum_{i=1}^n\sum_{j=i+1}^nX^iY^jZ^{lca(i,j)}$,构造一颗满足其 $Hash$ 值的树,节点数小于等于 $50$。
设树有 $37$ 个节点,全部与 $1$ 相连,考虑将节点 $2\sim 37$ 分为 $6$ 组,每组中取两个节点连到另外一个节点上,会有 $C_5^2\cdot 6=60$ 种情况,$6$ 组共有 $60^6$ 种情况,由于 $X,Y,Z$ 随机给出,每种情况都可视为随机的,则存在解的概率为 $1-(\dfrac{Mod-1}{Mod})^{60^6}\approx 1-5.0341\cdot{10^{-21}}$。

2022-2023/teams/kunkunkun/2022-nowcoder-6.1659842150.txt.gz · 最后更改: 2022/08/07 11:15 由 sd_ltt