結果

問題 No.315 世界のなんとか3.5
ユーザー te-shte-sh
提出日時 2017-06-20 14:16:40
言語 D
(dmd 2.106.1)
結果
TLE  
実行時間 -
コード長 2,083 bytes
コンパイル時間 2,156 ms
コンパイル使用メモリ 105,764 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-06-12 20:18:05
合計ジャッジ時間 9,588 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,756 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1,376 ms
6,940 KB
testcase_13 AC 1,375 ms
6,944 KB
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 AC 1,428 ms
6,952 KB
testcase_19 AC 1,405 ms
6,944 KB
testcase_20 AC 1,424 ms
6,940 KB
testcase_21 AC 1,409 ms
6,940 KB
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

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;

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

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

  auto dp3 = new int[][][][][][](2, 2, 3, 8, 2, 2);
  foreach (j; 0..2)
    foreach (k; 0..2)
      foreach (l; 0..3)
        foreach (m; 0..8)
          dp3[j][k][l][m][0][0] = dp1[j][k][l][m];

  foreach_reverse (i; 0..min(sp, ai.length)) {
    auto dp4 = new int[][][][][][](2, 2, 3, 8, 2, 2);
    foreach (j; 0..2)
      foreach (k; 0..2)
        foreach (l; 0..3)
          foreach (m; 0..8) {
            int lim = j ? 9 : ai[$-i-1];
            foreach (d; 0..lim+1)
              foreach (p; 0..2)
                foreach (q; 0..2)
                  dp4[j || d < lim][k || d == 3][(l + d) % 3][m][q][d == 0].add(dp3[j][k][l][m][p][q]);
          }
    dp3 = dp4;
  }

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

  foreach (j; jMin..2)
    foreach (k; 0..2)
      foreach (l; 0..3)
        foreach (m; 0..8)
          foreach (p; 0..2)
            foreach (q; 0..2)
              if ((k == 1 || l == 0) && (sp == 0 && m != 0 || sp == 1 && (m != 0 || q == 0) || sp == 2 && (m != 0 || p == 0 || q == 0)))
                r.add(dp3[j][k][l][m][p][q]);

  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