結果

問題 No.978 Fibonacci Convolution Easy
ユーザー nimonnimon
提出日時 2020-01-31 22:42:20
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 17,493 bytes
コンパイル時間 1,096 ms
コンパイル使用メモリ 83,872 KB
最終ジャッジ日時 2024-04-27 03:04:04
合計ジャッジ時間 1,468 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
stack trace: (most recent call last)
Main.nim(221, 19)        inputs
macros.nim(1219, 27)     expectKind
/home/judge/data/code/Main.nim(453, 1) template/generic instantiation of `inputs` from here
/home/judge/data/code/Main.nim(454, 3) Error: Expected one of {nnkIdent, nnkPar}, got nnkTupleConstr

ソースコード

diff # 

when NimMajor <= 0 and NimMinor <= 18: import future else: import sugar

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from typetraits import arity
from sequtils import map, mapIt, newSeqWith, toSeq
from strutils import split, parseInt, parseFloat, parseBool, parseEnum, parseBiggestInt
when NimMajor == 0 and NimMinor >= 14: from strutils import parseBiggestUInt

import macros

from terminal import setForegroundColor, ForegroundColor, resetAttributes
proc warn(message: string) =
  when not defined release:
    stderr.setForegroundColor(fgYellow)
    stderr.write("注意: ")
    stderr.resetAttributes
    stderr.writeLine message

when not declared parseBiggestUInt:
  proc parseBiggestUInt(s: string): uint64 = uint64(parseInt(s))
when not declared SomeFloat:
  type SomeFloat = float | float64 | float32
when not defined nimHasRunnableExamples:
  template runnableExamples*(body: untyped) = discard

proc parseT(s: string; T: typedesc): auto =
  ## `parse` 系関数のジェネリック版
  ## `T` が `SomeOrdinal | SomeFloat` (subranges を含む) でない場合，そのまま `s` を返す
  runnableExamples:
    doAssert parseT("12", int) == 12
    doAssert parseT("12", uint) == 12
    doAssert parseT("12", int64) == 12
    doAssert parseT("12", float32) == 12.0
    doAssert parseT("Yes", bool) == true

  when T is SomeSignedInt: cast[T](parseBiggestInt(s))
  elif T is SomeUnsignedInt: cast[T](parseBiggestUInt(s))
  elif T is SomeFloat: cast[T](parseFloat(s))
  elif T is enum: parseEnum[T](s)
  elif T is bool: parseBool(s)
  elif T is char: s[0]
  else: s

proc unpackWithParse*(input: openArray[string]; T: typedesc[tuple]): T =
  ## 文字列配列を `T` で指定された `tuple` に `parse` しながら変換する
  runnableExamples:
    let t = unpackWithParse(@["1", "1", "1", "1", "1"], 4, tuple[a: int8, b: uint32, c: float64, d: bool])
    doAssert int8 is t.a.type and t.a == 1
    doAssert uint32 is t.b.type and t.b == 1
    doAssert float64 is t.c.type and t.c == 1.0
    doAssert bool is t.d.type and t.d == true
    doAssert tuple[a: int8, b: uint32, c: float64, d: bool] is t.type

  var i = 0
  for x in result.fields:
    if i > input.high:
      warn "元の配列の長さが " & $T.arity & " 未満だから，一部デフォルト値になってるよ"
      break
    x = parseT(input[i], x.type)
    i.inc
  result

proc input(T: typedesc[string]): string = stdin.readLine
proc input(T: typedesc[SomeOrdinal | SomeFloat | char]): auto = input(string).parseT(T)
proc input(T: typedesc[seq[string]]): auto = input(string).split
proc input(T: typedesc[seq[char]]): auto = toSeq(input(string).items)
proc input[E: SomeOrdinal | SomeFloat](T: typedesc[seq[E]]): auto = input(seq[string]).mapIt(it.parseT(E.type))
proc input(T: typedesc[tuple]): auto = input(seq[string]).unpackWithParse(T)

proc toTupleType(parTuple: NimNode): NimNode {.compileTime.} =
  ## `nnkPar` で表現されてる名前付きタプルを `tuple[]` 形式に変換する
  ## `nnkPar` が名前付きタプルじゃない場合は，そのまま返す
  runnableExamples:
    static:
      doAssert((quote do: (a: int, b: float)).toTupleType == (quote do: tuple[a: int, b: float]))
      doAssert((quote do: (a, b: int)).toTupleType == (quote do: tuple[a, b: int]))
      doAssert((quote do: (int, int)).toTupleType == (quote do: (int, int)))
      doAssert((quote do: ()).toTupleType == (quote do: ()))

  if parTuple.len == 0 or parTuple.findChild(it.kind == nnkExprColonExpr) == nil: # () or (T, U, ...)
    result = parTuple
  else:
    result = newTree(nnkTupleTy)
    var identDefs = newTree(nnkIdentDefs)
    for field in parTuple:
      if field.kind == nnkIdent: # (a, b, ..., x: T)  の a, b, ... 部分 (x 以外)
        identDefs.add(field)
      field.copyChildrenTo(identDefs)
      if field.kind != nnkIdent: # (..., x: T, y: ...) の x: T 部分
        identDefs.add(newEmptyNode())
        result.add(identDefs)
        identDefs = newTree(nnkIdentDefs)

proc seqInputCall(bracketTree: NimNode): NimNode {.compileTime.} =
  ## `seq[N, seq[M, ..., [seq[T]]...]]` を `newSeqWith(N, newSeqWith(M, ..., input(seq[T])...))` にする

  if bracketTree.kind != nnkBracketExpr:
    case bracketTree.kind:
      of nnkPar: # x: (Field0: ...)
        result = newCall("input", bracketTree.toTupleType)
      else: # x: T
        result = newCall("input", bracketTree)
  else:
    case bracketTree.len:
      of 2: # seq[N, ... seq[T] ...] の seq[T]
        if bracketTree[^1].kind == nnkBracketExpr:
          error("seq[seq[T]] みたいな書き方はできないって言ったでしょ！ seq[N, seq[T]] みたいに書き直してっ")
        result = newCall("input", bracketTree)
      of 3: # それ以外 (seq[N, ...])
        result = newCall("newSeqWith", bracketTree[1], seqInputCall(bracketTree[^1]))
      else:
        error("変な入力があるよ")

proc appendedProcCallBlocks(procCalls: NimNode; i: int): NimNode =
  ## `procCalls[i]` の関数呼び出しを
  ## .. code-block:: Nim
  ##   block:
  ##     var it = procCall(...)
  ## という形に変換しながらつなげていく
  ## 最後だけは
  ## .. code-block:: Nim
  ##   block:
  ##     var it = lastProcCall(...)
  ##     it
  ## というようにして `it` を返すようにする

  let it = ident("it")
  let procCall = procCalls[i]
  result = newStmtList(quote do:
    var `it` = `procCall`
  )
  if i == procCalls.len - 1: # 最後の要素だけは it を返すようにする
    result.add(it)
  else:
    result.add(appendedProcCallBlocks(procCalls, i + 1))
  result = newBlockStmt(result)

proc inputsImpl(pre, post: NimNode): NimNode {.compileTime.} =
  ## pre で指定された変数に post の結果を入れる

  # input() 部分の生成
  var inputCall: NimNode
  case pre.kind:
    of nnkPar: # (x, y, ...): ...
      result = newTree(nnkVarTuple)
      pre.copyChildrenTo(result)
      result.add(newEmptyNode())
      case post[0].kind:
        of nnkPar: # (x, y, ...): (T, T, ...)
          inputCall = newCall("input", post[0].toTupleType)
        of nnkTupleTy: # (x, y, ...): tuple[Field0: ...]
          inputCall = newCall("input", post)
        else: # (x, y, ...): T
          var parTupleTy = newTree(nnkPar)
          for _ in 0..<pre.len: parTupleTy.add(post[0]) # (int, int, int, ...) みたいなのを作ってる
          inputCall = newCall("input", parTupleTy)
    else: # x: ...
      result = newTree(nnkIdentDefs).add(pre).add(newEmptyNode())
      case post[0].kind:
        of nnkPar: # x: (Field0: ...)
          inputCall = newCall("input", post[0].toTupleType)
        of nnkBracketExpr:
          inputCall = seqInputCall(post[0])
        else: # x: T
          inputCall = newCall("input", post[0])

  # 関数部分の生成（ある場合）と結合
  if post.len > 1:
    let it = ident("it")
    var itStmts = when NimMajor == 0 and NimMinor < 17: newStmtList(quote do: (var `it` = `inputCall`)) # 入力の読み込み
                  else: newStmtList(quote do: (var `it` {.used.} = `inputCall`))
    itStmts.add(appendedProcCallBlocks(post, 1)) # 関数の適用
    result.add(newTree(nnkStmtListExpr, newBlockStmt(itStmts))) # 結合
  else:
    result.add(inputCall) # 結合

macro inputs*(body: untyped): untyped =
  ## 入力を受け取る
  ## 宣言の後に `it` を用いた式を（`y` みたいに用いなくてもいいんだけど）いくつでもかくことができ，
  ## その返り値が変数の値となる
  ## 式中で型が変わってもいい（下の例の `u`, `y` とか見たいな感じ）
  ##
  ## .. code-block:: Nim
  ##   inputs:
  ##     a: int
  ##     b: string
  ##     c: (x: char, y: float)
  ##     d: tuple[x: char, y: float]
  ##     e: (u, v: BiggestInt)
  ##     f: tuple[u, v: int]
  ##     g: seq[int]
  ##     h: seq[a, seq[int]]
  ##     i: seq[a, (s, t: int)]
  ##     (j, k, l): int
  ##     (m, n): (char, float)
  ##     o: seq[a, string]
  ##     (p): int
  ##     q: seq[int]; it.sorted(system.cmp)
  ##     r: seq[float]; it.sorted(cmp).filterIt(it > 0)
  ##     s: seq[char]
  ##     t: seq[2, seq[a, int]]
  ##     u: string; parseInt(it); abs(-it)
  ##     (_, v): (a: char, b: char)
  ##     (w, x): tuple[a, b: char]
  ##     y: int; "hoge"

  expectKind(body, nnkStmtList)
  result = newTree(nnkStmtList)
  var letSection = newTree(nnkLetSection)
  for decl in body:
    case decl[0].kind:
      of nnkIdent: # x: ...
        letSection.add(inputsImpl(decl[0], decl[1]))
      of nnkPar:
        expectMinLen(decl[0], 1)
        if decl[0].len == 1: # (x): ... これは x: ... と同じ扱いにしたい
          letSection.add(inputsImpl(decl[0][0], decl[1]))
        else: # (x, y, ...): ...
          letSection.add(inputsImpl(decl[0], decl[1]))
      else:
        expectKind(decl[0], {nnkIdent, nnkPar})

  result.add(letSection)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
proc `ceilDiv`*[T](x, y: T): T = x div y + ord(x mod y != 0)
proc `//=`*(x: var SomeInteger; y: SomeInteger) = x = x div y
proc `%=`*(x: var SomeInteger; y: SomeInteger) = x = x mod y
proc `<?=`*[T](x: var T; y: T) = x = min(x, y)
proc `>?=`*[T](x: var T; y: T) = x = max(x, y)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from sequtils import concat

template flatten*[T](s: seq[T]): untyped =
  when T is seq: flatten(s.concat)
  else: s
proc flatten*[T](s: seq[T]; recLevel: static[Natural]): auto =
  when recLevel == 0: s
  elif T is seq: flatten(s.concat, recLevel - 1)
  else: s

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
proc withIndex*[T](s: openArray[T]): seq[tuple[i: int, v: T]] =
  (0..s.high).mapIt((it, s[it]))

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
template countIt*[T](a: openArray[T]; pred: untyped): int =
  var result = 0
  for it {.inject.} in items(a):
    if pred: result.inc
  result

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from sequtils import newSeqWith, allIt

template newSeqWithImpl[T](lens: seq[int]; init: T; currentDimension, lensLen: static[int]): untyped =
  when currentDimension == lensLen:
    newSeqWith(lens[currentDimension - 1], init)
  else:
    newSeqWith(lens[currentDimension - 1], newSeqWithImpl(lens, init, currentDimension + 1, lensLen))

template newSeqWith*[T](lens: varargs[int]; init: T): untyped =
  assert(lens.allIt(it > 0))
  newSeqWithImpl(@lens, init, 1, lens.len)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
template stderrEcho*(x: varargs[string, `$`]) =
  for v in x:
    stderr.write(v)
  stderr.writeLine ""

template stderrEcho*[T](x: seq[seq[T]]) =
  for v in x: stderrEcho v

template stderrEcho*(x: seq[string]) =
  for v in x: stderrEcho v

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
template useMint*(MOD: range[2..int.high]) =
  ## mint型を使えるようにする
  ##
  ## .. code-block:: Nim
  ##  useMint(1_000_000_007)
  ##  let (n, m) = (3.toMint, 5.toMint)

  type mint* {.inject.} = distinct int

  #--- 型変換 ---#
  proc toMint*(n: SomeInteger): mint {.inline.} =
    if n < -MOD: mint(n mod MOD + MOD)
    elif n < 0: mint(n + MOD)
    elif n >= MOD: mint(n mod MOD)
    else: mint(n)

  proc toInt*(n: mint): int {.inline.} = int(n)

  #--- 逆元 ---#
  proc inverse*(n: mint): mint {.inline.} =
    ## 逆元 O(log(MOD))
    ## 非再帰extGcd版: ax + by = 1 を満たす x が b を法とした a の逆元
    ## 参考: https://topcoder.g.hatena.ne.jp/iwiwi/20130105/1357363348
    var (a, x, b, y) = (MOD, 0, n.toInt, 1)
    while b != 0:
      let tmp = a div b
      a -= tmp * b; swap(a, b)
      x -= tmp * y; swap(x, y)
    assert(x.toMint.toInt * n.toInt mod MOD == 1)
    return x.toMint

  proc `~`*(n: mint): mint {.inline.} = n.inverse

  #--- 単項演算子 ---#
  proc `+`*(n: mint): mint {.borrow.}
  proc `-`*(n: mint): mint {.inline.} = mint(MOD - n.toInt)
  proc `$`*(n: mint): string {.borrow.}

  #--- 二項演算子 ---#
  # 比較 #
  template extendComparisonOperatorToInt(op: untyped) =
    ## mint と int を混ぜて使ってもいいように比較演算子を拡張する
    proc op*(n: mint; m: int): bool {.inline.} = op(n, m.toMint)
    proc op*(n: int; m: mint): bool {.inline.} = op(n.toMint, m)

  proc `<`*(n, m: mint): bool {.borrow.}
  extendComparisonOperatorToInt(`<`)
  proc `<=`*(n, m: mint): bool {.borrow.}
  extendComparisonOperatorToInt(`<=`)
  proc `==`*(n, m: mint): bool {.borrow.}
  extendComparisonOperatorToInt(`==`)

  # 算術 #
  template extendArithmeticOperatorToInt(op: untyped) =
    ## mint と int を混ぜて使ってもいいように算術演算子を拡張する
    proc op*(n: mint; m: int): mint {.inline.} = op(n, m.toMint)
    proc op*(n: int; m: mint): mint {.inline.} = op(n.toMint, m)

  proc `mod`*(n, m: mint): mint {.inline.} = (n.toInt mod m.toInt).toMint
  proc `mod`*(n: mint, m: int): mint {.inline.} = (n.toInt mod m).toMint
  proc `mod`*(n: int, m: mint): mint {.inline.} = (n mod m.toInt).toMint
  proc `%`*(n, m: mint): mint {.inline.} = n mod m
  proc `%`*(n: mint; m: int): mint = n mod m
  proc `%`*(n: int; m: mint): mint = n mod m
  proc `+`*(n, m: mint): mint {.inline.} = (n.toInt + m.toInt).toMint
  extendArithmeticOperatorToInt(`+`)
  proc `-`*(n, m: mint): mint {.inline.} = n + (-m)
  extendArithmeticOperatorToInt(`-`)
  proc `*`*(n, m: mint): mint {.inline.} = (n.toInt * m.toInt).toMint
  extendArithmeticOperatorToInt(`*`)
  proc `div`*(n, m: mint): mint {.inline.} =
    ## O(log(MOD))
    n * m.inverse
  extendArithmeticOperatorToInt(`div`)
  proc `/`*(n, m: mint): mint {.inline.} = n div m
  extendArithmeticOperatorToInt(`/`)

  proc mul*(n: mint; m: int): mint =
    ## MOD が大きすぎるとき用の掛け算 O(log(m))  (足し算で掛け算を計算するので)
    result = m.toMint
    var (n, m) = (n, m)
    while m != 0:
      if (m and 1) == 1: result = result + n
      n = n + n
      m = m shr 1
  proc mul*(n, m: mint): mint = mul(n, m.toInt)
  proc mul*(n: int; m: mint): mint = mul(m, n)

  # 算術代入 #
  proc `%=`*(n: var mint; m: mint | int) {.inline.} = (n = n % m.int)
  proc `+=`*(n: var mint; m: mint | int) {.inline.} = (n = n + m.int)
  proc `-=`*(n: var mint; m: mint | int) {.inline.} = (n = n - m.int)
  proc `*=`*(n: var mint; m: mint | int) {.inline.} = (n = n * m.int)
  proc `/=`*(n: var mint; m: mint | int) {.inline.} = (n = n / m.int)

  #--- 累乗 ---#
  proc pow*(n: mint; m: int): mint {.inline.} =
    # O(log(m))?
    var (nn, mm) = (n, abs(m).toMint.int)
    result = 1.toMint
    while mm != 0:
      if (mm and 1) == 1: result = result * nn
      nn = nn * nn
      mm = mm shr 1
    if m < 0: result = result.inverse
  proc pow*(n, m: mint): mint {.inline.} = n.pow(m.toInt)
  proc pow*(n: int; m: mint): mint {.inline.} = n.toMint.pow(m.toInt)

  proc `^`*(n, m: mint): mint {.inline.} =
    ## O(log(m))?
    n.pow(m)
  proc `^`*(n: mint; m: int): mint {.inline.} = n.pow(m)
  proc `^`*(n: int; m: mint): mint {.inline.} = n.pow(m) # これは戻り値が mint でいいのか疑問ではある

  #--- その他関数 ---#
  proc inc*(x: var mint; y: int = 1) = (x += y)
  proc inc*(x: var mint; y: mint) = (x += y)

  proc dec*(x: var mint; y: int = 1) = (x -= y)
  proc dec*(x: var mint; y: mint) = (x -= y)

  template useNumberOfCases*(size = 3_000_000) =
    ## 場合の数（組み合わせとか）関係の関数も使えるようにする
    ##
    ## .. code-block:: Nim
    ##  useMint(1_000_000_007)
    ##  useNumberOfCases(1_000_000)
    ##  let (n, m) = (3.toMint, 5.toMint)
    ##  m.C(n) # => 10

    proc init(): tuple[facs, facInvs: seq[mint]] =
      ## MODを法とした階乗テーブルとその逆元テーブルの作成
      result = (newSeq[mint](size + 1), newSeq[mint](size + 1))

      result.facs[0] = mint(1)
      for i in 1..size:
        result.facs[i] = result.facs[i - 1] * i

      result.facInvs[size] = result.facs[size].inverse
      for i in countdown(size - 1, 0):
        result.facInvs[i] = result.facInvs[i + 1] * (i + 1)

    let (facs, facInvs) = init() # const にすると too many iterations

    template extendNumberOfCases(f: untyped) =
      ## mint と int を混ぜたり，int だけで
      ## 使ってもいいように場合の数を求める関数を拡張する
      proc f*(n: mint; r: int): mint = f(n, mint(r))
      proc f*(n: int; r: mint): mint = f(mint(n), r)
      proc f*(n, r: int): int = f(mint(n), mint(r)).toInt

    proc C*(n, r: mint): mint =
      let (n, r) = (n.toInt, r.toInt)
      if r < 0 or n < r: mint(0)
      else: facs[n] * facInvs[r] * facInvs[n - r]
    extendNumberOfCases(C)

    proc P*(n, r: mint): mint =
      let (n, r) = (n.toInt, r.toInt)
      if r < 0 or n < r: mint(0)
      else: facs[n] * facInvs[n - r]
    extendNumberOfCases(P)

    proc H*(n, r: mint): mint =
      if r == 0: mint(1)
      else: C(n + r - 1, r)
    extendNumberOfCases(H)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
const MOD = 1_000_000_007

useMint(MOD)

inputs:
  (N, p) : int

if N == 1:
  echo 0
  quit()
if N == 2:
  echo 1
  quit()

var a = newSeq[mint](N)
a[1] = 1.toMint
for i in 2..<N:
  a[i] = p * a[i - 1] + a[i - 2]

var
  sum = 0.toMint
  result = 0.toMint
for i in 0..<N:
  sum += a[i]
  result += a[i] * sum

echo result
0