日记

这是2025年10月22日的日记

周三 10月 22 2025

510 字 · 3 分钟

为了肤浅的事物找一个合理又正当的理由，多么可笑啊。

小 h 学步↗

给劳罗教的全忘完了。

观察到有向量，有模长的平方，我们想到一个东西： $\vec{a}^2 = |\vec{a}|^2$ 。由于 $\forall i,\sum_{j = 1}^{n}\vec{a_{i,j}} = \vec{0}$ ，所以把所有的向量都平方，加起来。最后乘上他们的贡献次数： $n^{n - 1}$ 就得到了最终的答案。

小球进洞↗

我们设 $dp_{u,i}$ 表示以 $u$ 为根的子树内有 $i$ 个球掉进新打的洞里了。设 $cnt_u$ 表示 $u$ 子树内的叶子数量， $siz_u$ 表示 $u$ 子树大小。那么有转移：

dp_{u,i} \gets \begin{cases} dp_{u,i} \times i & \text{球掉进打的洞里了，有 } i \text{ 种方案。} \\ dp_{u,i} \times cnt_u & \text{球掉进叶子的洞里了，有 } cnt_u \text{种方案。} \\ dp_{u,i - 1} \times \frac{siz_u - 1}{n - 1} & \text{有 } \frac{siz_u - 1}{n - 1} \text{ 的概率新打一个洞在 } u \text{ 子树内} \end{cases}

总计答案有 $ans = \sum_{i = cnt_1}^{m + cnt_1}dp_{1,i} \times \frac{m!}{(m - i + cnt_1)!}$ ，表示剩下的随便选。

炒鱿鱼↗

我们对于两个不能用同一个人事部员工的天之间建一条边，那么可以证明这个图一定是一个三分图。

证明：
我们发现一个点的出度至多是 $2$ ，形成的最大团也就只能是 $3$ ，所以这是一个三分图。

于是直接进行三分图染色。染色过程如下：

对于 $u$ 确定一个颜色 $col_u$ ，具体为使得 $ban_{u,i} = 0$ 的最小 $i$ 就是 $col_u$ 。（因为这样就不用判二分图了）
先来一次循环 $v \in son_u$ ，如果 $v$ 没确定颜色（ $col_v = 0$ ），将 $ban_{v,i}$ 置为 $1$ 。
再来一次循环 $v \in son_u$ ，如果有 $v$ 已经确定（指 ban 了两个颜色且 $col_v = 0$ ）就 dfs(v)。
最后一次循环 $v \in son_u$ ，将剩下的 $v$ 进行 dfs(v)。

然后染完色了就行了。

后日谈

我什么都做不到。

Thanks for reading!

日记

周三 10月 22 2025

510 字 · 3 分钟

© 伊埃斯 | CC BY-NC-SA 4.0