AOJ 570: Zig-Zag Numbers

動的計画法を使ってときました。

問題の設定では1以上のものだけがZig-Zag数になるらしいですが、0以上にしても同じです。

const int mod = 10000;

int M,len,dp[510][510][10][2][3];
/*dp[a][b][c][d][e]
 a:左からa桁目
 b:剰余
 c:一番右の数字
 d:与えられた数字と今見てる所まで一致しているなら1
 e:減った→0、増えた→1、一番左の数字→2
*/

int solve(const string &s){
	if(len)memset(dp,0,sizeof(dp));
	len = s.size();
	int res = 0;
	
	for(int i = 0; i < s[0]-48; i++){
		dp[0][i%M][i][0][2]++;
	}
	dp[0][(s[0]-48)%M][s[0]-48][1][2]++;
	
	for(int i = 1; i < len; i++){
		for(int j = 0; j < 10; j++){
			for(int k = 0; k < 10; k++){
				if(!k){
					dp[i][j%M][j][0][2]++;
				}
				
				if(j != k){
					for(int l = 0; l < M; l++){
						int t = (j+l*10)%M;
						dp[i][t][j][0][j<k] = (dp[i][t][j][0][j<k]+dp[i-1][l][k][0][j>k]+(k?dp[i-1][l][k][0][2]:0)) % mod;//kが0のときは、先に処理している
						if(j == s[i]-48){
							dp[i][t][j][1][j<k] = (dp[i][t][j][1][j<k]+dp[i-1][l][k][1][j>k]+dp[i-1][l][k][1][2]) % mod;
						}
						if(j < s[i]-48){
							dp[i][t][j][0][j<k] = (dp[i][t][j][0][j<k]+dp[i-1][l][k][1][j>k]+dp[i-1][l][k][1][2]) % mod;
						}
					}
				}
			}
		}
	}
	
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 10; k++){
				res = (res+dp[len-1][0][k][i][j]) % mod;
			}
		}
	}
	
	return res;
};

int check(const string &s){
	if(!(--len)){
		return !((s[0]-48) % M);
	}
	if(s[0] == s[1]) return 0;
	int m = s[0]-48;
	bool f = s[0]>s[1];
	for(int i = 1; i < len; i++){
		if(f){
			if(s[i]>=s[i+1])return 0;
		}else {
			if(s[i]<=s[i+1])return 0;
		}
		
		f = !f;
		m = (m*10+s[i]-48) % M;
	}
	return !((m*10+s[len]-48) % M);
};

int main(){
	string A,B;
	cin>>A>>B>>M;
	
	cout<<(solve(B)-solve(A)+check(A)+mod) % mod<<endl;
	
	return 0;
}