結果

問題 No.117 組み合わせの数
ユーザー m77som77so
提出日時 2018-06-13 01:53:58
言語 Nim
(2.0.2)
結果
AC  
実行時間 273 ms / 5,000 ms
コード長 1,803 bytes
コンパイル時間 2,875 ms
コンパイル使用メモリ 68,892 KB
実行使用メモリ 96,868 KB
最終ジャッジ日時 2023-09-13 03:46:20
合計ジャッジ時間 3,830 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 273 ms
96,868 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(13, 35) Warning: Deprecated since v1.4; there should not be `high(value)`. Use `high(type)`.; high is deprecated [Deprecated]
/home/judge/data/code/Main.nim(53, 18) Warning: imported and not used: 'macros' [UnusedImport]

ソースコード

diff # 

const threshold = 2_000_000
const m = 1_000_000_007
type CombinationObj = object of RootObj
  fact: array[threshold+10,int64]
  factinv: array[threshold+10, int64]

proc extend_euclid(x0:int64;y0:int64): array[3,int64]=
  var a0,a1,a2,b0,b1,b2,r0,r1,r2,q,x,y:int64
  (x,y)=(x0,y0);r0=x; r1=y; a0=1; a1=0; b0=0; b1=1;
  while r1>0:
    q=r0 div r1; r2=r0 mod r1; a2=a0-q*a1; b2=b0-q*b1; r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2;
  result = [a0,b0,r0]
proc mpow(a:int64;b:int64;m:int64=high(1'i64)): int64=
  result = 1
  var (x,n) = (a,b)
  while n!=0:
    if (n and 1) == 1:result = (result*x) mod m
    x = (x*x) mod m;n = n shr 1
proc combination(): array[2,array[threshold+10, int64]]=
  var   
    fact: array[threshold+10,int64]
    factinv: array[threshold+10, int64]
  
  fact[0]=1
  for i in 1..threshold+1:
    fact[i] = fact[i-1]*i mod m
  var a = (extend_euclid(fact[threshold+1],m))[0]
  if a<m:a+=m
  factinv[threshold+1] = a mod m
  var i = threshold
  while i>=0:
    factinv[i] = factinv[i+1]*(i+1) mod m
    i-=1
  return [fact,factinv]
proc C(obj: CombinationObj,n: int,k:int): int64=
  if k < 0 or k > n:
    return 0
  (obj.fact[n] * obj.factinv[k] mod m) * obj.factinv[n-k] mod m
proc P(obj: CombinationObj,n: int,k:int): int64=
  if k > n:
    return 0
  (obj.fact[n] * obj.factinv[n-k]) mod m
proc H(obj: CombinationObj,n: int,k:int): int64=
  if n==0 and k==0:
    return 1
  if n==0:
    return 0
  obj.C(n+k-1,k)


let cc = combination()
let c = CombinationObj(fact:cc[0],factinv:cc[1])
import strutils, macros, sequtils
let n = stdin.readLine.parseInt

for i in 0..<n:
  let l = stdin.readLine
  let rng = l[2..^2].split(',').map(parseInt)
  if l[0]=='C':
    echo c.C(rng[0],rng[1])
  elif l[0]=='P':
    echo c.P(rng[0],rng[1])
  elif l[0]=='H':
    echo c.H(rng[0],rng[1])
0