2017 西安网络赛 A题 TREE

最近想起来这么一道题,当时q神没rush出来,赛后几分钟AC掉的

题目链接:https://nanti.jisuanke.com/t/17114

题意是树上有\(N\)个点,每个点的点权是一个01矩阵,有\(Q\)次询问,每次问树上从x到y这条路径上的矩阵依次乘起来的结果是多少(模2意义下)。数据范围\(N\le 3000,Q\le 30000\),矩阵大小\(64\times 64\)。

首先这里的模2意义下的矩阵乘法可以用bitset优化,每行一个bitset,每列一个bitset,这样做乘法就是左行右列and起来,然后count一下1的个数,复杂度\(O({64}^2)\)。

注意到这道题中维护的信息只能合并,不能做“减法”,也就是不能使用逆矩阵,因为逆矩阵不一定存在。

一个显然的暴力思路是就是树上倍增,但很不幸,时间复杂度\(O({64}^2QlogN)\)达到了\(1.4\times 10^9\)肯定会超时。

我们用离线求LCA的方法,就可以把log去掉了。这里要注意题目中是点权,我们要先把点权看成边权,然后再把x与y的LCA处的矩阵乘上。另外,矩阵乘法是有顺序的,所以一条链,从上到下与从下到上乘起来是不一样的,所以要用两个并查集分别维护。忽略并查集的话,最终总的时间复杂度为\(O({64}^2N+{64}^2Q)\)。

这个题实际上还有树分治的写法,改天补一下。