結果

問題 No.1049 Zero (Exhaust)
ユーザー nadeshino
提出日時 2020-05-08 22:14:41
言語 Nim
(2.2.0)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 4,840 bytes
コンパイル時間 3,016 ms
コンパイル使用メモリ 69,672 KB
実行使用メモリ 18,560 KB
最終ジャッジ日時 2024-07-04 00:50:51
合計ジャッジ時間 4,414 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import algorithm, macros, math, sequtils, strutils, tables
# import bitops, lenientops, deques,
#   heapqueue, sets, sugar

let read* = iterator: string =
  while true: (for s in stdin.readLine.split: yield s)

template input*(T: static[typedesc]): untyped = 
  when T is int: read().parseInt
  elif T is float: read().parseFloat
  elif T is string: read()
  elif T is char: read()[0]

macro dump*(args: varargs[typed]): untyped =
  result = newNimNode(nnkStmtList)
  for x in args:
    let s = toStrLit(x)
    result.add quote do: stderr.write `s`, " = ", `x`, " "
  result.add quote do: stderr.write "\n"

proc `|=`*(n: var int, m: int) = n = n or m
proc `|=`*(n: var bool, m: bool) = n = n or m
proc `&=`*(n: var int, m: int) = n = n and m
proc `&=`*(n: var bool, m: bool) = n = n and m
proc `^=`*(n: var int, m: int) = n = n xor m
proc `^=`*(n: var bool, m: bool) = n = n xor m
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 SomeNumber, m: SomeNumber) = n = min(n, m)
proc `>?=`*(n: var SomeNumber, m: SomeNumber) = n = max(n, m)
proc newSeq2*[T](n1, n2: Natural): seq[seq[T]] = newSeqWith(n1, newSeq[T](n2))
proc newSeq3*[T](n1, n2, n3: Natural): seq[seq[seq[T]]] = newSeqWith(n1, newSeqWith(n2, newSeq[T](n3)))
proc newSeq4*[T](n1, n2, n3, n4: Natural): seq[seq[seq[seq[T]]]] = newSeqWith(n1, newSeqWith(n2, newSeqWith(n3, newSeq[T](n4))))

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

template useModInt*(p: static[Positive]) =
  type ModInt* {.inject.} = distinct int

  proc toModInt*(n: int): ModInt {.inline.} =
    if n >= p + p:
      ModInt(n mod p)
    elif n >= p:
      ModInt(n - p)
    elif n >= 0:
      ModInt(n)
    elif n >= -p:
      ModInt(n + p)
    else:
      ModInt((n mod p + p) mod p)

  proc inverse*(n: range[1 .. p - 1]): ModInt {.inline.} =
    var (sx, tx, s, t) = (0, 1, p, n)
    while t != 1:
      let k = s div t
      s -= t * k; swap(s, t)
      sx -= tx * k; swap(sx, tx)
    return toModInt(tx)

  proc inverse*(n: ModInt): ModInt {.inline.} =
    inverse(int(n))
    
  proc `$`*(n: ModInt): string {.borrow.}
  proc `+`*(n: ModInt): ModInt {.borrow.}
  proc `-`*(n: ModInt): ModInt {.inline.} =
    ModInt((p - int(n)) * int(int(n) != 0))

  proc `<`*(n: ModInt, m: ModInt): bool {.borrow.}
  proc `<`*(n: ModInt, m: int): bool {.borrow.}
  proc `<`*(n: int, m: ModInt): bool {.borrow.}
  proc `<=`*(n: ModInt, m: ModInt): bool {.borrow.}
  proc `<=`*(n: ModInt, m: int): bool {.borrow.}
  proc `<=`*(n: int, m: ModInt): bool {.borrow.}
  proc `==`*(n: ModInt, m: ModInt): bool {.borrow.}
  proc `==`*(n: ModInt, m: int): bool {.borrow.}
  proc `==`*(n: int, m: ModInt): bool {.borrow.}
 
  proc `+`*(n: ModInt, m: ModInt): ModInt {.inline.} =
    ModInt(int(n) + int(m) - p * int(int(n) + int(m) >= p))
  proc `+`*(n: ModInt, m: int): ModInt {.inline.} =
    toModInt(int(n) + m)
  proc `+`*(n: int, m: ModInt): ModInt {.inline.} =
    toModInt(n + int(m))
  proc `-`*(n: ModInt, m: ModInt): ModInt {.inline.} =
    ModInt(int(n) - int(m) + p * int(int(n) - int(m) < 0))
  proc `-`*(n: ModInt, m: int): ModInt {.inline.} =
    toModInt(int(n) - m)
  proc `-`*(n: int, m: ModInt): ModInt {.inline.} =
    toModInt(- + int(m))
  proc `*`*(n: ModInt, m: ModInt): ModInt {.inline.} =
    toModInt(int(n) * int(m))
  proc `*`*(n: ModInt, m: int): ModInt {.inline.} =
    toModInt(int(n) * m)
  proc `*`*(n: int, m: ModInt): ModInt {.inline.} =
    toModInt(n * int(m))
  proc `/`*(n: ModInt, m: ModInt): ModInt {.inline.} =
    toModInt(int(n) * int(inverse(m)))
  proc `/`*(n: ModInt, m: int): ModInt {.inline.} =
    toModInt(int(n) * int(inverse(m)))
  proc `/`*(n: int, m: ModInt): ModInt {.inline.} =
    toModInt(n * int(inverse(m)))

  proc `+=`*(n: var ModInt, m: ModInt) {.inline.} =
    n = n + m
  proc `+=`*(n: var ModInt, m: int) {.inline.} =
    n = n + m
  proc `-=`*(n: var ModInt, m: ModInt) {.inline.} =
    n = n - m
  proc `-=`*(n: var ModInt, m: int) {.inline.} =
    n = n - m
  proc `*=`*(n: var ModInt, m: ModInt) {.inline.} =
    n = n * m
  proc `*=`*(n: var ModInt, m: int) {.inline.} =
    n = n * m
  proc `/=`*(n: var ModInt, m: ModInt) {.inline.} =
    n = n / m
  proc `/=`*(n: var ModInt, m: int) {.inline.} =
    n = n / m

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

useModInt(10 ^ 9 + 7)

let p, K = input(int)
let P = ModInt(p)
var dp: array[0 .. 10 ^ 6, array[0 .. 1, ModInt]]
dp[0][0] = ModInt(1)
#dump(0)
#dump(dp[0])
for i in 1 .. K:
  #dump(i)
  # +
  dp[i][0] += dp[i - 1][0] + dp[i - 1][1]
  dp[i][1] += (P - 1) * (dp[i - 1][0] + dp[i - 1][1])
  #dump(dp[i])
  # *
  dp[i][0] += P * dp[i - 1][0] + dp[i - 1][1]
  dp[i][1] += (P - 1) * dp[i - 1][1]
  #dump(dp[i])
echo dp[K][0]
0