Digit Sum Divisible の解説

桁和を固定して考える。

dp[i][j][k][l] := 上からi桁目まで考えたとき、今のところの桁和がj, 総和 % 桁和がk, スデイカフラグがlのときの場合の数

桁和はmaxで9 * 14なので、dpのサイズは (9 * 14) ^ 3 * 2 * 14 = 56,010,528これのdpテーブルの処理内部で次の数字を0..=9で総当りでためすので、5 * 10^8くらいの計算量。

実行時間がかなり余裕あるので、かなり余裕で通る(Rustで300msくらい)

fn main() {
    input! {
        n: usize,
    }
    let amaxnum = n.to_string().len() * 9;
    let ln = n.to_string().len();

    let nc = n.to_string().chars().map(|e| e.to_digit(10).unwrap() as usize).collect_vec();
    
    let mut ans = 0;
    for ketawa in 1..=amaxnum {
        let mut dp = vec![vec![vec![vec![0usize; 2]; ketawa]; ketawa + 1]; ln + 1];
        dp[0][0][0][1] = 1;

        for i in 0..ln {
            for j in 0..ketawa + 1 {
                for k in 0..ketawa {
                    for l in 0..2 {
                        if dp[i][j][k][l] == 0 {
                            continue;
                        }
                        let target = nc[i];
                        let now = dp[i][j][k][l];
                        for next in 0..=9 {
                            if l == 1 && next > target {
                                continue;
                            }
                            if j + next > ketawa {
                                continue;
                            }
                            let nl = if l == 1 && next == target {1} else {0};
                            dp[i + 1][j + next][(k * 10 + next) % ketawa][nl] += now;
                        }
                    }
                }
            }
        }
        ans += dp[ln][ketawa][0].iter().sum::<usize>();
    }
    println!("{}", ans);
}