Typical DP Contest

Submission #1240757

Source codeソースコード

#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

Task問題 E - 数
User nameユーザ名 はまやんはまやん
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 4
Source lengthソースコード長 1360 Byte
File nameファイル名
Exec time実行時間 48 ms
Memory usageメモリ使用量 8192 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 30 ms 8192 KB
02 AC 48 ms 8064 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB