2020-2021:teams:alchemist:weekly_digest_9
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_9 [2020/08/07 16:56] hardict [龙鹏宇 Hardict] |
2020-2021:teams:alchemist:weekly_digest_9 [2020/08/07 17:05] (当前版本) hardict [龙鹏宇 Hardict] |
||
|---|---|---|---|
| 行 120: | 行 120: | ||
| === 标签： === | === 标签： === | ||
| + | |||
| + | 期望，点分治，FFT | ||
| === 题意： === | === 题意： === | ||
| + | |||
| + | 给定一棵树，每次随机选一个未被选过点，获得改点目前联通块大小的分数，并删除该点 | ||
| + | |||
| + | 求期望分数 | ||
| === 题解： === | === 题解： === | ||
| + | |||
| + | 考虑$u,v$两点,其至多提供一次贡献,当且仅当$u \leftrightarrow v$路径存在,且此次选取$u,v$两点之一 | ||
| + | |||
| + | $dis(u,v)=dis$,则贡献为$\frac{2}{dis+1}$ | ||
| + | |||
| + | 再考虑单点还有一个贡献，则答案为$n+\sum_{i=1}^{n-1}cnt[i]\frac{2}{i+1},cnt[i]为树中路径长度为i的个数$ | ||
| + | |||
| + | 考虑点分治进行统计，可以利用FFT进行优化 | ||
| + | |||
| + | 具体操作是，定根下，构造一个关于每种$depth$个数的生成函数，然后做卷积 | ||
| + | |||
| + | 然后就可以利用容斥$O(N\log^{2}{N})$求解 | ||
| + | |||
| + | 但需要注意，因为FFT计算过多，可以预处理每次FFT的置换以及单位根值进行优化 | ||
| === 评论： === | === 评论： === | ||
| + | |||
| + | 多次计算FFT时可以牺牲一定空间预处理一些值优化时间 | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
2020-2021/teams/alchemist/weekly_digest_9.1596790593.txt.gz · 最后更改: 2020/08/07 16:56 由 hardict
