官方题解 | Zombie

G. Zombie

Subtask 6 pt

数据范围较小，直接枚举即可。

Subtask 100 pt

采用倍增上数位 DP 的方法。

我们先看式子：

$$pos_{new}=((pos+f(pos)) \bmod p)+1$$

省略 $+1$，得：

$$pos_{new}=(pos+f(pos)) \bmod p$$

我们发现每次增量不会超过 $9$，因此如果不看个位前面每次的增量不会超过 $1$。也就是说对于除个位之外的每一位我们都是一点点变化的，每次循环每个阶段我们都会经历。于是我们发现个位是特殊的，考虑单独处理。既然其他位置每个阶段都会经历，那我们不妨找到最特殊的阶段——全 $0$（尽管不会出现）。而前面的阶段位数对后面剩下的影响只需要记录最大数码即可。

于是我们考虑定义 $dp1_{i,j,k},dp2_{i,j,k}$ 分别表示 $2\sim i$ 位均为 $0$，$j$ 是 $i+1$ 位及以上的最大数码，个位现在是 $k$ 的状态下，我们想要给 $i+1$ 位加 $1$，并且第一次回到 $2\sim i$ 位均为 $0$ 的状态后个位的值，和需要的步数。

我们发现 $dp1_{i,j,k},dp2_{i,j,k}$ 只需要由 $dp1_{i-1},dp2_{i-1}$ 开始然后枚举 $i−1$ 开始由 $0\to 9$ 的变化即可转移。

接下来我们有 $3$ 步。

1. 对于 $\bmod m$ 的操作，我们先尝试将 $A$ 变为 $0\sim 9$。先变到要跨过 $m$ 之前，我们先用 $dp1_{i,j,k},dp2_{i,j,k}$ 从低位开始一步步加到 $0$ 然后加到不能再加后，再从高位一步步向下加到不能再加。

2. 然后因为我们反复跨过 $m$ 的次数可能很多，于是我们通过 $dp1_{i,j,k},dp2_{i,j,k}$ 预处理数组 $fr_{i,j,k},to_{i,j,k}$ 表示 $0\sim9$ 中的数 $j$ 跨过 $m2^i$ 次后变成的 $0\to9$ 中的哪一个，用多少步，然后我们就可以快速处理跨过 $m$ 了。

3. 接下来我们不会再走一次超过 $m$ 的了，于是我们又按 $Step 1$ 中的方法，从低位开始一步步加到 $0$​ 然后加到不能再加后，再从高位一步步向下加到不能再加。

最后 $+1$ 即可。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp1[20][10][10],dp2[20][10][10],pw[20];
int fr[70][25],to[70][25],num[20],maxx[20];
int solve(int x){
	int maxx = 0;
    while(x){
        maxx = max(maxx,x % 10);
        x /= 10;
    }
	return maxx;
}
signed main(){
    int _; cin >> _;
    while(_--){
    	int a,m,rem; cin >> a >> m >> rem;
    	int mm = m;
        rem--;
    	for(int i = 1;i <= 19;i++){
    		num[i] = mm % 10;
    		mm /= 10;
    	}
    	pw[0] = 1;
    	for(int i = 1;i <= 19;i++) pw[i] = pw[i - 1] * 10;
    	for(int a = 0;a < 10;a++){
            for(int b = 0;b < 10;b++){
        		if(!a && !b){
                    dp2[1][a][b]=LLONG_MAX;
                    continue;
                }
        		dp1[1][a][b] = b;
                dp2[1][a][b] = 0;
        		while(dp1[1][a][b] <= 9){
        			dp1[1][a][b] += max(a,dp1[1][a][b]);
        			dp2[1][a][b]++;
        		}
        		dp1[1][a][b] -= 10;
            }
    	}
    	for(int k = 2;k <= 19;k++){
            for(int a = 0;a < 10;a++){
                for(int b = 0;b < 10;b++){
            		if(!a && !b){
                        dp2[k][a][b] = LLONG_MAX;
                        continue;
                    }
            		int ft = b,gt = 0,t;
            		for(int i = 0;i <= 9;i++){
            			t = ft;
            			ft = dp1[k - 1][max(a,i)][t];
            			gt = min(gt + dp2[k - 1][max(a,i)][t],LLONG_MAX);
            		}
            		dp1[k][a][b] = ft;
            		dp2[k][a][b] = gt;
                }
            }
    	}
    	for(int s = 0;s < 10;s++){
    		if(!s){
                fr[0][s] = 0;
                to[0][s] = 1;
                continue;
            }
    		int ff = s,gg = 0,maxx = 0,t,b = 0;
    		for(int i = 19;i >= 2;i--){
    			for(int j = 0;j <= num[i] - 1;j++){
    				t = ff;
    				ff = dp1[i - 1][max(maxx,j)][t];
    				gg = min(gg + dp2[i - 1][max(maxx,j)][t],LLONG_MAX);
    			}
    			b = b * 10 + num[i];
    			maxx = max(maxx,num[i]);
    		}
    		ff = b * 10 + ff;
    		while(ff < m){
    			ff += solve(ff);
    			gg++;
    		}
    		fr[0][s] = ff % m;
            to[0][s] = gg;
    	}
    	for(int i = 1;i <= 69;i++){
            for(int s = 0;s < 10;s++){
        		int t = fr[i - 1][s];
        		fr[i][s] = fr[i - 1][t];
        		to[i][s] = min(to[i - 1][s] + to[i - 1][t],LLONG_MAX);
            }
    	}
    	while(rem >= 100){
    		if(a <= 9 && to[0][a] <= rem){
    			int k = 0;
    			while(k <= 63 && to[k + 1][a] <= rem) k++;
    			rem -= to[k][a];
    			a = fr[k][a];
    			continue;
    		}
    		if(m - a <= 100){
    			a = (a + solve(a)) % m;
    			rem--;
    			continue;
    		}
    		mm = a;
    		for(int i = 1;i <= 19;i++){
    			num[i] = mm % 10;
    			mm /= 10;
    		}
    		for(int i = 19;i >= 1;i--){
    			if(i != 19) maxx[i] = maxx[i + 1];
                else maxx[i] = 0;
    			maxx[i] = max(maxx[i],num[i]);
    		}
    		int k = 1;
    		int t = a % 10;
    		while(!num[k + 1] && (a / pw[k + 1] + 1) * pw[k + 1] + dp1[k + 1][maxx[k + 2]][t] < m && rem >= dp2[k + 1][maxx[k + 2]][t]) k++;
    		rem -= dp2[k][maxx[k + 1]][t];
    		num[1] = dp1[k][maxx[k + 1]][t];
    		num[k + 1]++;
    		a = 0;
    		for(int i = 19;i >= 1;i--) a = a * 10 + num[i];
    	}
    	while(rem--) a = (a + solve(a)) % m + 1;
    	cout << a << "\n";
    }
	return 0;
}

时间复杂度：$O(T\times\log N)$