#506117 (Nim) No.1105 Many Triplets

提出ソース

結果

問題	No.1105 Many Triplets
ユーザー	chaemon
提出日時	2020-07-03 22:00:48
言語	Nim (2.0.2)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	9,782 bytes
コンパイル時間	5,141 ms
コンパイル使用メモリ	76,528 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-17 02:15:31
合計ジャッジ時間	7,178 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	1 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	1 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	1 ms 4,348 KB
testcase_12	AC	2 ms 4,348 KB
testcase_13	AC	2 ms 4,348 KB
testcase_14	AC	2 ms 4,348 KB
testcase_15	AC	1 ms 4,348 KB
testcase_16	AC	1 ms 4,348 KB
testcase_17	AC	1 ms 4,348 KB
testcase_18	AC	2 ms 4,348 KB
testcase_19	AC	2 ms 4,348 KB
testcase_20	AC	1 ms 4,348 KB
testcase_21	AC	2 ms 4,348 KB
testcase_22	AC	2 ms 4,348 KB
testcase_23	AC	1 ms 4,348 KB
testcase_24	AC	2 ms 4,348 KB
testcase_25	AC	1 ms 4,348 KB
testcase_26	AC	2 ms 4,348 KB
testcase_27	AC	1 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#{{{ header
{.hints:off warnings:off optimization:speed.}
import algorithm, sequtils, tables, macros, math, sets, strutils, strformat, sugar
when defined(MYDEBUG):
  import header

import streams
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
#proc getchar(): char {.header: "<stdio.h>", varargs.}
proc nextInt(): int = scanf("%lld",addr result)
proc nextFloat(): float = scanf("%lf",addr result)
proc nextString[F](f:F): string =
  var get = false
  result = ""
  while true:
#    let c = getchar()
    let c = f.readChar
    if c.int > ' '.int:
      get = true
      result.add(c)
    elif get: return
proc nextInt[F](f:F): int = parseInt(f.nextString)
proc nextFloat[F](f:F): float = parseFloat(f.nextString)
proc nextString():string = stdin.nextString()

template `max=`*(x,y:typed):void = x = max(x,y)
template `min=`*(x,y:typed):void = x = min(x,y)
template inf(T): untyped = 
  when T is SomeFloat: T(Inf)
  elif T is SomeInteger: ((T(1) shl T(sizeof(T)*8-2)) - (T(1) shl T(sizeof(T)*4-1)))
  else: assert(false)

proc discardableId[T](x: T): T {.discardable.} =
  return x
macro `:=`(x, y: untyped): untyped =
  var strBody = ""
  if x.kind == nnkPar:
    for i,xi in x:
      strBody &= fmt"""
{xi.repr} := {y[i].repr}
"""
  else:
    strBody &= fmt"""
when declaredInScope({x.repr}):
  {x.repr} = {y.repr}
else:
  var {x.repr} = {y.repr}
"""
  strBody &= fmt"discardableId({x.repr})"
  parseStmt(strBody)


proc toStr[T](v:T):string =
  proc `$`[T](v:seq[T]):string =
    v.mapIt($it).join(" ")
  return $v

proc print0(x: varargs[string, toStr]; sep:string):string{.discardable.} =
  result = ""
  for i,v in x:
    if i != 0: addSep(result, sep = sep)
    add(result, v)
  result.add("\n")
  stdout.write result

var print:proc(x: varargs[string, toStr])
print = proc(x: varargs[string, toStr]) =
  discard print0(@x, sep = " ")

template makeSeq(x:int; init):auto =
  when init is typedesc: newSeq[init](x)
  else: newSeqWith(x, init)

macro Seq(lens: varargs[int]; init):untyped =
  var a = fmt"{init.repr}"
  for i in countdown(lens.len - 1, 0): a = fmt"makeSeq({lens[i].repr}, {a})"
  parseStmt(a)

template makeArray(x; init):auto =
  when init is typedesc:
    var v:array[x, init]
  else:
    var v:array[x, init.type]
    for a in v.mitems: a = init
  v

macro Array(lens: varargs[typed], init):untyped =
  var a = fmt"{init.repr}"
  for i in countdown(lens.len - 1, 0):
    a = fmt"makeArray({lens[i].repr}, {a})"
  parseStmt(a)
# }}}

const Mod = 1000000007

# ModInt {{{
# ModInt[Mod] {{{
type ModInt[Mod: static[int]] = object
  v:int32

proc initModInt(a:SomeInteger, Mod:static[int]):ModInt[Mod] =
  var a = a.int
  a = a mod Mod
  if a < 0: a += Mod
  result.v = a.int32

macro declareModInt(Mod:static[int], t: untyped):untyped =
  var strBody = ""
  strBody &= fmt"""
type {t.repr} = ModInt[{Mod.repr}]
converter to{t.repr}(a:SomeInteger):{t.repr} = initModInt(a, {Mod.repr})
proc init{t.repr}(a:SomeInteger):{t.repr} = initModInt(a, {Mod.repr})
proc `$`(a:{t.repr}):string = $(a.v)
"""
  parseStmt(strBody)

when declared(Mod): declareModInt(Mod, Mint)
##}}}

# ModIntDynamic {{{
type DMint = object
  v:int32

proc setModSub(self:typedesc, m:int = -1, update = false):int32 {.discardable.} =
  var DMOD {.global.}:int32
  if update: DMOD = m.int32
  return DMOD

proc fastMod(a:int,m:uint32):uint32{.inline.} =
  var
    minus = false
    a = a
  if a < 0:
    minus = true
    a = -a
  elif a < m.int:
    return a.uint32
  var
    xh = (a shr 32).uint32
    xl = a.uint32
    d:uint32
  asm """
    "divl %4; \n\t"
    : "=a" (`d`), "=d" (`result`)
    : "d" (`xh`), "a" (`xl`), "r" (`m`)
  """
  if minus and result > 0'u32: result = m - result
proc initDMint(a:SomeInteger, Mod:int):DMint =
  var a = fastMod(a.int, Mod.uint32).int
  result.v = a.int32
#}}}

# Operations {{{
type ModIntC = concept x, type T
  x.v

proc getMod[T](self: T):int32 =
  when T is ModInt:
    return T.Mod
  else:
    return T.type.setModSub()
proc getMod(self: typedesc):int32 =
  when self is ModInt:
    return self.Mod
  else:
    return self.setModSub()

proc setMod(self: typedesc, m:int) =
  self.setModSub(m, true)

proc Identity(self:ModIntC):auto = result = self;result.v = 1
proc makeModInt[Mod:static[int], T](self:ModInt[Mod], a:T):ModInt[Mod] =
  when a is ModInt[Mod]:
    return a
  else:
    initModInt(a, Mod)

proc makeModInt[T](self:ModIntC and not ModInt, a:T):typeof(self) =
  when a is self.type:
    a
  else:
    (var r = self.type.default;r.v = fastMod(a.int, self.getMod().uint32).int32;r)

macro declareDMintConverter(t:untyped) =
  parseStmt(fmt"""
converter to{t.repr}(a:int):{t.repr} =
  let Mod = {t.repr}.getMod()
  if Mod > 0:
    result.v = fastMod(a.int, Mod.uint32).int32
  else:
    result.v = a.int32
    doAssert(false)
  return result
""")

declareDMintConverter(DMint)

macro declareDMint(t:untyped) =
  parseStmt(fmt"""
type {t.repr} {{.borrow: `.`.}} = distinct DMint
declareDMintConverter({t.repr})
""")

proc `*=`[T](self:var ModIntC, a:T) =
  when self is ModInt:
    self.v = (self.v.int * self.makeModInt(a).v.int mod self.getMod().int).int32
  else:
    self.v = fastMod(self.v.int * self.makeModInt(a).v.int, self.getMod().uint32).int32
proc `==`[T](a:ModIntC, b:T):bool = a.v == a.makeModInt(b).v
proc `!=`[T](a:ModIntC, b:T):bool = a.v != a.makeModInt(b).v
proc `-`(self:ModIntC):auto =
  if self.v == 0: return self
  else: return self.makeModInt(self.getMod() - self.v)
proc `$`(a:ModIntC):string = return $(a.v)

proc `+=`[T](self:var ModIntC; a:T) =
  self.v += self.makeModInt(a).v
  if self.v >= self.getMod(): self.v -= self.getMod()
proc `-=`[T](self:var ModIntC, a:T) =
  self.v -= self.makeModInt(a).v
  if self.v < 0: self.v += self.getMod()
proc `^=`(self:var ModIntC, n:int) =
  var (x,n,a) = (self,n,self.Identity)
  while n > 0:
    if (n and 1) > 0: a *= x
    x *= x
    n = (n shr 1)
  swap(self, a)
proc inverse(self: ModIntC):auto =
  var
    a = self.v.int
    b = self.getMod().int
    u = 1
    v = 0
  while b > 0:
    let t = a div b
    a -= t * b;swap(a, b)
    u -= t * v;swap(u, v)
  return self.makeModInt(u)
proc `/=`[T](a:var ModIntC,b:T) =
  a *= a.makeModInt(b).inverse()
proc `+`[T](a:ModIntC,b:T):auto = result = a;result += b
proc `-`[T](a:ModIntC,b:T):auto = result = a;result -= b
proc `*`[T](a:ModIntC,b:T):auto = result = a;result *= b
proc `/`[T](a:ModIntC,b:T):auto = result = a;result /= b
proc `^`(a:ModIntC,b:int):auto = result = a;result ^= b
# }}}
# }}}

#{{{ pow[T]: Identity and *= must be defined
#proc Identity(self: seq[int]): seq[int] =
#  return lc[i | (i <- 0..<self.len), int]

proc `^=`[T](self: var T, k:int) =
  var k = k
  var B = self.IdentityMat()
  while k > 0:
    if (k and 1) > 0: B *= self
    self *= self;k = k shr 1
  self.swap(B)

proc `^`[T](self: T, k:int):T =
  result = self;result ^= k
#}}}

# Matrix {{{
import sequtils

type Matrix[T] = seq[seq[T]]
type Vector[T] = seq[T]

proc initMatrix[T](self: Matrix[T]):Matrix[T] = return self
proc initMatrix[T](n:int, m: int):Matrix[T] = Matrix[T](newSeqWith(n, newSeqWith(m, T.default)))
proc initMatrix[T](n:int):Matrix[T] = Matrix[T](newSeqWith(n, newSeqWith(n, T.default)))

proc initVector[T](n:int):Vector[T] = Vector[T](newSeqWith(n, T.default))

proc height[T](self: Matrix[T]):int = self.len
proc width[T](self: Matrix[T]):int = self[0].len

proc IdentityMat[T](n:int):Matrix[T] =
  result = initMatrix[T](n)
  for i in 0..<n: result[i][i] = T(1)
proc IdentityMat[T](self: Matrix[T]):Matrix[T] =
  result = initMatrix[T](self.len)
  for i in 0..<self.len: result[i][i] = T(1)

proc `+=`[T](self: var Matrix[T], B: Matrix[T]) =
  let (n, m) = (self.height, self.width)
  assert(n == B.height() and m == B.width())
  for i in 0..<n:
    for j in 0..<m:
      self[i][j] += B[i][j]

proc `-=`[T](self: var Matrix[T], B: Matrix[T]) =
  let (n, m) = (self.height, self.width)
  assert(n == B.height() and m == B.width())
  for i in 0..<n:
    for j in 0..<m:
      self[i][j] -= B[i][j]

proc `*=`[T](self: var Matrix[T], B: Matrix[T]) =
  let (n,m,p) = (self.height, B.width, self.width)
  assert(p == B.height())
  var C = initMatrix[T](n, m)
  for i in 0..<n:
    for j in 0..<m:
      for k in 0..<p:
        C[i][j] += self[i][k] * B[k][j]
  swap(self, C)
proc `*`[T](self: Matrix[T], v: Vector[T]): Vector[T] =
  let (n,m) = (self.height, self.width)
  result = initVector[T](n)
  assert(v.len == m)
  var C = initMatrix[T](n, m)
  for i in 0..<n:
    for j in 0..<m:
        result[i] += self[i][j] * v[j]

proc `+`[T](self: Matrix[T], B:Matrix[T]):Matrix[T] =
  result = self; result += B
proc `-`[T](self: Matrix[T], B:Matrix[T]):Matrix[T] =
  result = self; result -= B
proc `*`[T](self: Matrix[T], B:Matrix[T]):Matrix[T] =
  result = self; result *= B

proc `$`[T](self: Matrix[T]):string =
  result = ""
  let (n,m) = (self.height, self.width)
  for i in 0..<n:
    result &= "["
    for j in 0..<m:
      result &= $(self[i][j])
      result &= (if j + 1 == m: "]\n" else: ",")

proc determinant[T](self: Matrix[T]):T =
  var B = initMatrix(self)
  assert(self.width() == self.height());
  result = T(1)
  for i in 0..<self.width():
    var idx = -1
    for j in i..<self.width():
      if B[j][i] != T(0): idx = j
    if idx == -1: return T(0)
    if i != idx:
      result *= T(-1)
      swap(B[i], B[idx])
    result *= B[i][i];
    let vv = B[i][i]
    for j in 0..<self.width():
      B[i][j] /= vv
    for j in i+1..<self.width():
      let a = B[j][i]
      for k in 0..<self.width():
        B[j][k] -= B[i][k] * a;
# }}}


var N, A, B, C = nextInt()
N = N - 1

M := initMatrix[Mint](3, 3)
M[0][0] = 1
M[1][1] = 1
M[2][2] = 1
M[0][1] = -1
M[1][2] = -1
M[2][0] = -1
v := initVector[Mint](3)
v[0] = A
v[1] = B
v[2] = C
M^=N
v = M*v
print v[0], v[1], v[2]

yukicoder

結果

テストケース

ソースコード