AOJ0570 Zig-Zag Numbers

AOJ Volume5

問題リンク Zig-Zag Numbers

  • 解法

DPもといメモ化探索で解きました。
扱う数値の範囲が異常に広く、更にその中のMの倍数にしか興味がないというのが厄介なところです。500桁近いある値がMの倍数かを判定するのもままならないかもしれません(自分がそうでした)。

まず、ある数値がMの倍数かを調べる方法を説明します。
数値VがMの倍数かを判定するためには左から1桁ずつ見ていくことで判定可能です。
(A*X + B) mod M ≡ ( (A*X mod M) + (B mod M) ) mod M
という合同式をうまく利用します。
429が13の倍数かどうか調べるためには、まず4%13を計算し、4を得ます。
得られた4を10倍して2を足し、13との剰余を取ります。( (4*10 mod 13) + (2 mod 13) ) mod 13 = 3
得られた3を10倍して9を足し、13との剰余を取ります。( (3*10 mod 13) + (9 mod 13) ) mod 13 = 0
よって429は13の倍数と分かります。これは 429を42*10 + 9に分解し、更に42を4*10 + 2に分解して解いたのと同じことです。

次は1〜Xの中でMの倍数であるようなジグザグ数の個数をmod 10000で返すメソッドf(X)の説明です。このメソッドを作ると、解は f(B) - f(A-1)と求まります。
f(X)を求めるには再帰関数を使い、左側の桁から1つずつ数字を決めていく方法をとります。
先頭の数字と、その次にくる数字はそれより大きいかどうかを決めていきます。大きいか小さいかは呼び出しごとに交互になります。更にk桁目に使える数字の範囲が自由に使えるかどうかも情報としてもっておきます。たとえば、
X = 429のとき、
4 _ _ と決めたら次は0〜2までしか使えませんが、
3 _ _ と決めたら次はどのような数字を使ってもXを超えないので0〜9まで使える
という具合です。
更に気をつけるのが、先頭から0が連続しているときです。このときはまだジグザグが開始されていないので直前の桁と同じ数字である0がまだ使えます。
直前の桁までの剰余がmで、k桁目に数字pを採用した場合、上述したように
(m*10 + p) % M
が次の桁へ渡す剰余の値になります。
最後の桁を埋めきった後、この値が0になっていたらMの倍数でかつX以下のジグザグ数を見つけたことになります。
プログラムでは

dp[k][f][u][p][m]:
現在k桁目を決めようとしていて、
k桁目にあらゆる数字が使えるならf=1, そうでないならf=0
k桁目は直前の桁の数字 p より大きくなければならないならu=1、そうでないならu=0
k桁目に渡された剰余の値 m
のとき、k桁に数字を設定して得られるジグザグ数の個数

という表を埋めています。
再帰関数には更に、0が連続しているかの真偽値 zero も使っています。
f(B) < f(A-1)となる可能性があるので答えには
(f(B)-f(A-1)+M) % M
としないとダメです。

  • ソース
import java.math.BigInteger;
import java.util.Scanner;

//Zig-Zag Numbers
public class AOJ0570 {

	int[] s;
	int n, MOD, M = 10000;
	//idx, free, isUp, pre, M
	int[][][][][] dp;
	
	int get(int k, int f, int u, int pre, int m, boolean zero){
		if(k==n)return zero?0:m==0?1:0;
		int res = 0;
		if(zero){
			res+=get(k+1,f,u,0,0,true);
			for(int p=1;p<10;p++){
				res+=get(k+1,f,0,p,p%MOD,false);
				if(k+1!=n)res+=get(k+1,f,1,p,p%MOD,false);
			}
			return res%M;
		}
		if(dp[k][f][u][pre][m]!=-1)return dp[k][f][u][pre][m];
		if(f==1){
			if(u==1){
				for(int p=pre+1;p<10;p++){
					res+=get(k+1,f,1-u,p,(m*10+p)%MOD,false);
				}
			}
			else{
				for(int p=0;p<pre;p++){
					res+=get(k+1,f,1-u,p,(m*10+p)%MOD,false);
				}
			}
		}
		else{
			if(u==1){
				for(int p=pre+1;p<=s[k];p++){
					if(p==s[k])res+=get(k+1,0,1-u,p,(m*10+p)%MOD,false);
					else res+=get(k+1,1,1-u,p,(m*10+p)%MOD,false);
				}
			}
			else{
				int t = Math.min(pre-1, s[k]);
				for(int p=0;p<=t;p++){
					if(p==s[k])res+=get(k+1,0,1-u,p,(m*10+p)%MOD,false);
					else res+=get(k+1,1,1-u,p,(m*10+p)%MOD,false);
				}
			}
		}
		return dp[k][f][u][pre][m] = res%M;
	}
	
	int f(String r){
		n = r.length();
		s = new int[n];
		for(int i=0;i<n;i++)s[i]=r.charAt(i)-'0';
		dp = new int[n+1][2][2][10][MOD];
		for(int i=0;i<=n;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int p=0;p<10;p++)for(int m=0;m<MOD;m++)dp[i][j][k][p][m]=-1;
		int res = 0;
		res += get(1, 1, 0, 0, 0, true);
		for(int p=1;p<=s[0];p++){
			if(p==s[0]){
				res+=get(1,0,0,p,p%MOD,false);
				if(n!=1)res+=get(1,0,1,p,p%MOD,false);
			}
			else{
				res+=get(1,1,0,p,p%MOD,false);
				if(n!=1)res+=get(1,1,1,p,p%MOD,false);
			}
		}
		return res%M;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		String A = sc.nextBigInteger().subtract(BigInteger.ONE).toString(), B = sc.next();
		MOD = sc.nextInt();
		System.out.println((f(B)-f(A)+M)%M);
	}
	
	public static void main(String[] args) {
		new AOJ0570().run();
	}
}