結果

問題 No.117 組み合わせの数
ユーザー te-shte-sh
提出日時 2017-01-30 15:03:07
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 256 ms / 5,000 ms
コード長 1,668 bytes
コンパイル時間 8,491 ms
コンパイル使用メモリ 299,440 KB
実行使用メモリ 27,032 KB
最終ジャッジ日時 2024-06-12 06:43:11
合計ジャッジ時間 8,487 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 256 ms
27,032 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.regex;     // RegEx

const int p = 10 ^^ 9 + 7;

void main()
{
  auto bufFrac = new int[](2_000_000), sf = 1;
  bufFrac[0] = 1;

  auto bufInvFrac = new int[](2_000_000);
  bufInvFrac[] = -1;

  auto frac(int n) {
    if (sf <= n) {
      foreach (i; sf..n+1)
        bufFrac[i] = modMul(bufFrac[i - 1], i, p);
      sf = n + 1;
    }
    return bufFrac[n];
  }

  auto invFrac(int n) {
    if (bufInvFrac[n] == -1)
      bufInvFrac[n] = invMod(frac(n), p);
    return bufInvFrac[n];
  }

  auto t = readln.chomp.to!size_t;
  foreach (_; t.iota) {
    auto rd = readln.chomp;
    auto m = rd.matchFirst(r"([CPH])\((\d+),(\d+)\)");
    auto n = m[2].to!int, k = m[3].to!int;

    auto r = 0;
    switch (m[1]) {
    case "C":
      if (n >= k) {
        r = frac(n);
        r = modMul(r, invFrac(k), p);
        r = modMul(r, invFrac(n - k), p);
      }
      break;
    case "P":
      if (n >= k) {
        r = frac(n);
        r = modMul(r, invFrac(n - k), p);
      }
      break;
    case "H":
      if (n > 0) {
        r = frac(n + k - 1);
        r = modMul(r, invFrac(k), p);
        r = modMul(r, invFrac(n - 1), p);
      } else if (k == 0) {
        r = 1;
      }
      break;
    default:
      assert(0);
    }

    writeln(r);
  }
}

int modMul(int a, int b, int mod)
{
  return ((a.to!long * b.to!long) % mod).to!int;
}

T exEuclid(T)(T a, T b, ref T x, ref T y)
{
  auto g = a;
  x = 1;
  y = 0;
  if (b != 0) {
    g = exEuclid(b, a % b, y, x);
    y -= a / b * x;
  }
  return g;
}

T invMod(T)(T x, T m)
{
  T a, b;
  exEuclid(x, m, a, b);
  return ((a % m) + m) % m;
}
0