数位dp3

package com.zhang.reflection.面试.算法模版.动态规划;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
 * 给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。
 * 输入文件中仅包含一行两个整数a、b，含义如上所述。
 * 输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。
 */
public class 数字计数 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        long a = Long.parseLong(arr[0]);
        long b = Long.parseLong(arr[1]);
        ten[0] = 1;
        for (int i = 1; i <= 12; i++) {
            f[i] = f[i - 1] * 10 + ten[i - 1];
            ten[i] = 10 * ten[i - 1];
        }

        count(a - 1, cnta);
        count(b, cntb);
        for (int i = 0; i <= 9; i++) {
            System.out.print(cntb[i] - cnta[i] + " ");
        }
    }
    // 1 10 100 1000 ```
    public static long[] ten = new long[13];
    // 0 1 20 300 4000 50000 ```
    public static long[] f = new long[13];
    public static long[] cnta = new long[10];
    public static long[] cntb = new long[10];
    public static void count(long x, long[] cnt) {
        long[] num = new long[13];
        int len = 0;
        while (x != 0) {
            num[++len] = x % 10;
            x = x / 10;
        }
        for (int i = len; i >= 1; i--) {
            for (int j = 0; j <= 9; j++) {
                cnt[j] += f[i - 1] * num[i];
            }
            for (int j = 0; j < num[i]; j++) {
                cnt[j] += ten[i - 1];
            }
            long num2 = 0;
            for (int j = i - 1; j >= 1; j--) {
                num2 = num2 * 10 + num[j];
            }
            cnt[(int) num[i]] += num2 + 1;
            cnt[0] -= ten[i - 1];
        }
    }
}