A – 迷宫
这道题挺好的,让我知道了线段树还有这样的操作。
考虑线段树维护一段区间行入口到行出口的最短路,大概的维护方法非常像 Floyd。也没啥好说的,看代码吧。
这道题挺好的,让我知道了线段树还有这样的操作。
考虑线段树维护一段区间行入口到行出口的最短路,大概的维护方法非常像 Floyd。也没啥好说的,看代码吧。
这道题的式子跟 Codeforces 一道 F 题是一样的,让我误以为是 BSGS 之类的玩意,最后发现其实算是矩阵乘法的题。
考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的,由于\(k\)很小,所以我们可以考虑计算每一个\(f\)的指数,然后就可以用快速幂来计算这些东西。