ZigZagK

Never give up fighting!

[随机]BZOJ5365(Lydsy1805月赛)【回文树】题解

题目概述

给你 \(n\) 个点的树,每个点有一个 \([1,n]\) 的随机权值,问有多少回文路径。

解题报告

因为是随机的……所以你要有信仰,假装回文路径长度最多只有 \(5\) 就行了。

然后因为他只有 \(3s\) 时限……你会TLE不止(小常数巨佬们当我没说)……

我们再来理性分析一波:一个串是回文串的概率为 \(({1\over n})^{len/2}\) ,当 \(len=4\) 的时候概率就只有 \(10^{-10}\)真棒

所以我们只要考虑 \(len\le 3\) 的情况就行了,瞎搞搞。

ps:\(n\) 非常小的时候最好还是 \(O(n^2)\) 处理,但是BZOJ没卡我,不想管了XD……

示例程序

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

不资瓷Markdown;资瓷LaTeX:行内公式\(...\),行间公式\[...\]