Submission #5024903

---

Source Code Expand

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

using ll = long long;

const ll MOD = 1000000007;

ll dp[105][100005];
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string n;
    int d;
    cin >> n >> d;
    
    dp[0][0] = 1;
    for (int i = 0; i < n.size(); i++) {
        for (int j = 0; j <= d; j++) {
            int num = 0, tmp = 1;
            for (int k = i; k >= 0; k--) {
                if (n[k] == '0') {
                    (dp[i + 1][j] += dp[k][j - num]) %= MOD;
                } else {
                    if (tmp > 100000) break;
                    num += tmp * (n[k] - '0');
                    if (j < num) break;
                    (dp[i + 1][j] += dp[k][j - num]) %= MOD;
                }
                if (tmp <= 100000) tmp *= 10;
            }
        }
    }
    
    ll ans = 0;
    for (int i = 0; i <= d; i++) {
        (ans += dp[n.size()][i]) %= MOD;
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result