时与风
对每条边进行 BFS。二维偏序部分用 vector 存一下就行了。
花神诞日
引理：对于 \(a<b<c\)，\(\min(a\text{ XOR }b,b\text{ XOR }c)\leq a\text{ XOR }c\)。
证明：考虑比较 \(a,c\) 二进制下第一位不同，也就是 \(a=(X0\dots)_{(2)},c=(X1\dots)_{2}\)。因为 \(b\in(a,c)\) 所以 \(b\) 也有 \(X\) 前缀，后一位必然和 \(a\) 或者 \(c\) 相同。证毕。
原问题我们只需要排序，只需要关注相邻数的异或大小。
考虑 dp，假设 \(f_{i,j}\) 表示考虑到 \(a[1,\max(i,j)]\)，第一道菜最后放置 \(i\)，第二道最后放置 \(j\) 的方案数。直接转移是 \(\mathcal O(n^3)\)。
你发现 \(f_{i,j}\) 当 \(i-j\geq 2\) 时只能从 \(f_{i-1,j}\) 转移而来，复杂度降至 \(\mathcal O(n^2)\)。
这样子，我们根据经典技巧压掉一位，对每个 \(i\)，考虑 \(T(i)_j\) 表示 \(i\) 放在第一道菜，上一个放到第二道菜的是 \(j\) 的方案数。考虑 \(T(i)\) 转移到 \(T(i+1)\)，\(S(i)_j\) 表示 \(i\) 放第二道菜的方案数。
- 如果 \(a_i\text{ XOR }a_{i+1}< k_1\)，那么 \(T(i)\) 不能转到 \(T(i+1)\)。
- 否则，\(T(i+1)\) 继承 \(T(i)\)。
最后再考虑 \(T(i+1)_i\) 的情况，其会从 \(S(i)\) 转移而来，具体的从每个 \(a_j\text{ XOR }a_{i+1}\geq k_1\) 的数转移过来。
这部分我们只需要对 \(T(i),S(i)\) 维护一颗 trie 树就容易查询了。
永恒
考虑一条路径上面的数依次是 \(P_1,P_2,\dots,P_n\)（\(n\geq 2\)），从 \(1\) 走到 \(n\)，你可以在 \(\bmod P=1145141\) 下得到多少余数？
考虑一种更加简单的情况 \(P_i\equiv 1\)，那么走出的路径形如 \(11\dots1\)（\(2k\) 个 \(1\)），即 \(\dfrac{10^{2k}-1}{9}\)。注意到 \(10\) 是 \(\bmod P\) 意义下的原根，也就是能走出所有形如 \(\dfrac{x^2-1}{9}\) 的数。这个是好判断的。
进一步，这个方法可以扩展到 \(P_1=P_3=\dots,P_2=P_3=\dots\) 的情况，也就是判断二次剩余。
考虑如果出现某个 \(P_{i-1}\not=P_{i+1}\)，我们断言所有数都能被表示。
具体构造大概是从 \(1\) 走到 \(i\) 之后不断从 \(i\) 走到 \(i±1\) 再走到 \(i\)。这样子我们就得到类似 \(10^{2k}\) 的线性组合的玩意。这东西显然能组成 \(\bmod P\) 意义下的完全剩余类。
路径的问题可以扩展到连通块，只需要对连通块黑白染色，要求黑格的数完全相同，白格的数完全相同就可以判断二次剩余，否则就能表示出所有数。
对于原问题，还有更改操作。直接线段树分治即可。
时间复杂度：\(\mathcal O((nm+q)\log q\log nm)\)。
标签：dots,geq,题解,bmod,2024,mathcal,考虑,省队,2k From： https://www.cnblogs.com/OtomachiUna/p/18038443