就是给定一张有向图,问一个点能否到达另一个。
显然,弗洛伊德可以在 O(n3)\mathcal O(n^3)O(n3) 的时间内解决。
结果校内 OJ 告诉我有更快的做法,能解决 n≤8×104n \le 8 \times 10^4n≤8×104 的情况!
惊了!这枚举出点对都不够啊!
所以怎么做呢?bfs 未果。
当然输入输出有变化。
f(i,j)f(i,j)f(i,j) 表示 iii 能否到达 jjj , 能是 111, 不能是 000 输出 nnn 行,第 iii 行一个整数,表示 (∑j=1nf(i,j)×2(j−1) mod 64×w⌈j64⌉) mod 264\left(\sum\limits_{j=1}^{n} f(i,j)\times 2^{(j-1)\bmod 64}\times w_{\lceil\frac{j}{64}\rceil}\right)\bmod{2^{64}}(j=1∑nf(i,j)×2(j−1)mod64×w⌈64j⌉)mod264
f(i,j)f(i,j)f(i,j) 表示 iii 能否到达 jjj , 能是 111, 不能是 000
输出 nnn 行,第 iii 行一个整数,表示 (∑j=1nf(i,j)×2(j−1) mod 64×w⌈j64⌉) mod 264\left(\sum\limits_{j=1}^{n} f(i,j)\times 2^{(j-1)\bmod 64}\times w_{\lceil\frac{j}{64}\rceil}\right)\bmod{2^{64}}(j=1∑nf(i,j)×2(j−1)mod64×w⌈64j⌉)mod264