Submission #1797216

---

Source Code Expand

#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;
    scanf("%d", &D);
    char str[MAX_len];
    scanf("%s", str);
    
    int len = int(strlen(str));
    
    int N[MAX_len];
    for (int i = 0; i < MAX_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;
            }
        }
    }
    
    
    printf("%lld\n", modp(dp[len-1][0] - 1, MOD));
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main(int, const char**)’:
./Main.cpp:24:29: error: ‘strlen’ was not declared in this scope
     int len = int(strlen(str));
                             ^
./Main.cpp:20:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &D);
                    ^
./Main.cpp:22:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", str);
                     ^