Submission #1797229

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

typedef long long ll;
#define MOD 1000000007
#define MAX_len 10001
#define MAX_D 100
#define modp(x,y) ((x % y) + y) % y

int main(int argc, const char * argv[]) {
    // dp[i][p] : Nの先頭から(i+1)文字目までの(i+1)桁の整数以下で, 各桁の総和がp(mod D)となる非負整数の個数(mod MOD)
    ll dp[MAX_len][MAX_D];
    // c[i] : Nの先頭から(i+1)文字目までの(i+1)桁の総和(mod D)
    int c[MAX_len];
    
    int D;
    cin >> D;
    string str;
    cin >> str;
    
    int len = int(str.size());
    
    int N[MAX_len];
    for (int i = 0; i < len; i++) {
        N[i] = int(str[i]) - int('0');
    }
    
    for (int i = 0; i < len; i++) {
        if (i == 0) c[i] = N[i] % D;
        else c[i] = modp(c[i-1] + N[i], D);
    }
    
    for (int i = 0; i < len; i++) {
        for (int p = 0; p < D; p++) {
            if (i == 0) {
                for (int n = 0; n < N[i]+1; n++) {
                    if (modp(n, D) == p) dp[i][p]++;
                }
            } else {
                long long sum = 0;
                for (int n = 0; n < 10; n++) {
                    sum += dp[i-1][modp((p-n),D)];
                }
                for (int n = N[i] + 1; n < 10; n++) {
                    if ((c[i-1] + n) % D == p) sum = modp(sum - 1, MOD);
                }
                dp[i][p] = sum % MOD;
            }
        }
    }
    
    cout << modp(dp[len-1][0] - 1, MOD) << endl;
    return 0;
}

Submission Info

Judge Result