【杂题乱写】AtCoder-ARC113-526互联

AtCoder-ARC113A ABC

枚举 \(A,B\)，那么 \(C\in [1,\left\lfloor\frac{K}{AB}\right\rfloor]\)，时间复杂度是 \(O(K\log K)\)。

\(A^k\) 的末尾存在循环节，找到循环节长度 \(|T|\)，答案就是 \(A^{B^C \bmod |T|}\bmod 10\)。

贪心方法一定是从右向左枚举连续段，每次扩展到底。

按照这个思路模拟，如果上一个连续段和当前连续段字符相同，那么只能扩展这两个连续段之间的部分，反之则可以扩展到底，注意零散的和连续段字符相同的位置不计入贡献。

结论是必须满足 \(\max_{i=1}^n \{A_i\}\le \min_{j=1}^m \{B_j\}\)，证明只需要考虑对每个位置，都有 \(A_i\le C_{i,j}\le B_j\)。

之后计数形如给定值域 \(V\)，序列长度 \(n\)，求卡上界或下界的方案数，应当为 \(V^n-(V-1)^n\)。

最后 \(n=1\) 或 \(m=1\) 的情况需要特判，实际上对于每个 \(A\) 或 \(B\)，答案是唯一的，结果是 \(k^{nm}\)。