EDPC S - Digit Sum - かんプリンの学習記録

問題はこちら

問題概要
解説

問題概要

${1}$ 以上 ${K}$ 以下の整数のうち，十進表記における各桁の数字の総和が ${D}$ の倍数であるようなものはいくつか．

${1\leq K < 10^{10000}}$
${1\leq D\leq 100}$

解説

桁DPというものを用いると解くことができます．実装方法には様々な種類があるので代表的なものについて解説を行います．桁DPの概念については他の分かりやすい記事を参考にしてください．

以下のけんちょんさんの記事がおすすめです。

drken1215.hatenablog.com

以下， ${K}$ の上から ${i}$ 桁目の数を ${K_i}$ ， ${K}$ の桁数を ${L}$ と表します．

未満フラグを持つDP

${dp[i][j][k]=}$ 「上位 ${i}$ 桁まで決めたとき，桁和を ${D}$ で割った余りが ${j}$ となるようなものの数( ${k}$ は決めた数が ${K}$ 未満であることが確定しているかのフラグ)」とします．
${dp[i][j][0]}$ からの遷移は以下のものがあります．

${dp[i+1][(j+x)\%D][0]}$ ( ${i+1}$ 桁目の数 ${x}$ として ${x=K_{i+1}}$ を選んだ場合)
${dp[i+1][(j+x)\%D][1]}$ ( ${i+1}$ 桁目の数 ${x}$ として ${0\leq x < K_{i+1}}$ を選んだ場合)

${dp[i][j][1]}$ からの遷移は以下のものがあります．

${dp[i+1][(j+x)\%D][1]}$ ( ${i+1}$ 桁目の数 ${x}$ として ${0\leq x\leq 9}$ を選んだ場合)

これをそのまま書けば求めることができます．

Pythonプログラム

K = input()
D = int(input())
L = len(K)
DP = [[[0]*2 for _ in range(D)] for _ in range(L+1)]
MOD = 10**9+7

DP[0][0][0] = 1
for i in range(L):
    for j in range(D):
        for x in range(10):
            if x == int(K[i]):
                DP[i+1][(j+x)%D][0] += DP[i][j][0]
                DP[i+1][(j+x)%D][0] %= MOD
            if x < int(K[i]):
                DP[i+1][(j+x)%D][1] += DP[i][j][0]
                DP[i+1][(j+x)%D][1] %= MOD
            DP[i+1][(j+x)%D][1] += DP[i][j][1]
            DP[i+1][(j+x)%D][1] %= MOD
            
print((DP[L][0][0]+DP[L][0][1]-1)%MOD)

未満フラグを持たない方法

${dp[i][j]=}$ 「上位 ${i}$ 桁まで決めたとき，桁和を ${D}$ で割った余りが ${j}$ となるようなもののうち ${K}$ より小さいことが確定しているものの数」とします．

${dp[i][j]}$ からは ${dp[i+1][(j+x)\%D](0\leq x\leq 9)}$ への遷移があります．
また， ${i}$ 桁目で初めて ${K}$ より小さいことが確定するような数( ${i-1}$ 桁まで ${K}$ と同じで， ${i}$ 桁目が ${K_{i}}$ より小さい数)の分も考える必要があります．
${dp[L][0]}$ は ${0\leq x < K}$ を満たす ${x}$ について桁和が ${D}$ の倍数であるものの数となるので，これから ${0}$ の分を引いて ${K}$ の分を確認して足せば答えが求まります．

Pythonプログラム

K = input()
D = int(input())
L = len(K)
DP = [[0] * D for _ in range(L+1)]
MOD = 10**9+7
 
S = 0
for i in range(L):
    for x in range(10):
        for j in range(D):
            DP[i+1][(j+x)%D] += DP[i][j]
            DP[i+1][(j+x)%D] %= MOD
        if 0 <= x < int(K[i]):
            DP[i+1][(S+x)%D] += 1
            DP[i+1][(S+x)%D] %= MOD
    S += int(K[i])
 
if S%D == 0:
    print(DP[L][0])
else:
    print((DP[L][0]-1)%MOD)

今回の問題はLeadingZeroがあったとしても(0は和の単位元なので)問題なく数えられますが，LeadingZeroがあってはならない問題もあります．*1
この場合はDPを上位 ${i}$ 桁まで決めたとき以下の条件を満たすものの数と定義すればよいです．

${N}$ より小さいことが確定している
すべての桁が ${0}$ ではない( ${000...0}$ でない)

すると，以下のように分けられます．

${dp[i][j]}$ から ${dp[i+1][(j+x)\%D](0\leq x\leq 9)}$ への遷移
${i}$ 桁目で初めて ${K}$ より小さいことが確定するような数( ${i-1}$ 桁まで ${K}$ と同じ)
${i}$ 桁目で初めて ${0}$ でない数が現れるような数．

最後に ${K}$ の分を確認して足せば答えが求まります．

Pythonプログラム

K = input()
D = int(input())
L = len(K)
DP = [[0] * D for _ in range(L+1)]
MOD = 10**9+7

for i in range(1,int(K[0])):
    DP[1][i%D] += 1
    DP[1][i%D] %= MOD

S = int(K[0])
for i in range(1,L):
    for x in range(10):
        for j in range(D):
            DP[i+1][(j+x)%D] += DP[i][j]
            DP[i+1][(j+x)%D] %= MOD
        if 0 <= x < int(K[i]):
            DP[i+1][(S+x)%D] += 1
            DP[i+1][(S+x)%D] %= MOD
        if 1 <= x:
            DP[i+1][x%D] += 1
            DP[i+1][x%D] %= MOD
    S += int(K[i])

if S%D == 0:
    print((DP[L][0]+1)%MOD)
else:
    print(DP[L][0])

メモ化再帰

${f(x,d):=}$ ${0}$ 以上 ${x}$ 以下の整数のうち，桁和を ${D}$ で割った余りが ${d}$ となるものの数

とします． ${1}$ の位の数字を ${k}$ としたときの場合分けをします．

${k\leq (x\bmod{10})}$ のとき

　 ${f(\lfloor x/10\rfloor, (d-k)\bmod{D})}$

${(x\bmod{10}) < k}$ のとき

　 ${f(\lfloor x/10\rfloor-1, (d-k)\bmod{D})}$
となるので再帰で解くことができます。
実は ${f(K,*)}$ を計算するために再帰していく際，第 ${1}$ 引数には「 ${K}$ の上位 ${i}$ 桁」か「 ${K}$ の上位 ${i}$ 桁 ${-1}$ 」の形の数しか現れません．
したがって，全体で ${O(D\log{K})}$ しかかかりません．

C++プログラム

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

constexpr int MOD = 1e9 + 7;

unordered_map<ll,ll> memo;
string K;
int D;

// 0以上K[:x](tight?以下:未満)の整数のうち，桁和をDで割った余りがdとなるものの数
ll solve(int x, int tight, int d) {
    if (memo.count(x*D*2+tight*D+d)) return memo[x*D*2+tight*D+d];
    if (x == -1 && tight == 1 && d == 0) return 1;
    else if (x == -1) return 0;
    ll res = 0;
    int k = K[x]-'0'-1+tight;
    for (int i = 0; i <= k; i++) {
        res += solve(x-1,1,((d-i)%D+D)%D);
        res %= MOD;
    }
    for (int i = k+1; i < 10; i++) {
        res += solve(x-1,0,((d-i)%D+D)%D);
        res %= MOD;
    }
    return memo[x*D*2+tight*D+d] = res;
}

int main() {
    cin >> K >> D;
    cout << (solve(K.size()-1,1,0)+MOD-1)%MOD << endl; // 0の分引く
    return 0;
}

以下の記事も参考になります．
maspypy.com

場合分け

${1}$ 以上 ${K}$ 以下の整数 ${x}$ は以下の ${4}$ つのグループのうち，ちょうど ${1}$ グループに属します．

${K}$ と上位 ${k}$ 桁が一致する ${L}$ 桁の整数( ${1\leq k < L}$ )
${K}$ と ${1}$ 桁目が異なる ${L}$ 桁の整数
${k}$ 桁の整数( ${1\leq k < L}$ )
${K}$ そのもの

それぞれのグループに属する整数のうち，桁和 ${D}$ で割った余りが ${0}$ となるものの数を数えます．
このとき，以下の値が必要になるのであらかじめ基本的なDPにより求めておきましょう．

${N,d}$ が与えられる．
整数列 ${\{a_1,a_2,\dots,a_N\}}$ のうち， ${0\leq a_i\leq 9(1\leq i\leq N)}$ かつ ${\sum_{i=1}^{N}a_i\equiv d\bmod{D}}$ となるものの数 ${f(N,d)}$ を求めよ．

それぞれ以下のように求められます．

${K}$ と上位 ${k}$ 桁が一致する ${L}$ 桁の整数( ${1\leq k < L}$ )

${x_i=K_i(i\leq k)}$ かつ ${0\leq x_i < K_i(i= k+1)}$ かつ ${0\leq x_i\leq 9(k+1 < i)}$ となるので，
${f(L-k-1,-x_{k+1}-\sum_{i\leq k}K_i)}$ が答えになります．

${K}$ と ${1}$ 桁目が異なる ${L}$ 桁の整数

${1\leq x_1 < K_1}$ かつ ${0\leq x_i\leq 9(1 < i)}$ となるので，
${f(L-1,-x_1)}$ が答えになります．

${k}$ 桁の整数( ${1\leq k < L}$ )

${x_i=0(i\leq L-k)}$ かつ ${1\leq x_i\leq 9(i=L-k+1)}$ かつ ${0\leq x_i\leq 9(L-k+1 < i)}$ となるので，
${f(k-1,-x_{L-k+1})}$ が答えになります．

${K}$ そのもの

${x_i=K_i(i\leq L)}$ となるので，
${f(0,-\sum_{i\leq L}K_i)}$ が答えになります．

Pythonプログラム

K = input()
D = int(input())
L = len(K)
F = [[0] * D for _ in range(L+1)]
MOD = 10**9+7
ans = 0

# f(N,d)の計算
F[0][0] = 1
for i in range(L):
    for j in range(D):
        for x in range(10):
            F[i+1][(j+x)%D] += F[i][j]
            F[i+1][(j+x)%D] %= MOD

S = 0
for k in range(1,L):
    S += int(K[k-1])
    S %= D
    for xk in range(int(K[k])):
        SS = (S + xk) % D
        ans += F[L-k-1][(D-SS)%D]
        ans %= MOD

for x1 in range(1,int(K[0])):
    ans += F[L-1][(D-x1)%D]
    ans %= MOD

for k in range(1,L):
    for xk in range(1,10):
        ans += F[k-1][(D-xk%D)%D]
        ans %= MOD

S += int(K[-1])
if S % D == 0:
    ans += 1

print(ans)