滴滴笔试

public class 美丽值 {

    /**
     * 老张教授开了一堂美数课！
     * <p>
     * 老张认为每个非负整数x都有一个美丽值b(x)。
     * <p>
     * 一个非负整数的美丽值定义为这个数十进制下每个数位的异或和。即，对于123来说，美丽值为1^2^3=0，
     * 对于654815424美丽值为6^5^4^8^1^5^4^2^4=9 （在C/C++中^运算符表示异或）
     * <p>
     * 现在老张想考考同学，对于[L,R]这个闭区间内的所有整数，美丽值恰好为t的数有多少个。
     * <p>
     * <p>
     * <p>
     * 输入描述
     * 第一行一个正整数，表示有次询问。
     * <p>
     * 接下来有三行：
     * <p>
     * 第一行个非负整数 L1,L2,...,Li,...,LT(1≤i≤T)
     * <p>
     * 第二行个非负整数  R1,R2,...,Ri,...,RT(1≤i≤T)
     * <p>
     * 第三行个非负整数  t1,t2,...,ti,...,tT(1≤i≤T)
     * <p>
     * 每个询问是对于 [Li, Ri] (Li≤Ri)这个闭区间内的所有整数，美丽值恰好为的数有多少个。
     * <p>
     * <p>
     * <p>
     * 输出描述
     * 每个询问输出T个整数，每两个数之间用空格隔开，表示答案。
     * <p>
     * <p>
     * 样例输入
     * 2
     * 0 1
     * 0 10
     * 0 1
     * 样例输出
     * 1 2
     * <p>
     * 提示
     * <p>
     * <p>
     * 一共两次询问。
     * <p>
     * 第1次询问 [0, 0] 这个区间中美丽值为0的有多少个，0的美丽值为0，答案为1。
     * <p>
     * 第2次询问 [1, 10] 这个区间中美丽值为1的有多少个，1和10的美丽值为1，答案为2。
     */
    static int N = 5;
    static int T = 15;
    //dp[i,j,k] 表示一共i位，最高位是j，异或和为k
    private static final long[][][] dp = new long[N + 1][10][T + 1];

    static void init() {
        for (int j = 0; j <= 9; j++) {
            dp[1][j][j] = 1;
        }

        //   很容易疏忽的位置，容易把第三维度开太大导致超时，要对2进制加强敏感程度
        //   每一位都是[1,9] 最大的异或和不超过4位全1=> (1111)2 => 15
        //   j x _ _ _ _ _
        //   从x到最后一位一共i-1位，从j到最后一位共i位
        //   dp[i,j,k] += dp[i-1,x,k^j]
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= 9; j++) {
                for (int x = 0; x <= 9; x++) {
                    for (int k = 0; k <= T; k++) {
                        dp[i][j][k] += dp[i - 1][x][k ^ j];
                    }
                }
            }
        }
    }

    static {
        init();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] l = new int[n];
        int[] r = new int[n];
        int[] t = new int[n];
        for (int i = 0; i < n; i++) {
            l[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            r[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            t[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            System.out.print(f(r[i], t[i]) - f(l[i] - 1, t[i]) + " ");
        }

    }


    /**
     * f(n,t): [0,n] 所有的数的美丽值为t的个数
     * 因为所有测试用例可以共享dp，dp初始化全局共享
     * 技巧1：依赖于java底层：在类加载的时机jvm会对static属性就完成显式赋值，执行static代码块 这个过程只会发生一次且按照代码顺序执行
     * 技巧2：我所知道OJ平台测试时都是类加载一次，然后每个用例会new一个对象，调用测评方法 这样可以利用构造代码块的特性 每次 new对象 先执行构造块 最后执行构造方法
     * leetcode acwing 蓝桥系统 acmcoder皆适用
     * 复杂度分析：
     * 初始化dp: 10*10*16*4*logN
     * f(n,t):  log(n)
     * 总复杂度为:  log(n) ~ 6400*logN
     */
    private static long f(int n, int t) {
        if (n < 0)
            return 0;
        if (n == 0) {
            return dp[1][n][t];
        }
        ArrayList<Integer> nums = new ArrayList<>();
        while (n != 0) {
            nums.add(n % 10);
            n /= 10;
        }
        long res = 0;
        int mask = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            for (int j = 0; j < x; j++) {
                res += dp[i + 1][j][t ^ mask];
            }
            mask ^= x;
            // 特判顺利到达最后一位 并且所有的位异或和正好为 t
            if (i == 0 && mask == t)
                res++;
        }
        return res;
    }
}