「BZOJ3451」「Tyvj1953」Normal-点分治+FFT

发布于 17 天前  60 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「BZOJ3451」「Tyvj1953」Normal-点分治+FFT

Description

求随机点分治的操作次数期望。定义操作次数为每次分治时子树的大小之和。

\(n \leqslant 30000\)

Solution

考虑每个点的贡献为它在点分树上的深度。

对于一个点对\((x,y)\)的贡献即\(x\)是\(y\)父亲的概率,那么点\(x\)必须是\(x\)到\(y\)路径上最先被选择的点。概率是\(\frac{1}{dis(x,y)}\)。

所以统计每一种长度路径的条数即可,用点分治+FFT解决。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「BZOJ3451」「Tyvj1953」Normal-点分治+FFT


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!