下から桁DPする場合の別解です。まずすべての数字にleading zero を加えることで15桁に固定して考えることにします。\(N\)についてもleading zeroを加え15桁にしたものとして考えます。また\(N=n_{15}n_{14}n_{13}...n_2n_1\)と置きます。

つぎに\(dp_{d,s, i,j,f}\)を

• \(dp_{d,s,i,j,f}:=\)(下から\(d\)桁目まで決めたとき、予定している桁和が\(s\)、現在の桁和が\(i\)、現在の値の\(\mod s\)が\(j\)、\(f=0\)なら\(n_d...n_1\)以下、\(f=1\)なら\(n_d...n_1\)より大きい)

とします。このとき答えは、すべての数字をleading zeroで補ったことに注意すると

\[ \sum_{s=1}^{s=9\times 14} dp_{15,s,s,0,0}\]

となります。

遷移を考えます。\(d+1\)桁目を\(t\)としたときの新たな大小関係を\(nf\)とします。また\(N\)の\(d+1\)桁目を\(n_{d+1}\)とします。このとき\(nf\)は場合分けによって決定することもできますが、式にすると

\[ nf=2 \times n_{d+1}< 2 \times t + f \]

となります。 よって\(dp_{d,s,i,j,f}\)からの遷移は

\[dp[d+1][s][i+t][(10 ^ {d+1}\times t+j) \mod s][nf]+=dp[d][s][i][j][f]\]

となります。計算量は公式解説と同じで、\(B=10\)として全体で\(\Omicron((B \log N)^4)\)です。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll N, dp[16][130][130][130][2];
int main() {
    cin >> N;
    // 初期化
    for (int s = 1; s <= 9 * 14; s++) dp[0][s][0][0][0] = 1;

    // 遷移
    ll pow10 = 1;
    for (int d = 0; d < 15; d ++) {
        int n = N % 10;
        for (int s = 1; s <= 9 * 14; s++) {
            for (int i = 0; i <= 9 * 14; i++) {
                for (int j = 0; j < s; j++) {
                    for (int f = 0; f < 2; f++) {
                        for (int t = 0; t < 10; t++) {
                            if (i + t > s) break;
                            int nf = 2 * n < 2 * t + f;
                            dp[d + 1][s][i + t][(pow10 * t + j) % s][nf] += dp[d][s][i][j][f];
                        }
                    }
                }
            }
        }
        N /= 10;
        pow10 *= 10;
    }

    // 答えの計算
    ll ans = 0;
    for (int s = 1; s <= 9 * 14; s++) ans += dp[15][s][s][0][0];
    cout << ans << '\n';
}

実際の提出