Submission #5896662

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
using ll = long long;

const ll MM = 1000000007;
string N;
int D;
ll num[10001][10][101] = {};

int mod(int a, int b){
    if (a<0) {
        int c = int(double(-a)/double(b)) + 1;
        return (a + b * c) % b;
    }
    else return a % b;
}

void solve(int kk) {
    for (int k = 1; k < kk; ++k) {
        for (int j = 0; j < D; ++j) {
            num[k][0][j] = num[k-1][9][j];
        }
        for (int i = 1; i < 10; ++i) {
            for (int j = 0; j < D; ++j) {
                int a = mod(j-i, D);
                int f = i%D == j ? 1 : 0;
                num[k][i][j] = (num[k-1][9][a] + num[k][i-1][j] + f) % MM;
            }
        }
    }
}
int main(int argc, char *argv[])
{
    cin >> D;
    cin >> N;
    if (D==1) {
        cout << N << endl;
        return 0;
    }
    for (int i = 0; i < 10; ++i) {
        for (int j = 1; j < i+1; ++j) {
            num[0][i][j % D] += 1;
        }
    }

    solve(N.size());

    int c = N[0] - '0';
    int a=0;
    ll ans = 0;
        // num[N.size()-1][c-1][0];
    for (int i = 0; i < N.size(); ++i) {
        c = N[i] - '0';
        int sub = 0;
        if (c > 0) {
            sub = num[N.size() - i - 1][c-1][a];
        }
        if(a == 0 && i != 0) {  // xxx000もOk
            sub += 1;
        }
        if (i == N.size()-1 && a+c % D == 0 && i>0)  sub+=1;
        ans = (ans + sub) % MM;
        // printf("c=%d, a=%d, sub=%d", c, a, sub);
        a = mod(a-c, D);
        // printf(" newa=%d\n", a);
    }
    printf("%lld\n", ans);
    return 0;
}

Submission Info

Judge Result