Submission #11376221


Source Code Expand

#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <cassert>
using namespace std;
const long long MOD = 1000000007;
long long dp[10000][100];
int main(){ 
    int D;
    cin >> D;
    string N;
    cin >> N;

    

    int cur_digit = (int) (N[0] - '0');
    for(int i = 0; i < cur_digit; i++){
        dp[0][i % D] ++;
    }

    long long tmp_mod = cur_digit % D;
    for(int i = 0; i < N.size() - 1; i++){
        for(int j = 0; j < D; j++){
            for(int k = 0; k < 10; k++){
                dp[i + 1][(j + k) % D] = (dp[i + 1][(j + k) % D] + dp[i][j]) % MOD;
            }
        }
        cur_digit = (int) (N[i + 1] - '0');
        for(int j = 0; j < cur_digit; j++){
            dp[i + 1][(tmp_mod +  j) % D] = (dp[i + 1][(tmp_mod + j) % D] + 1) % MOD;
        }
        tmp_mod = (tmp_mod + cur_digit) % D;
    }
    dp[N.size() - 1][tmp_mod] = (dp[N.size() - 1][tmp_mod] + 1) % MOD;
    dp[N.size() - 1][0] = (dp[N.size() - 1][0] - 1 + MOD) % MOD;
    
    cout << dp[N.size() - 1][0] << endl;
    return 0;
}

Submission Info

Submission Time
Task E - 数
User katom
Language C++14 (GCC 5.4.1)
Score 4
Code Size 1295 Byte
Status AC
Exec Time 48 ms
Memory 8064 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 256 KB
01 AC 31 ms 8064 KB
02 AC 48 ms 7936 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB