結果

問題 No.978 Fibonacci Convolution Easy
ユーザー nadeshinonadeshino
提出日時 2020-01-31 22:03:27
言語 Nim
(2.0.2)
結果
AC  
実行時間 69 ms / 2,000 ms
コード長 3,939 bytes
コンパイル時間 3,358 ms
コンパイル使用メモリ 73,472 KB
実行使用メモリ 34,304 KB
最終ジャッジ日時 2024-09-18 20:58:36
合計ジャッジ時間 4,615 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 27 ms
15,124 KB
testcase_02 AC 15 ms
9,088 KB
testcase_03 AC 64 ms
32,896 KB
testcase_04 AC 18 ms
10,624 KB
testcase_05 AC 5 ms
5,376 KB
testcase_06 AC 24 ms
13,472 KB
testcase_07 AC 43 ms
22,400 KB
testcase_08 AC 29 ms
16,384 KB
testcase_09 AC 50 ms
25,244 KB
testcase_10 AC 69 ms
34,136 KB
testcase_11 AC 20 ms
11,776 KB
testcase_12 AC 4 ms
5,376 KB
testcase_13 AC 24 ms
13,272 KB
testcase_14 AC 8 ms
5,888 KB
testcase_15 AC 27 ms
14,748 KB
testcase_16 AC 67 ms
34,304 KB
testcase_17 AC 68 ms
34,176 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 1 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 8) Warning: imported and not used: 'algorithm' [UnusedImport]
/home/judge/data/code/Main.nim(1, 19) Warning: imported and not used: 'complex' [UnusedImport]
/home/judge/data/code/Main.nim(1, 58) Warning: imported and not used: 'strformat' [UnusedImport]
/home/judge/data/code/Main.nim(1, 79) Warning: imported and not used: 'sugar' [UnusedImport]

ソースコード

diff # 

import algorithm, complex, macros, math, sequtils, sets, strformat, strutils, sugar, tables

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])

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)))

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

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 (N, p) = input(int, 2)
if N == 1:
  echo 0
  quit()
var A = newSeq[ModInt](N + 1)
A[1] = initModInt(0)
A[2] = initModInt(1)
for i in 3 .. N:
  A[i] += p * A[i - 1]
  A[i] += A[i - 2]
var cum = newSeq[ModInt](N + 2)
for i in countdown(N, 1):
  cum[i] = cum[i + 1] + A[i]
var res = initModInt(0)
for i in 1 .. N:
  res += A[i] * cum[i]
echo res
0