結果

問題 No.117 組み合わせの数
ユーザー nebukuro09nebukuro09
提出日時 2016-10-28 14:35:25
言語 D
(dmd 2.106.1)
結果
TLE  
実行時間 -
コード長 1,493 bytes
コンパイル時間 665 ms
コンパイル使用メモリ 103,212 KB
実行使用メモリ 39,628 KB
最終ジャッジ日時 2024-06-12 04:45:26
合計ジャッジ時間 13,113 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

import std.stdio;
import std.array;
import std.string;
import std.conv;
import std.algorithm;
import std.typecons;
import std.range;

long ncr(int n, int r, int mod=10^^9+7){
  if (n-r < r) r = n-r;
  if (r == 0) return 1;
  if (r == 1) return n;

  int[] numerator = new int[](r);
  int[] denominator = new int[](r);

  foreach (k; iota(r)) {
    numerator[k] = n - r + k + 1;
    denominator[k] = k + 1;
  }

  foreach (p; iota(2, r+1)) {
    int pivot = denominator[p-1];
    if (pivot > 1) {
      int offset = (n-r)%p; 
      foreach (k; iota(p-1, r, p)) {
        numerator[k-offset] /= pivot;
        denominator[k] /= pivot;
      }
    }
  }

  long result = 1;
  foreach (k; iota(r))
    if (numerator[k] > 1)
      result = (result * numerator[k]) % mod;
  return result;
 }

void main() {
  long mod = 10^^9+7;
  long[] factorial = new long[](10^^6+1);
  factorial[0] = 1;
  factorial[1] = 1;
  foreach (i; iota(2, 10^^6+1)) 
    factorial[i] = (i * factorial[i-1]) % mod;

  int T = readln().chomp.to!int;
  foreach (i; iota(T)) {
    auto input = readln().chomp.replace("(", " ").replace(",", " ").replace(")", "").split;
    int n = input[1].to!int;
    int k = input[2].to!int;
    if (input[0] == "C") {
      if (n < k) writeln(0);
      else writeln(ncr(n, k));
    }
    else if (input[0] == "P") {
      if (n < k) writeln(0);
      else writeln(ncr(n, k)*factorial[k]%mod);
    }
    else {
      if (n+k-1 < k) writeln(0);
      else writeln(ncr(n+k-1, k));
    }
  }
}
0