HDU5898數位DP

求區間[L，R]，滿足：

連續奇數個數為偶數  或者 

連續偶數個數為奇數 

的個數。

注意字首為0的特殊情況

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		new P1007().main();
	}
}

class P1007 {
	final int Max_N = 20;
	final int ODD = 1;
	final int EVEN = 0;
	final BigInteger ten = BigInteger.valueOf(10);

	long[][][] dp = new long[Max_N][2][Max_N];
	int[] bit = new int[Max_N];

	boolean isEven(int x) {
		return (x & 1) == 0;
	}

	boolean isOdd(int x) {
		return (x & 1) == 1;
	}

	long DP(int pos, int pre, int bitSum, boolean isend) {
		if (pos == -1) {
			if (pre == EVEN)
				return isOdd(bitSum) ? 1L : 0L;
			else
				return isEven(bitSum) ? 1L : 0L;
		}
		if (pre != -1 && !isend && dp[pos][pre][bitSum] != -1)
			return dp[pos][pre][bitSum];
		int d = isend ? bit[pos] : 9;
		long ans = 0;
		for (int i = 0; i <= d; i++) {
			if (pre == -1) {
				if (i == 0)
					ans += DP(pos - 1, -1, bitSum, isend && (i == d));
				else if (isEven(i))
					ans += DP(pos - 1, EVEN, bitSum + 1, isend && (i == d));
				else
					ans += DP(pos - 1, ODD, bitSum + 1, isend && (i == d));
			} else if (pre == EVEN) {
				if (isEven(i))
					ans += DP(pos - 1, EVEN, bitSum + 1, isend && (i == d));
				else {
					if (isEven(bitSum)) {
						ans += 0;
					} else
						ans += DP(pos - 1, ODD, 1, isend && (i == d));
				}
			} else if (pre == ODD) {
				if (isOdd(i))
					ans += DP(pos - 1, ODD, bitSum + 1, isend && (i == d));
				else {
					if (isOdd(bitSum)) {
						ans += 0;
					} else
						ans += DP(pos - 1, EVEN, 1, isend && (i == d));
				}
			}
		}
		if (pre != -1 && !isend)
			dp[pos][pre][bitSum] = ans;
		return ans;
	}

	long Ans(BigInteger x) {
		int Len = 0;
		while (x.compareTo(BigInteger.ZERO) > 0) {
			bit[Len++] = x.mod(ten).intValue();
			x = x.divide(ten);
		}
		return DP(Len - 1, -1, 0, true);
	}

	InputReader in = new InputReader(System.in);
	PrintWriter out = new PrintWriter(System.out);

	void main() {
		for (int i = 0; i < Max_N; i++) {
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < Max_N; k++) {
					dp[i][j][k] = -1;
				}
			}
		}
		BigInteger l, r;
		int t = in.nextInt();
		for (int ca = 1; ca <= t; ca++) {
			out.print("Case #" + ca + ": ");
			l = in.nextBigInteger();
			r = in.nextBigInteger();
			long sr = Ans(r);
			long sl = Ans(l.subtract(BigInteger.ONE));
			out.println(sr - sl);
		}
		out.flush();
	}
}

class InputReader {
	public BufferedReader reader;
	public StringTokenizer tokenizer;

	public InputReader(InputStream stream) {
		reader = new BufferedReader(new InputStreamReader(stream), 32768);
		tokenizer = new StringTokenizer("");
	}

	private void eat(String s) {
		tokenizer = new StringTokenizer(s);
	}

	public String nextLine() {
		try {
			return reader.readLine();
		} catch (Exception e) {
			return null;
		}
	}

	public boolean hasNext() {
		while (!tokenizer.hasMoreTokens()) {
			String s = nextLine();
			if (s == null)
				return false;
			eat(s);
		}
		return true;
	}

	public String next() {
		hasNext();
		return tokenizer.nextToken();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public BigInteger nextBigInteger() {
		return new BigInteger(next());
	}

}