D - 禁止された数字 AtCoder Beginner Contest 007

問題概略
A~Bの中で4か9が含まれる物の個数を答えよ。

制約
A,B <=10^18

解法
4か9が一つでも含まれてればいいなら包除原理使うか！と思ったけど、大変そうなので桁DPで解いた。
まとめ上げるのに必要な条件は　
何桁目を見ているか
数が上限ギリギリかどうか
すでに4,9を使っているか
の3つとしてメモ化再帰で解いた。

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        A = nl();
        B = nl();
        System.out.println(task(B) - task(A - 1));
    }

    public static long rec(int k, int ti, int bad) {
        if (k == N) {
            if (bad == 1) return 1;
            else return 0;
        } else if (dp[k][ti][bad] != -1) {
            return dp[k][ti][bad];
        }
        long sum = 0;
        int maxn = ti == 1 ? v[k] : 9;
        for (int i = 0; i <= maxn; i++) {
            int t = i == maxn ? ti : 0;
            int b = i == 4 || i == 9 ? 1 : bad;
            sum += rec(k + 1, t, b);
        }
        return dp[k][ti][bad] = sum;
    }

    public static long task(long n) {
        N = keta(n);
        v = toIntArray(n);
        dp = new long[N + 1][2][2];
        fill(dp, -1);
        return rec(0, 1, 0);
    }