Atcoder beginner contest 336 -- E -- Digit Sum Divisible --- 题解（数位dp)

目录

E -- Digit Sum Divisibl

题目大意：

思路解析:

代码实现：

E -- Digit Sum Divisibl

题目大意：

给你一个整数n，让你找出小于等于n的数中一共有多少个好整数，并输出好整数的个数。对好整数的个数定义为如果一个数能被他的数位之和整除，则称这个数为好整数。例如 12 能被 3 整除。

n<=10^14。

思路解析:

看到数位之和，应该优先想到数位dp，那么我们想到最大的数位之和应该为14*9=126。则我们可以枚举每个数位之和k，看0-n中间是否有数位之和加起来刚好是k，并且刚好能被k整除。所以我们遍历次数为 126 * 10^14，这是不能接受的，但是对于每一个k来说，其实当中有许多重复遍历情况，所以可以用记忆化搜索来加速遍历行为。

代码实现：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;

public class Main {
    static int[] dig = new int[15];
    static long[][][] dp;
    static int p;
    public static void main(String[] args) throws IOException {
         Scanner input = new Scanner(System.in);
         long n = input.nextLong();
         dp = new long[15][127][127];
         p = 0;
         while (n > 0){
             dig[p++] =(int) (n % 10);
             n /= 10;
         }
         long res = 0;
        for (int k = 1; k <= 126; k++) {
            for (int i = 0; i < 15; i++) {
                for (int j = 0; j < 127; j++) {
                    Arrays.fill(dp[i][j], -1);
                }
            }
            res += dfs(p - 1, 0, 0, k, false);
        }
        System.out.println(res);
    }
    // lim 表示当前位是否有限制，如果lim == false，表示当前位选择没有限制，可以选择 0-9，否则只能选择0-dig[u]
    // u 表示当前抉择到哪一位了‘
    // s 表示抉择到当前位的数位之和为多少，
    // t表示当前数模上k后的余数是多少
    public static long dfs(int u, int s, int t, int k, boolean lim){
        if (u == -1 && t == 0 && s == k) return 1;
        if (u == -1) return 0;
        if (lim && dp[u][s][t] != -1) return dp[u][s][t];
        int x = lim ? 9 : dig[u];
        long ans = 0;
        for (int i = 0; i <= x; i++) {
            ans += dfs(u - 1, s+i, (t * 10 + i) % k, k, i != x || lim);
        }
        if (lim) dp[u][s][t] = ans;
        return ans;
    }
}