0529题解

2018-05-29 21:50:05 By fizzydavid

griffin

考虑模拟边加入的过程。对于某一层的边,它们将从某个时间节点出现,所以共有C个时间段,每段中图的形态不改变。

我们可以维护当前时刻,对于每个顶点,有没有可能恰好到达当前节点。如果用01向量来表示,那么从时刻$t$到$t+1$可以用矩阵来转移。在每个时间段内,可以用矩阵乘法倍增来找第一次到达终点的时刻。注意此时并不满足二分性质,添加一条从终点到终点的边后即可处理。此时时间复杂度为$O(c n^3 log w)$。

注意到矩阵乘法可以用位运算加速(按位与),可以将时间复杂度优化到$O(\frac{c n^3 log w}{32})$,即可通过本题。

manastorm

原题:CF891E

将题目转换为求最终每一项的乘积的期望。

使用指数型生成函数,对于第i项$a_i$,它对应的指数型生成函数为$e^x(a_i-x)$,我们要求的是他们的积的第K项的系数。

于是我们只要算$(a_i-x)$的乘积,然后算出每一项对于第K项系数的贡献就好了。可以使用分治FFT加速。

时间复杂度$O(n log^2 n)$

poem

将题目转换为求每个字符串在前缀中出现次数的平方的和。

考虑建出所有串的Generalized Suffix Automaton(或Generalized Suffix Tree,以下以SAM举例),那么我们只需要对于每个串,将它对应的子串集合的出现次数增加,并求出当前所有节点出现次数的平方和即可。每个串对应的所有子串为它的所有前缀的所有后缀。那么对于每个串,我们只需要对于它的每个前缀,将其所有后缀的出现次数+1即可,而它们在suffix link组成的树上是一条根到当前节点的路径,于是可以树剖+线段树解决。

时间复杂度$O(n log^2 n)$

评论

avatar
babblishu
这速度!
avatar
littleming
https://li-mi.github.io/2018/05/30/noi%E6%A8%A1%E6%8B%9F%E8%B5%9B%20%E7%8B%AE%E9%B9%AB%E6%97%85%E8%A1%8C/

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。