結果

問題 No.315 世界のなんとか3.5
コンテスト
ユーザー Min_25
提出日時 2015-12-08 14:45:23
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 2,363 bytes
コンパイル時間 569 ms
コンパイル使用メモリ 65,284 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 20:09:57
合計ジャッジ時間 1,896 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cassert>
#include <cstring>
#include <ctime>

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>

#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define rep3(i, m, n) for (int i = int(m); i < int(n); ++i)

using namespace std;
using int64 = long long;

char A[200010];
char B[200010];

const int MOD = 1e9 + 7;

int pow_mod(int b, int e, int m) {
  int ret = 1;
  while (e) {
    if (e & 1) ret = int64(ret) * b % m;
    b = int64(b) * b % m;
    e >>= 1;
  }
  return ret;
}

template <typename T, typename U>
void add(T& a, U b) {
  a += b;
  if (a >= MOD) a -= MOD;
}

int count(char* str, int size, int p, int t, bool inclusive) {
  int64 dp[2][3200];

  int64 prefix = 0;
  bool has3 = false;

  int64 f = 0;
  int mid = max(0, size - 3 - t - 1);
  int64 s = 0;
  rep(i, mid) {
    int d = str[i] - '0';
    f = (f * 10 + s) % MOD;
    s = s * 9 % MOD;
    if (has3) add(f, d);
    else {
      add(s, d - (d > 3));
      add(f, d > 3);
    }
    prefix = (prefix + d) % 3;
    has3 |= d == 3;
  }

  // 3 * p
  const int mod = 3 * p;
  int64* curr = dp[0], *next = dp[1];
  fill(curr, curr + 4 * p, 0);

  curr[0] = curr[1] = curr[2] = s * pow_mod(3, MOD - 2, MOD) % MOD;
  curr[mod] = f % MOD;
  rep3(i, mid, size) {
    int d = str[i] - '0';
    fill(next, next + 4 * p, 0);
    rep(r, mod) rep(j, 10) {
      if (j == 3) add(next[mod + (r * 10 + j) % p], curr[r]);
      else add(next[(r * 10 + j) % mod], curr[r]);
    }
    rep(r, p) rep(j, 10) add(next[mod + (r * 10 + j) % p], curr[mod + r]);
    rep(j, d) {
      if (j == 3 || has3) add(next[mod + (prefix * 10 + j) % p], 1);
      else add(next[(prefix * 10 + j) % mod], 1);
    }
    prefix = (prefix * 10 + d) % mod;
    has3 |= d == 3;
    swap(curr, next);
  }
  if (inclusive) {
    if (has3) add(curr[mod + prefix % p], 1);
    else add(curr[prefix], 1);
  }
  int64 ret = 0;
  rep(i, mod) if (i % 3 == 0 && i % p != 0) ret += curr[i];
  rep3(i, 1, p) ret += curr[i + mod];
  return ret % MOD;
}

void solve() {
  int P;
  while (~scanf("%s %s %d", A, B, &P)) {
    int t = 0;
    int Q = P;
    while (Q % 10 == 0) Q /= 10, ++t;
    int ans = (MOD - count(A, strlen(A), P, t, false)
                   + count(B, strlen(B), P, t, true)) % MOD;
    printf("%d\n", ans);
  }
}

int main() {
  solve();
  return 0;
}
0