G. ZOMBIE SUBTASK 6 PT 数据范围较小，直接枚举即可。 SUBTASK 100 PT 采用倍增上数位 DP 的方法。 我们先看式子： posnew=((pos+f(pos)) mod p)+1pos_{new}=((pos+f(pos)) \bmod p)+1 posnew =((pos+f(pos))modp)+1 省略 +1+1+1，得： posnew=(pos+f(pos)) mod ppos_{new}=(pos+f(pos)) \bmod p posnew =(pos+f(pos))modp 我们发现每次增量不会超过 999，因此如果不看个位前面每次的增量不会超过 111。也就是说对于除个位之外的每一位我们都是一点点变化的，每次循环每个阶段我们都会经历。于是我们发现个位是特殊的，考虑单独处理。既然其他位置每个阶段都会经历，那我们不妨找到最特殊的阶段——全 000（尽管不会出现）。而前面的阶段位数对后面剩下的影响只需要记录最大数码即可。 于是我们考虑定义 dp1i,j,k,dp2i,j,kdp1_{i,j,k},dp2_{i,j,k}dp1i,j,k ,dp2i,j,k 分别表示 2∼i2\sim i2∼i 位均为 000，jjj 是 i+1i+1i+1 位及以上的最大数码，个位现在是 kkk 的状态下，我们想要给 i+1i+1i+1 位加 111，并且第一次回到 2∼i2\sim i2∼i 位均为 000 的状态后个位的值，和需要的步数。 我们发现 dp1i,j,k,dp2i,j,kdp1_{i,j,k},dp2_{i,j,k}dp1i,j,k ,dp2i,j,k 只需要由 dp1i−1,dp2i−1dp1_{i-1},dp2_{i-1}dp1i−1 ,dp2i−1 开始然后枚举 i−1i−1i−1 开始由 0→90\to 90→9 的变化即可转移。 接下来我们有 333 步。 1. 对于  mod m\bmod mmodm 的操作，我们先尝试将 AAA 变为 0∼90\sim 90∼9。先变到要跨过 mmm 之前，我们先用 dp1i,j,k,dp2i,j,kdp1_{i,j,k},dp2_{i,j,k}dp1i,j,k ,dp2i,j,k 从低位开始一步步加到 000 然后加到不能再加后，再从高位一步步向下加到不能再加。 2. 然后因为我们反复跨过 mmm 的次数可能很多，于是我们通过 dp1i,j,k,dp2i,j,kdp1_{i,j,k},dp2_{i,j,k}dp1i,j,k ,dp2i,j,k 预处理数组 fri,j,k,toi,j,kfr_{i,j,k},to_{i,j,k}fri,j,k ,toi,j,k 表示 0∼90\sim90∼9 中的数 jjj 跨过 m2im2^im2i 次后变成的 0→90\to90→9 中的哪一个，用多少步，然后我们就可以快速处理跨过 mmm 了。 3. 接下来我们不会再走一次超过 mmm 的了，于是我们又按 Step1Step 1Step1 中的方法，从低位开始一步步加到 000 然后加到不能再加后，再从高位一步步向下加到不能再加。 最后 +1+1+1 即可。 AC CODE 时间复杂度：O(T×log⁡N)O(T\times\log N)O(T×logN)