Typical DP Contest

Submission #5902709

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define RREP(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)

const ll MAX = 1e9+7;

ll dp[10001][2][101];
int D;
string N;

ll solve(int k, int big, int sum) {
  if (k == N.size()) return sum == 0;
  if (dp[k][big][sum] != -1) return dp[k][big][sum];

  ll ret = 0;
  int c = N[k] - '0';
  REP(i, big ? 10 : c+1) {
    int b = big == 1 || i < c;
    ret += solve(k+1, b, (sum+i)%D);
    ret %= MAX;
  }
  return dp[k][big][sum] = ret;
}

int main(int argc, char *argv[]) {
  cin >> D;
  cin >> N;
  if (D==1) {
    cout << N << endl;
    return 0;
  }
  fill_n(&dp[0][0][0], 10001*2*101, -1);
  solve(0, 0, 0);
  cout << dp[0][0][0] - 1<< endl;
  return 0;
}

Submission

Task問題 E - 数
User nameユーザ名 vintersnow
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 4
Source lengthソースコード長 828 Byte
File nameファイル名
Exec time実行時間 96 ms
Memory usageメモリ使用量 17024 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 7 ms 16000 KB
01 AC 61 ms 17024 KB
02 AC 96 ms 17024 KB
90 AC 6 ms 16000 KB
91 AC 6 ms 16000 KB