Typical DP Contest

Submission #5896533

Source codeソースコード

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
using ll = long long;

const ll MM = 1000000007;
string N;
int D;
ll num[10000][10][101] = {};

int mod(int a, int b){
    if (a<0) {
        int c = int(double(-a)/double(b)) + 1;
        return (a + b * c) % b;
    }
    else return a % b;
}

void solve(int kk) {
    for (int k = 1; k < kk; ++k) {
        for (int j = 0; j < D; ++j) {
            num[k][0][j] = num[k-1][9][j];
        }
        for (int i = 1; i < 10; ++i) {
            for (int j = 0; j < D; ++j) {
                int a = mod(j-i, D);
                int f = i%D == j ? 1 : 0;
                num[k][i][j] = (num[k-1][9][a] + num[k][i-1][j] + f) % MM;
            }
        }
    }
}
int main(int argc, char *argv[])
{
    cin >> D;
    cin >> N;
    if (D==1) {
        cout << N << endl;
        return 0;
    }
    for (int i = 0; i < 10; ++i) {
        for (int j = 1; j < i+1; ++j) {
            num[0][i][j % D] += 1;
        }
    }

    solve(N.size());

    int c = N[0] - '0';
    int a=mod(D-c, D);
    ll ans = num[N.size()-1][c-1][0];
    // printf("\n%d\n", ans);
    for (int i = 1; i < N.size(); ++i) {
        c = N[i] - '0';
        int sub = 0;
        if (c > 0) {
            sub = num[N.size() - i - 1][c-1][a];
        }
        if(a == 0) {  // xxx000もOk
            sub += 1;
        }
        if (i == N.size()-1 && a+c % D == 0)  sub+=1;
        ans = (ans + sub) % MM;
        // printf("c=%d, a=%d, sub=%d", c, a, sub);
        a = mod(a-c, D);
        // printf(" newa=%d\n", a);
    }
    printf("%lld\n", ans);
    return 0;
}

Submission

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

Test case

Set

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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 2 ms 1024 KB
01 WA
02 WA
90 AC 1 ms 256 KB
91 AC 1 ms 512 KB