結果

問題 No.117 組み合わせの数
コンテスト
ユーザー nebukuro09
提出日時 2016-10-28 14:09:47
言語 D
(dmd 2.109.1)
結果
RE  
実行時間 -
コード長 1,362 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 729 ms
コンパイル使用メモリ 103,152 KB
実行使用メモリ 17,324 KB
最終ジャッジ日時 2024-06-12 04:45:10
合計ジャッジ時間 1,194 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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")
      writeln(ncr(n, k));
    else if (input[0] == "P")
      writeln(ncr(n, k)*factorial[k]%mod);
    else
      writeln(ncr(n+k-1, k));
  }
}
0