結果

問題 No.315 世界のなんとか3.5
ユーザー te-shte-sh
提出日時 2017-06-20 14:59:34
言語 D
(dmd 2.107.1)
結果
AC  
実行時間 910 ms / 2,000 ms
コード長 2,503 bytes
コンパイル時間 845 ms
コンパイル使用メモリ 96,612 KB
実行使用メモリ 10,620 KB
最終ジャッジ日時 2023-09-03 14:38:22
合計ジャッジ時間 12,707 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 3 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 199 ms
7,280 KB
testcase_13 AC 198 ms
7,220 KB
testcase_14 AC 395 ms
8,088 KB
testcase_15 AC 394 ms
8,112 KB
testcase_16 AC 396 ms
8,100 KB
testcase_17 AC 394 ms
8,096 KB
testcase_18 AC 199 ms
7,232 KB
testcase_19 AC 199 ms
7,232 KB
testcase_20 AC 199 ms
7,220 KB
testcase_21 AC 199 ms
7,268 KB
testcase_22 AC 394 ms
8,164 KB
testcase_23 AC 394 ms
8,148 KB
testcase_24 AC 395 ms
8,152 KB
testcase_25 AC 396 ms
8,224 KB
testcase_26 AC 394 ms
8,156 KB
testcase_27 AC 391 ms
8,156 KB
testcase_28 AC 385 ms
8,088 KB
testcase_29 AC 713 ms
10,064 KB
testcase_30 AC 711 ms
9,396 KB
testcase_31 AC 712 ms
10,384 KB
testcase_32 AC 785 ms
9,812 KB
testcase_33 AC 395 ms
7,844 KB
testcase_34 AC 644 ms
10,400 KB
testcase_35 AC 910 ms
10,620 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;

const p = 10 ^^ 9 + 7;

void main()
{
  auto rd1 = readln.split;
  auto rd2 = rd1[0..2].map!(s => s.map!(c => (c - '0').to!int).array), a = rd2[0], b = rd2[1];
  auto p = rd1[2].to!int;

  auto sp = p.predSwitch(8, 0, 80, 1, 800, 2);
  auto r = calc8!true(b, sp);
  auto s = calc8!false(a, sp);
  r.sub(s);
  writeln(r);
}

auto calc8(bool includeMax)(int[] ai, int sp)
{
  auto n = ai.length.to!int;
  if (n <= sp + 3) return calcNaive!(includeMax)(ai, sp);

  auto dp1 = new int[][][](2, 2, 3);
  dp1[0][0][0] = 1;

  foreach (i; 0..n-sp-3) {
    auto dp2 = new int[][][](2, 2, 3);
    foreach (j; 0..2)
      foreach (k; 0..2)
        foreach (l; 0..3) {
          int lim = j ? 9 : ai[i];
          foreach (d; 0..lim+1)
            dp2[j || d < lim][k || d == 3][(l + d) % 3].add(dp1[j][k][l]);
          }
    dp1 = dp2;
  }

  auto dp3 = new int[][][][](2, 2, 3, 2);
  foreach (j; 0..2)
    foreach (k; 0..2)
      foreach (l; 0..3) {
        int lim = j ? 999 : ai[$-sp-3..$-sp].toInt;
        foreach (d; 0..lim+1)
          dp3[j || d < lim][k || d.include3][(l + d) % 3][d % 8 == 0].add(dp1[j][k][l]);
      }

  auto dp4 = new int[][][][][](2, 2, 3, 2, 2);
  if (sp > 0)
    foreach (j; 0..2)
      foreach (k; 0..2)
        foreach (l; 0..3)
          foreach (m; 0..2) {
            int lim = j ? 10 ^^ sp - 1 : ai[$-sp..$].toInt;
            foreach (d; 0..lim+1)
              dp4[j || d < lim][k || d.include3][(l + d) % 3][m][d % (10 ^^ sp) == 0].add(dp3[j][k][l][m]);
          }

  auto jMin = includeMax ? 0 : 1, r = 0;

  foreach (j; jMin..2)
    foreach (k; 0..2)
      foreach (l; 0..3)
        foreach (m; 0..2)
          if (sp == 0) {
            if ((k == 1 || l == 0) && m == 0)
              r.add(dp3[j][k][l][m]);
          } else {
            foreach (p; 0..2)
              if ((k == 1 || l == 0) && (m == 0 || p == 0))
                r.add(dp4[j][k][l][m][p]);
          }

  return r;
}

auto calcNaive(bool includeMax)(int[] ai, int sp)
{
  auto n = ai.toInt, r = 0;
  if (!includeMax) --n;
  foreach (i; 1..n+1)
    if ((i % 3 == 0 || i.include3) && i % (8 * (10 ^^ sp)) != 0)
      ++r;
  return r;
}

auto include3(int n)
{
  for (; n > 0; n /= 10)
    if (n % 10 == 3) return true;
  return false;
}

auto toInt(int[] ai)
{
  auto r = 0;
  foreach (a; ai) r = r * 10 + a;
  return r;
}

auto add(ref int a, int b) { a = (a + b) % p; }
auto sub(ref int a, int b) { a = ((a - b) % p + p) % p; }
0