結果

問題 No.823 Many Shifts Easy
ユーザー nadeshinonadeshino
提出日時 2019-04-26 23:12:15
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,626 bytes
コンパイル時間 969 ms
コンパイル使用メモリ 80,660 KB
最終ジャッジ日時 2024-11-14 21:26:06
合計ジャッジ時間 1,327 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 19) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated]
stack trace: (most recent call last)
Main.nim(13, 9)          unpack
/home/judge/data/code/Main.nim(139, 19) template/generic instantiation of `input` from here
/home/judge/data/code/Main.nim(19, 41) template/generic instantiation of `unpack` from here
/home/judge/data/code/Main.nim(13, 9) Error: index 1 not in 0 .. 0

ソースコード

diff # 

import algorithm, future, hashes, macros, math, sequtils, sets, strutils, tables, times, unicode

proc `%=`(n: var int, m: int)  = n = n mod m
proc `//=`(n: var int, m: int) = n = n div m
proc `<<=`(n: var int, m: int) = n = n shl m
proc `>>=`(n: var int, m: int) = n = n shr m
proc `<?=`(n: var int, m: int) = n = min(n, m)
proc `>?=`(n: var int, m: int) = n = max(n, m)

macro unpack*(rhs: seq, cnt: static[int]): auto =
  let t = genSym(); result = quote do:(let `t` = `rhs`;())
  if NimMinor <= 17:
    for i in 0..<cnt: result[0][1].add(quote do:`t`[`i`])
  else:
    for i in 0..<cnt: result[1].add(quote do:`t`[`i`])

template input*(typ: typedesc, cnt: Natural = 1): untyped =
  let line = stdin.readLine.split(" ")
  when typ is int:    line.map(parseInt).unpack(cnt)
  elif typ is float:  line.map(parseFloat).unpack(cnt)
  elif typ is string: line.unpack(cnt)
  elif typ is char:   line.mapIt(it[0]).unpack(cnt)

template inputs*(typ: typedesc): untyped =
  let line = stdin.readLine.split(" ")
  when typ is int:    line.map(parseInt)
  elif typ is float:  line.map(parseFloat)
  elif typ is string: line
  elif typ is char:   line.mapIt(it[0])

# -------------------------------------------------- #

const modulus = 10 ^ 9 + 7

type ModInt* = object
  v: int

proc initModInt*(n: int): ModInt =
  result.v = (n mod modulus + modulus) mod modulus

proc `$`*(x: ModInt): string =
  $x.v

proc pow*(x: ModInt, n: int): ModInt =
  if n < 0:
    return pow(x, -n).pow(modulus - 2)
  var p = 1
  var x = x.v
  var n = n
  while n > 0:
    if (n and 1) != 0:
      p = p * x mod modulus
    x = x * x mod modulus
    n = n shr 1

  result.v = p

proc inverse*(x: ModInt): ModInt =
  pow(x, modulus - 2)

proc `+`*(x: ModInt): ModInt =
  result.v = x.v
proc `-`*(x: ModInt): ModInt =
  result.v = modulus - x.v
  if result.v == modulus: result.v = 0

proc `+`*(a: ModInt, b: ModInt): ModInt =
  result.v = a.v + b.v
  if result.v >= modulus: result.v -= modulus
proc `-`*(a: ModInt, b: ModInt): ModInt =
  result.v = a.v - b.v
  if result.v < 0: result.v += modulus
proc `*`*(a: ModInt, b: ModInt): ModInt =
  result.v = a.v * b.v
  if result.v >= modulus: result.v = result.v mod modulus
proc `/`*(a: ModInt, b: ModInt): ModInt =
  result.v = a.v * b.inverse().v
  if result.v >= modulus: result.v = result.v mod modulus

proc `+`*(a: ModInt, b: int): ModInt =
  a + initModInt(b)
proc `-`*(a: ModInt, b: int): ModInt =
  a - initModInt(b)
proc `*`*(a: ModInt, b: int): ModInt =
  a * initModInt(b)
proc `/`*(a: ModInt, b: int): ModInt =
  a / initModInt(b)

proc `+`*(a: int, b: ModInt): ModInt =
  initModInt(a) + b
proc `-`*(a: int, b: ModInt): ModInt =
  initModInt(a) - b
proc `*`*(a: int, b: ModInt): ModInt =
  initModInt(a) * b
proc `/`*(a: int, b: ModInt): ModInt =
  initModInt(a) / b

proc `+=`*(a: var ModInt; b: ModInt) =
  a = a + b
proc `-=`*(a: var ModInt; b: ModInt) =
  a = a - b
proc `*=`*(a: var ModInt; b: ModInt) =
  a = a * b
proc `/=`*(a: var ModInt; b: ModInt) =
  a = a / b

proc `+=`*(a: var ModInt; b: int) =
  a = a + b
proc `-=`*(a: var ModInt; b: int) =
  a = a - b
proc `*=`*(a: var ModInt; b: int) =
  a = a * b
proc `/=`*(a: var ModInt; b: int) =
  a = a / b

# -------------------------------------------------- #

let MAX = 100000 + 100 # n の最大値

var comFactorial = newSeq[ModInt](MAX + 1)
var comInverse = newSeq[ModInt](MAX + 1)
var comInverseFactorial = newSeq[ModInt](MAX + 1)
proc initCom() =
  comFactorial[0].v = 1; comFactorial[1].v = 1;
  comInverse[1].v = 1;
  comInverseFactorial[0].v = 1; comInverseFactorial[1].v = 1;
  for n in countup(2, MAX):
    comFactorial[n] = comFactorial[n - 1] * n
    comInverse[n] = comInverse[modulus mod n] * (modulus div n) * (-1)
    comInverseFactorial[n] = comInverseFactorial[n - 1] * comInverse[n]
proc combination(n: int, k: int): ModInt =
  if n < k: return initModInt(0)
  comFactorial[n] * comInverseFactorial[k] * comInverseFactorial[n - k]

# -------------------------------------------------- #

initCom()

var (N, K) = input(int, 2)

var res = initModInt(0)

if K == 1:
  var cus = 0
  for i in countup(1, N):
    cus += i
  for n in countup(1, N):
    res += cus - n
  echo res
  quit(0)

for n in countup(1, N):
  if n < N:
    var cnt = initModInt(0)
    cnt += combination(K, 2) * combination(N - 2, K - 2) * comFactorial[K - 2]
    cnt += combination(N - 1, K) * comFactorial[K]
    cnt *= n
    res += cnt

    # echo n, " ", cnt / n, " ", cnt
  else:
    var cnt = initModInt(0)
    cnt += combination(N - 1, K) * comFactorial[K]
    cnt *= n
    res += cnt
    

    # echo n, " ", cnt / n, " ", cnt

echo res
0