Typical DP Contest

Submission #5890879

Source codeソースコード

#include <bits/stdc++.h>
#define BASE 1000000007
using namespace std;

int main() {
    int d;
    string n;
    cin >> d >> n;
    int m = n.size();
    long dp[2][d][m + 1];
    for (int j = 0; j <= m; j++) {
        for (int i = 0; i < d; i++) {
            dp[0][i][j] = 0;
            dp[1][i][j] = 0;
        }
    }
    dp[1][0][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < d; j++) {
            for (int k = 0; k < n[i - 1] - '0'; k++) {
                dp[0][(j + k) % d][i] += (dp[0][j][i - 1] + dp[1][j][i - 1]) % BASE;
                dp[0][(j + k) % d][i] %= BASE;
            }
            dp[0][(j + n[i - 1] - '0') % d][i] += dp[0][j][i - 1];
            dp[0][(j + n[i - 1] - '0') % d][i] %= BASE;
            dp[1][(j + n[i - 1] - '0') % d][i] += dp[1][j][i - 1];
            dp[1][(j + n[i - 1] - '0') % d][i] %= BASE;
            for (int k = n[i - 1] - '0' + 1; k < 10; k++) {
                dp[0][(j + k) % d][i] += dp[0][j][i - 1];
                dp[0][(j + k) % d][i] %= BASE;
            }
        }
    }
    cout << (BASE - 1 + dp[0][0][m] + dp[1][0][m]) % BASE << endl;
    return 0;
}

Submission

Task問題 E - 数
User nameユーザ名 hi_watana
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 4
Source lengthソースコード長 1178 Byte
File nameファイル名
Exec time実行時間 77 ms
Memory usageメモリ使用量 15488 KB

Test case

Set

Set name Score得点 / Max score Cases
All 4 / 4 00,01,02,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 2 ms 384 KB
01 AC 46 ms 9344 KB
02 AC 77 ms 15488 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB