dynamic-programming - 数値の合計に対する桁の動的計画問題

Question

範囲 [1, N] 内のすべての正の整数の合計を、指定された桁の合計 d で見つけたいと考えています。たとえば、n = 100 で d = 7 の場合、答えは 7 + 16 + 25 + 34 + 43 + 52 + 61 + 70 = 308 になります。

次のコードを使用して、範囲 [1, N] 内の数値を、指定された桁の合計 d で数えることができます。

cnt[i][0][s] は、インデックス i から始まる形成可能なサフィックスの数を示し、その数字の合計は s になります。

cnt[i][1][s] インデックス i から始まる形成可能なサフィックスの数。形成されたサフィックスが入力文字列の対応するサフィックスより大きくならないように、数字の合計は s になります

#include <bits/stdc++.h>

using namespace std;

typedef long long int i64;

i64 cnt[20][2][200];

void digit_sum_dp(string ss) {
    int n = ss.size();

    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 200; k++) {
                cnt[i][j][k] = 0;
            }
        }
    }

    cnt[n][0][0] = 1;
    cnt[n][1][0] = 1;
 
    for (int i = n - 1; i >= 0; i--) {
        for (int tight = 0; tight < 2; tight++) {
            for (int sum = 0; sum < 200; sum++) {
                if (tight) {
                    for (int d = 0; d <= ss[i] - '0'; d++) {
                        if (d == ss[i] - '0') {
                            cnt[i][1][sum] += cnt[i + 1][1][sum - d];
                        } else {
                            cnt[i][1][sum] += cnt[i + 1][0][sum - d];
                        }
                    }
                } else {
                    for (int d = 0; d < 10; d++) {
                        cnt[i][0][sum] += cnt[i + 1][0][sum - d];
                    }
                }
            }
        }
    }
    return cnt[0][1][d];
}

int main() {
    string str = "100";
    int d = 7;
    cout << digit_sum_dp(str, d) << "\n";
    return 0;
}

コードを拡張して、数値のカウントではなく数値の合計を見つけようとしました。以下はコード スニペットです。

cnt[i][1][sum] += cnt[i + 1][1][sum - d];
tot[i][1][sum] += (d * cnt[i + 1][1][sum - d] + tot[i + 1][1][sum - d] * pow(10, i));

一部の入力で誤った結果が得られます。誰かが私を助けることができれば、私は感謝します。