C – The Number Of Good Substrings
这道题比较傻逼。
考虑记录上一个最近的\(1\)的位置\(nxt_i\)，然后显然的是：如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间，那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。
这道题比较傻逼。
考虑记录上一个最近的\(1\)的位置\(nxt_i\)，然后显然的是：如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间，那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。
这道题可以离线回答，很大概率是什么树上差分之类的东西。但是树上差分无法维护区间信息，然后想到用权值线段树来维护。如果暴力开\(1e5\)个线段树来维护会 GG，但是我们可以动态开点，然后每个点对应的线段树大小差不多为\(O(\log n)\)级别的，这样空间就可以接受的了。
既然有了很好用的动态开点线段树，我们就可以用树上差分那一套路，在端点和\(LCA\)处打标记，然后考虑从下往上合并答案。合并可以用线段树合并，复杂度为重合部分，差不多就是\(O(\log n)\)。然后就没了，很傻逼的一道题。
这道题挺好的，让我知道了线段树还有这样的操作。
考虑线段树维护一段区间行入口到行出口的最短路，大概的维护方法非常像 Floyd。也没啥好说的，看代码吧。
这道题的式子跟 Codeforces 一道 F 题是一样的，让我误以为是 BSGS 之类的玩意，最后发现其实算是矩阵乘法的题。
考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的，由于\(k\)很小，所以我们可以考虑计算每一个\(f\)的指数，然后就可以用快速幂来计算这些东西。
这道题我在考场上打了一个错解，还骗到了 30 分。
正常的思路是：在最短路图上找到几个边进行修改。然而，最优的解决方案并不一定出现在最短路图上的边上，也可以通过修改次优边进行解决。所以，这道题其实跟最短路没什么太大关系，即使后面会用到 Djisktra 来求最短路。
我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份，然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\)，可以生成一个副本来连接下一层的目标点，也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\)，当最后求最短路时，经过这样的一条边可以被认为是修改一条边，且，这个边是单向向下的，所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路，然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。