結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
ユーザー 👑 hos.lyrichos.lyric
提出日時 2019-01-10 20:10:56
言語 D
(dmd 2.107.1)
結果
AC  
実行時間 719 ms / 3,000 ms
コード長 3,642 bytes
コンパイル時間 730 ms
コンパイル使用メモリ 106,064 KB
実行使用メモリ 13,900 KB
最終ジャッジ日時 2023-09-03 21:56:49
合計ジャッジ時間 4,135 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 706 ms
13,900 KB
testcase_01 AC 711 ms
12,656 KB
testcase_02 AC 719 ms
13,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) throw new EOFException; tokens = readln.split; } auto token = tokens[0]; tokens.popFront; return token; }
int readInt() { return readToken().to!int; }
long readLong() { return readToken().to!long; }
real readReal() { return readToken().to!real; }

void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


immutable MO = 10L^^9 + 7;
immutable A = [2,3,5,7,11,13];
immutable B = [4,6,8,9,10,12];

immutable L = (A[$ - 1] + B[$ - 1]) * 50;

long[] getPatterns(int num, in int[] die) {
  const lim = num * die.maxElement;
  const len = cast(int)(die.length);
  auto dp = new long[][][](num + 1, lim + 1, len);
  dp[0][0][0] = 1;
  foreach (h; 0 .. num) foreach (i; 0 .. lim + 1) {
    auto dpSum = dp[h][i].dup;
    foreach (pos; 1 .. len) {
      (dpSum[pos] += dpSum[pos - 1]) %= MO;
    }
    foreach (pos; 0 .. len) {
      if (i + die[pos] <= lim) {
        (dp[h + 1][i + die[pos]][pos] += dpSum[pos]) %= MO;
      }
    }
  }
  auto ret = new long[lim + 1];
  foreach (i; 0 .. lim + 1) {
    ret[i] = dp[num][i].sum;
  }
  return ret;
}

long N;
int P, Q;

void main() {
  try {
    for (; ; ) {
      N = readLong();
      P = readInt();
      Q = readInt();
      
      const patA = getPatterns(P, A);
      const patB = getPatterns(Q, B);
      auto coef = new long[L + 1];
      foreach (i, pA; patA) foreach (j, pB; patB) {
        (coef[i + j] += pA * pB) %= MO;
      }
      debug {
        writeln(patA[0 .. min($, 60)]);
        writeln(patB[0 .. min($, 60)]);
        writeln(coef[0 .. min($, 60)]);
        writeln("|supp coef| = ", coef.count!(c => (c != 0)));
      }
      
      long[] multiply(in long[] a, in long[] b) {
        auto ret = new long[2 * L];
        foreach (i; 0 .. L) foreach (j; 0 .. L) {
          (ret[i + j] += a[i] * b[j]) %= MO;
        }
        foreach_reverse (i; L .. 2 * L) {
          foreach (j; 1 .. L + 1) {
            if (coef[j] != 0) {
              (ret[i - j] += coef[j] * ret[i]) %= MO;
            }
          }
        }
        ret.length = L;
        return ret;
      }
      
      /*
      auto x = new long[L];
      auto y = new long[L];
      x[1] = 1;
      y[0] = 1;
      for (long n = N + L - 1; n; n >>= 1) {
        if (n & 1) {
          y = multiply(y, x);
        }
        x = multiply(x, x);
      }
      long ans = y.sum;
      */
      
      long[] power(long e) {
        if (e < L) {
          auto ret = new long[L];
          ret[cast(int)(e)] = 1;
          return ret;
        }
        auto b = power(e >> 1);
        if (e & 1) {
          b = [0L] ~ multiply(b, b);
          foreach (j; 1 .. L + 1) {
            (b[L - j] += coef[j] * b[L]) %= MO;
          }
          b.length = L;
        } else {
          b = multiply(b, b);
        }
        return b;
      }
      long ans = power(N + L - 1).sum;
      
      ans = (ans % MO + MO) % MO;
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}
0