#589247 (Nim) No.1307 Rotate and Accumulate

• 問題: No.1307 Rotate and Accumulate
• ユーザー: zer0-star
• 提出日時: 2020-12-04 20:25:53
• 言語: Nim (2.0.2)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 11,541 bytes
• コンパイル時間: 2,157 ms
• コンパイル使用メモリ: 60,036 KB
• 最終ジャッジ日時: 2023-10-13 10:08:44
• 合計ジャッジ時間: 3,102 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

コンパイルメッセージ

/home/judge/data/code/Main.nim(414, 27) Error: undeclared identifier: 'N'
candidates (edit distance, scope distance); see '--spellSuggest': 
 (1, 1): '*' [proc declared in /home/judge/data/code/Main.nim(253, 8)]
 (1, 1): '*' [proc declared in /home/judge/data/code/Main.nim(265, 8)]
 (1, 1): '+' [proc declared in /home/judge/data/code/Main.nim(241, 8)]
 (1, 1): '+' [proc declared in /home/judge/data/code/Main.nim(257, 8)]

ソースコード

# ========= utils/base.nim ========= {{{

when not declared(INCLUDE_GUARD_UTILS_BASE_NIM):
  const INCLUDE_GUARD_UTILS_BASE_NIM = 1
  import macros
  macro Please(x): untyped = nnkStmtList.newTree()

  Please give me AC
  Please give me AC
  Please give me AC

  {.hints: off, overflowChecks: on.}

  import strutils, sequtils, math, algorithm, strformat
  when (not (NimMajor <= 0)) or NimMinor >= 19:
    import sugar
  else:
    import future

  iterator range(x, y: int): int {.inline.} =
    var res = x
    while res < y:
      yield res
      inc(res)
  iterator range(x: int): int {.inline.} =
    var res = 0
    while res < x:
      yield res
      inc(res)
  proc range(x, y: int): seq[int] {.inline.} =
    toSeq(x..y-1)
  proc range(x: int): seq[int] {.inline.} =
    toSeq(0..x-1)
  proc discardableId[T](x: T): T {.inline, discardable.} =
    return x
  macro `:=`(x, y: untyped): untyped =
    if (x.kind == nnkIdent):
      return quote do:
        when declaredInScope(`x`):
          `x` = `y`
        else:
          var `x` = `y`
        discardableId(`x`)
    else:
      return quote do:
        `x` = `y`
        discardableId(`x`)
  when NimMajor <= 0 and NimMinor <= 17:
    proc count[T](co: openArray[T]; obj: T): int =
      for itm in items(co):
        if itm == obj:
          inc result
  proc divmod(x, y: SomeInteger): (int, int) =
    (x div y, x mod y)
  proc `min=`[T](x: var T; y: T): bool {.discardable.} =
    if x > y:
      x = y
      return true
    else:
      return false
  proc `max=`[T](x: var T; y: T): bool {.discardable.} =
    if x < y:
      x = y
      return true
    else:
      return false

  when NimMajor <= 0 and NimMinor <= 17:
    iterator pairs(n: NimNode): (int, NimNode) {.inline.} =
      for i in 0 ..< n.len:
        yield (i, n[i])

  #[
  when NimMajor <= 0 and NimMinor <= 18:
    macro parseInnerType(x: NimNode): untyped =
      newIdentNode("parse" & x[1][1].repr)
  else:
    macro parseInnerType(x: typedesc): untyped =
      newIdentNode("parse" & x.getType[1][1].repr)
  ]#

  proc parseInnerType(x: NimNode): NimNode =
    newIdentNode("parse" & x[1].repr)

  proc inputAsTuple(ty: NimNode): NimNode =
    result = nnkStmtListExpr.newTree()
    t := genSym()
    result.add quote do: (let `t` = stdin.readLine.split)
    p := nnkPar.newTree()
    for i, typ_tmp in ty.pairs:
      var ece, typ: NimNode
      if typ_tmp.kind == nnkExprColonExpr:
        ece = nnkExprColonExpr.newTree(typ_tmp[0])
        typ = typ_tmp[1]
      else:
        ece = nnkExprColonExpr.newTree(ident("f" & $i))
        typ = typ_tmp
      if typ.repr == "string":
        ece.add quote do: `t`[`i`]
      else:
        parsefn := newIdentNode("parse" & typ.repr)
        ece.add quote do: `t`[`i`].`parsefn`
      p.add ece
    result.add p

  macro inputAsType(ty: untyped): untyped =
    if ty.kind == nnkBracketExpr:
      if ty[1].repr == "string":
        return quote do: stdin.readLine.split
      else:
        parsefn := parseInnerType(ty)
        return quote do: stdin.readLine.split.map(`parsefn`)
        #[
          when NimMajor <= 0 and NimMinor <= 18:
            stdin.readLine.split.map(parseInnerType(ty.getType))
          else:
            stdin.readLine.split.map(parseInnerType(ty))
        ]#
    elif ty.kind == nnkPar:
      return inputAsTuple(ty)
    elif ty.repr == "string":
      return quote do: stdin.readLine
    else:
      parsefn := ident("parse" & ty.repr)
      return quote do: stdin.readLine.`parsefn`

  macro input(query: untyped): untyped =
    doAssert query.kind == nnkStmtList
    result = nnkStmtList.newTree()
    letSect := nnkLetSection.newTree()
    for defs in query:
      if defs[0].kind == nnkIdent:
        tmp := nnkIdentDefs.newTree(defs[0], newEmptyNode())
        typ := defs[1][0]
        var val: NimNode
        if typ.len <= 2:
          val = quote do: inputAsType(`typ`)
        else:
          op := typ[2]
          typ.del(2, 1)
          val = quote do: inputAsType(`typ`).mapIt(`op`)
        if defs[1].len > 1:
          op := defs[1][1]
          it := ident"it"
          tmp.add quote do:
            block:
              var `it` = `val`
              `op`
        else:
          tmp.add val
        letSect.add tmp
      elif defs[0].kind == nnkPar:
        vt := nnkVarTuple.newTree()
        for id in defs[0]:
          vt.add id
        vt.add newEmptyNode()
        sle := nnkStmtListExpr.newTree()
        t := genSym()
        sle.add quote do: (let `t` = stdin.readLine.split)
        p := nnkPar.newTree()
        if defs[1][0].kind == nnkPar:
          for i, typ in defs[1][0].pairs:
            if typ.repr == "string":
              p.add quote do: `t`[`i`]
            else:
              parsefn := newIdentNode("parse" & typ.repr)
              p.add quote do: `t`[`i`].`parsefn`
        else:
          typ := defs[1][0]
          if typ.repr == "string":
            for i in 0..<defs[0].len:
              p.add quote do: `t`[`i`]
          else:
            parsefn := newIdentNode("parse" & typ.repr)
            for i in 0..<defs[0].len:
              p.add quote do: `t`[`i`].`parsefn`
        sle.add p
        vt.add sle
        letSect.add vt
      elif defs[0].kind == nnkBracketExpr:
        ids := nnkIdentDefs.newTree(defs[0][0], newEmptyNode())
        cnt := defs[0][1]
        typ := defs[1][0]
        var input: NimNode
        if typ.kind == nnkBracketExpr and typ.len > 2:
          op := typ[2]
          typ.del(2, 1)
          input = quote do: inputAsType(`typ`).mapIt(`op`)
        else:
          input = quote do: inputAsType(`typ`)
        var val: NimNode
        if defs[0].len > 2:
          op := defs[0][2]
          it := ident"it"
          val = quote do:
            block:
              var `it` = `input`
              `op`
        else:
          val = input
        if defs[1].len > 1:
          op := defs[1][1]
          it := ident"it"
          ids.add(quote do:
            block:
              var `it` = newSeqWith(`cnt`, `val`)
              `op`)
        else:
          ids.add(quote do: newSeqWith(`cnt`, `val`))
        letSect.add ids
    result.add letSect

  proc makeSeq[T, Idx](num: array[Idx, int]; init: T): auto =
    when num.len == 1:
      return newSeqWith(num[0], init)
    else:
      var tmp: array[num.len-1, int]
      for i, t in tmp.mpairs: t = num[i+1]
      return newSeqWith(num[0], makeSeq(tmp, init))

  proc parseInt1(str: string): int =
    str.parseInt - 1

# ========= utils/base.nim ========= }}}

# ========= math/fft.nim ========= {{{

# ========= math/complex.nim ========= {{{

when not declared(INCLUDE_GUARD_MATH_COMPLEX_NIM):
  const INCLUDE_GUARD_MATH_COMPLEX_NIM = 1

  import math

  type Complex = object
    re, im: float

  proc complex(re, im: float = 0.0): Complex {.inline.} =
    Complex(re: re, im: im)

  proc `+`(a, b: Complex): Complex {.inline.} =
    result.re = a.re + b.re
    result.im = a.im + b.im

  proc `-`(a: Complex): Complex {.inline.} =
    result.re = - a.re
    result.im = - a.im

  proc `-`(a, b: Complex): Complex {.inline.} =
    result.re = a.re - b.re
    result.im = a.im - b.im

  proc `*`(a, b: Complex): Complex {.inline.} =
    result.re = a.re * b.re - a.im * b.im
    result.im = a.re * b.im + a.im * b.re

  proc `+`(a: Complex; b: float): Complex {.inline.} =
    result.re = a.re + b
    result.im = a.im + b

  proc `-`(a: Complex; b: float): Complex {.inline.} =
    result.re = a.re - b
    result.im = a.im - b

  proc `*`(a: Complex; b: float): Complex {.inline.} =
    result.re = a.re * b
    result.im = a.im * b

  proc `/`(a: Complex; b: float): Complex {.inline.} =
    result.re = a.re / b
    result.im = a.im / b

  proc conj(a: Complex): Complex {.inline.} =
    result.re = a.re
    result.im = - a.im

  proc inv(a: Complex): Complex {.inline.} =
    let t = a.re * a.re + a.im * a.im
    result.re = a.re / t
    result.im = - a.im / t

  proc `|.|`(a, b: Complex): float {.inline.} =
    a.re*b.im - a.im*b.re

  proc `|*|`(a, b: Complex): float {.inline.} =
    a.re*b.re + a.im*b.im

  proc norm(a: Complex): float {.inline.} =
    a |*| a

  proc abs(a: Complex): float {.inline.} =
    sqrt(norm(a))

  proc `/`(a, b: Complex): Complex {.inline.} =
    a * inv(b)

  proc `+=`(a: var Complex; b: Complex) {.inline.} =
    a = a + b

  proc `-=`(a: var Complex; b: Complex) {.inline.} =
    a = a - b

  proc `*=`(a: var Complex; b: Complex) {.inline.} =
    a = a * b

  proc `/=`(a: var Complex; b: Complex) {.inline.} =
    a = a / b

# ========= math/complex.nim ========= }}}


# ========= math/polynomial.nim ========= {{{

when not declared(INCLUDE_GUARD_MATH_POLYNOMIAL_NIM):
  const INCLUDE_GUARD_MATH_POLYNOMIAL_NIM = 1
  import sequtils, math

  type
    Polynomial[T] = object
      coeffs: seq[T]

  proc initPolynomial[T](a: seq[T]): Polynomial[T] {.inline.} =
    Polynomial[T](coeffs: a)

  proc initPolynomial[T](n: int): Polynomial[T] {.inline.} =
    Polynomial[T](coeffs: newSeq[T](n))

  proc expand[T](a: var Polynomial[T]; size: int) {.inline.} =
    if a.len < size:
      a.coeffs.setLen(size)

  proc `+`[T](a, b: Polynomial[T]): Polynomial[T] =
    result = a
    result.expand(max(a.coeffs.len, b.coeffs.len))
    for i, t in b:
      result.coeffs[i] += t

  proc `-`[T](a: Polynomial[T]): Polynomial[T] {.inline.} =
    result.coeffs = a.coeffs.mapIt(-it)

  proc `-`[T](a, b: Polynomial[T]): Polynomial[T] {.inline.} =
    a + (-b)

  proc at[T](a: Polynomial[T]; t: int): T {.inline.} =
    a.coeffs[t]

  proc `[]`[T](a: Polynomial[T]; t: int): T {.inline.} =
    a.at(t)

  proc `[]=`[T](a: var Polynomial[T]; t: Natural; c: T) {.inline.} =
    a.coeffs[t] = c

  proc call[T, S](a: Polynomial[T]; x: S): S {.inline.} =
    var t = x
    result = a[0]
    for i in 1 ..< a.len:
      result += t * a[i]
      t *= x

  proc len[T](a: Polynomial[T]): int {.inline.} =
    a.coeffs.len

# ========= math/polynomial.nim ========= }}}


when not declared(INCLUDE_GUARD_MATH_FFT_NIM):
  const INCLUDE_GUARD_MATH_FFT_NIM = 1
  import sequtils, math

  proc fft[T](f: Polynomial[T]; zeta: Complex): Polynomial[Complex] =
    assert f.len.isPowerOfTwo
    if f.len == 1:
      when T is float:
        return initPolynomial(@[f[0].complex])
      elif T is Complex:
        return initPolynomial(@[f[0]])
      elif T is int:
        return initPolynomial(@[f[0].float.complex])
    let dlen = f.len div 2
    result = initPolynomial[Complex](f.len)
    var f0, f1 = initPolynomial[T](dlen)
    for i in 0..<dlen:
      f0[i] = f[2*i]
      f1[i] = f[2*i+1]
    let
      ff0 = fft(f0, zeta*zeta)
      ff1 = fft(f1, zeta*zeta)
    var t = 1.complex
    for i in 0 ..< f.len:
      result[i] = ff0[i mod dlen] + ff1[i mod dlen] * t
      t *= zeta

  proc fftConvolute[T](f, g: Polynomial[T]): Polynomial[float] =
    var
      f = f
      g = g
    let
      flen = (f.len + g.len - 1).nextPowerOfTwo
      zeta = complex(cos(2*PI/float(flen)), sin(2*PI/float(flen)))
    f.expand(flen)
    g.expand(flen)
    let F = initPolynomial(zip(f.fft(zeta).coeffs, g.fft(zeta).coeffs).map((
        it: (Complex, Complex)) => it[0]*it[1]))
    result.coeffs = F.fft(inv(zeta)).coeffs.mapIt(it.re/float(flen))

# ========= math/fft.nim ========= }}}

input:
  (N, Q): int
  a: seq[int]; it.initPolynomial()
  r: seq[int]

var
  c = initPolynomial[int](N)
  b = newSeq[int](N)

for p in r:
  c.coeffs[(N-p) mod N].inc()

for i, v in fftConvolute(a, c).coeffs:
  b[i mod N] += int(round(v))

echo b.join(" ")