Submission #11841489


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;
// {{{ Modint
// using mint = modint<1000000007>;
// mint x = 2;
// std::cout << x.a << std::endl;
template <std::int64_t M>
class modint {
 public:
  int64_t a;

  explicit constexpr modint(const int64_t x = 0) noexcept :
    a((x % M + M) % M) {}
  constexpr int64_t &value() noexcept { return a; }
  constexpr const int64_t &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= M) {
      a -= M;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += M;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % M;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    int64_t exp = M - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  constexpr modint pow(ll t) const {
    if (!t) return modint(1);
    modint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
};
// }}}
using mint = modint<1000000007>;

// d[i][m][s]: 上からi桁まで見て、かつi桁番目までがKと m(atch) し総和がsとなる、場合の数
mint d[20000][2][200];
vector<ll> K;
ll D, N;

signed main() {
  string tmp;
  cin >> tmp >> D;
  N = tmp.size();
  K.resize(N);
  rep(i, N) {
    K[i] = tmp[i] - '0';
    // cout << "i=" << i << " Ki=" << K[i] << endl;
  }
  // cout<< "N=" << N << endl;

  // init
  rep(p, K[0]) {
    d[0][0][p%D] += mint(1);
  }
  d[0][1][K[0]%D] = mint(1);

  // process
  rep(i, N-1) rep(s, 200) {
    // for m=0
    {    
      rep(p, 10) {
        d[i+1][0][(s+p)%D] += d[i][0][s];
      }
    }
    // for m=1
    {
      rep(p, K[i+1]) {
        d[i+1][0][(s+p)%D] += d[i][1][s];
      }
      {
        ll p = K[i+1];
        d[i+1][1][(s+p)%D] += d[i][1][s];
      }
    }
  }
  //rep(i, N) rep(m, 2) rep(s, 200) {
  //  if (d[i][m][s].value() == 0) continue;
  //  printf("d[%ld][%ld][%ld] = %ld\n", i,m,s,d[i][m][s].value());
  //}

  mint ans(0);
  rep(m, 2) {
    ans += d[N-1][m][0];
  }
  ans -= mint(1); // 0...0 を引く
  cout << ans.value() << endl;
  return 0;
}

Submission Info

Submission Time
Task S - Digit Sum
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3095 Byte
Status
Exec Time 483 ms
Memory 33152 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
× 25
Set Name Test Cases
All 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21
Case Name Status Exec Time Memory
0_00 1 ms 256 KB
0_01 1 ms 256 KB
0_02 2 ms 256 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 436 ms 33152 KB
1_03 483 ms 33152 KB
1_04 390 ms 33152 KB
1_05 380 ms 33152 KB
1_06 388 ms 33152 KB
1_07 382 ms 33152 KB
1_08 389 ms 33152 KB
1_09 390 ms 33152 KB
1_10 386 ms 31104 KB
1_11 383 ms 33152 KB
1_12 376 ms 31104 KB
1_13 391 ms 33152 KB
1_14 389 ms 33152 KB
1_15 390 ms 33152 KB
1_16 389 ms 33152 KB
1_17 393 ms 33152 KB
1_18 379 ms 33152 KB
1_19 382 ms 33152 KB
1_20 1 ms 256 KB
1_21 1 ms 256 KB