Submission #1240757


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




int mod = 1000000007;
int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
template<class... T> int add(int x, T... y) { return add(x, add(y...)); }
int mul(int x, int y) { return 1LL * x * y % mod; }
template<class... T> int mul(int x, T... y) { return mul(x, mul(y...)); }
int sub(int x, int y) { return add(x, mod - y); }
int modpow(int a, long long b) { int ret = 1; while (b > 0) { if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod; b >>= 1; } return ret; }
int modinv(int a) { return modpow(a, mod - 2); }
//-----------------------------------------------------------------------------------
int D; string N;
int dp[10101][101][2];
int main() {
    cin >> D >> N;

    dp[0][0][1] = 1;
    rep(i, 0, N.length()) rep(j, 0, D) rep(k, 0, 2) if(dp[i][j][k]) {
        int c = N[i] - '0';

        int ma = 10;
        if (k == 1) ma = c + 1;
        rep(jj, 0, ma) {
            if(k == 1 && jj == c) dp[i + 1][(j + jj) % D][1] = add(dp[i + 1][(j + jj) % D][1], dp[i][j][k]);
            else dp[i + 1][(j + jj) % D][0] = add(dp[i + 1][(j + jj) % D][0], dp[i][j][k]);
        }
    }

    int ans = add(dp[N.length()][0][0], dp[N.length()][0][1]);
    ans = sub(ans, 1); // =0を抜く
    printf("%d\n", ans);
}

Submission Info

Submission Time
Task E - 数
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 4
Code Size 1360 Byte
Status AC
Exec Time 48 ms
Memory 8192 KB

Judge Result

Set Name All
Score / Max Score 4 / 4
Status
AC × 5
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 AC 2 ms 384 KB
01 AC 30 ms 8192 KB
02 AC 48 ms 8064 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB