結果

問題 No.754 畳み込みの和
ユーザー nadeshinonadeshino
提出日時 2020-02-22 03:43:55
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,831 bytes
コンパイル時間 962 ms
コンパイル使用メモリ 81,080 KB
最終ジャッジ日時 2024-11-14 22:08:02
合計ジャッジ時間 1,342 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(160, 22) Error: type mismatch
Expression: N + 1
  [1] N: (int,)
  [2] 1: int literal(1)

Expected one of (first mismatch at [position]):
[1] func `+`[T](x, y: Complex[T]): Complex[T]
[1] func `+`[T](x, y: set[T]): set[T]
[1] func `+`[T](x: Complex[T]; y: T): Complex[T]
[1] proc `+`(a, b: Duration): Duration
[1] proc `+`(a: Time; b: Duration): Time
[1] proc `+`(dt: DateTime; dur: Duration): DateTime
[1] proc `+`(dt: DateTime; interval: TimeInterval): DateTime
[1] proc `+`(n`gensym0: ModInt): ModInt
[1] proc `+`(n`gensym0: ModInt; m`gensym0: ModInt): ModInt
[1] proc `+`(n`gensym0: ModInt; m`gensym0: int): ModInt
[1] proc `+`(n`gensym0: int; m`gensym0: ModInt): ModInt
[1] proc `+`(ti1, ti2: TimeInterval): TimeInterval
[1] proc `+`(time: Time; interval: TimeInterval): Time
[1] proc `+`(x, y: float): float
[1] proc `+`(x, y: float32): float32
[1] proc `+`(x, y: int): int
[1] proc `+`(x, y: int16): int16
[1] proc `+`(x, y: int32): int32
[1] proc `+`(x, y: int64): int64
[1] proc `+`(x, y: int8): int8
[1] proc `+`(x, y: uint): uint
[1] proc `+`(x, y: uint16): uint16
[1] proc `+`(x, y: uint32): uint32
[1] proc `+`(x, y: uint64): uint64
[1] proc `+`(x, y: uint8): uint8
[1] proc `+`(x: float): float
[1] proc `+`(x: float32): float32
[1] proc `+`(x: int): int
[1] proc `+`(x: int16): int16
[1] proc `+`(x: int32): int32
[1] proc `+`(x: int64): int64
[1] proc `+`(x: int8): int8
[1] proc `+`[A](s1, s2: HashSet[A]): HashSet[A]
[2] func `+`[T](x: T; y: Complex[T]): Complex[T]

ソースコード

diff #

import algorithm, complex, macros, math, sequtils, sets, strutils, tables, times

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

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

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

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.} =
    ModInt(int(n) + m - p * int(int(n) + m >= p))
  proc `+`*(n: int, m: ModInt): ModInt {.inline.} =
    ModInt(n + int(m) - p * int(n + int(m) >= p))
  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.} =
    ModInt(int(n) - m + p * int(int(n) - m < 0))
  proc `-`*(n: int, m: ModInt): ModInt {.inline.} =
    ModInt(n - int(m) + p * int(n - int(m) < 0))
  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

  proc pow*(n: ModInt, m: int): ModInt {.inline.} =
    if m < 0:
      return pow(n, m + p - 1)
    result = ModInt(1)
    var (n, m) = (n, m)
    while m > 0:
      if (m and 1) == 1:
        result = result * n
      n = n * n
      m = m shr 1

  proc pow*(n: int, m: int): ModInt {.inline.} =
    pow(toModInt(n), m)

  template useNumberOfCases*(size = 2500000) =
    proc initNumberOfCases: tuple[facts, invs, invFacts: array[0 .. size, ModInt]] =
      var facts, invs, invFacts: array[0 .. size, ModInt]
      facts[0] = ModInt(1); facts[1] = ModInt(1)
      invs[1] = ModInt(1)
      invFacts[0] = ModInt(1); invFacts[1] = ModInt(1)
      for i in 2 .. size:
        facts[i] = facts[i - 1] * i
        invs[i] = invs[p mod i] * (p div i) * (-1)
        invFacts[i] = invFacts[i - 1] * invs[i]
      return (facts, invs, invFacts)
    let (facts, invs, invFacts) = initNumberOfCases()

    proc fact*(n: range[0 .. size]): ModInt {.inline.} =
      facts[n]
    
    proc inv*(n: range[1 .. size]): ModInt {.inline.} =
      invs[n]

    proc invFact*(n: range[0 .. size]): ModInt {.inline.} =
      invFacts[n]

    proc comb*(n, k: int): ModInt {.inline.} =
      assert n <= size
      if k < 0 or n < k: ModInt(0)
      else: facts[n] * invFacts[k] * invFacts[n - k]
    proc comb*(n: ModInt, k: int): ModInt {.inline.} = comb(int(n), k)
    proc comb*(n: int, k: ModInt): ModInt {.inline.} = comb(n, int(k))
    proc comb*(n, k: ModInt): ModInt {.inline.} = comb(int(n), int(k))

    proc perm*(n, k: int): ModInt {.inline.} =
      assert n <= size
      if k < 0 or n < k: ModInt(0)
      else: facts[n] * invFacts[n - k]
    proc perm*(n: ModInt, k: int): ModInt {.inline.} = perm(int(n), k)
    proc perm*(n: int, k: ModInt): ModInt {.inline.} = perm(n, int(k))
    proc perm*(n, k: ModInt): ModInt {.inline.} = perm(int(n), int(k))
    
# -------------------------------------------------- #

useModInt(10 ^ 9 + 7)

let N = input(int)
let A = newSeqWith(N + 1, input(int))
let B = newSeqWith(N + 1, input(int))
var C = ModInt(0)
for a in A:
  C += a
var res = ModInt(0)
for i in 0 .. N:
  res += C * B[i]
  C -= A[N - i]
echo res
0