結果
問題 | No.1186 長方形の敷き詰め |
ユーザー |
![]() |
提出日時 | 2020-08-22 14:12:27 |
言語 | Nim (2.2.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 17,207 bytes |
コンパイル時間 | 1,400 ms |
コンパイル使用メモリ | 84,892 KB |
最終ジャッジ日時 | 2024-11-14 23:32:47 |
合計ジャッジ時間 | 1,789 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
stack trace: (most recent call last) Main.nim(224, 19) inputs macros.nim(1219, 27) expectKind /home/judge/data/code/Main.nim(458, 1) template/generic instantiation of `inputs` from here /home/judge/data/code/Main.nim(459, 3) Error: Expected one of {nnkIdent, nnkPar}, got nnkTupleConstr
ソースコード
when NimMajor <= 0 and NimMinor <= 18: import future else: import sugar# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #when defined release: {.checks: off.}# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #from typetraits import arityfrom sequtils import map, mapIt, newSeqWith, toSeqfrom strutils import split, parseInt, parseFloat, parseBool, parseEnum, parseBiggestIntwhen NimMajor == 0 and NimMinor >= 14: from strutils import parseBiggestUIntimport macrosfrom terminal import setForegroundColor, ForegroundColor, resetAttributesproc warn(message: string) =when not defined release:stderr.setForegroundColor(fgYellow)stderr.write("注意: ")stderr.resetAttributesstderr.writeLine messagewhen not declared parseBiggestUInt:proc parseBiggestUInt(s: string): uint64 = uint64(parseInt(s))when not declared SomeFloat:type SomeFloat = float | float64 | float32when not defined nimHasRunnableExamples:template runnableExamples*(body: untyped) = discardproc parseT(s: string; T: typedesc): auto =## `parse` 系関数のジェネリック版## `T` が `SomeOrdinal | SomeFloat` (subranges を含む) でない場合,そのまま `s` を返すrunnableExamples:doAssert parseT("12", int) == 12doAssert parseT("12", uint) == 12doAssert parseT("12", int64) == 12doAssert parseT("12", float32) == 12.0doAssert parseT("Yes", bool) == truewhen 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: sproc 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 == 1doAssert uint32 is t.b.type and t.b == 1doAssert float64 is t.c.type and t.c == 1.0doAssert bool is t.d.type and t.d == truedoAssert tuple[a: int8, b: uint32, c: float64, d: bool] is t.typevar i = 0for x in result.fields:if i > input.high:warn "元の配列の長さが " & $T.arity & " 未満だから,一部デフォルト値になってるよ"breakx = parseT(input[i], x.type)i.incresultproc input(T: typedesc[string]): string = stdin.readLineproc input(T: typedesc[SomeOrdinal | SomeFloat | char]): auto = input(string).parseT(T)proc input(T: typedesc[seq[string]]): auto = input(string).splitproc 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 = parTupleelse: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: Tresult = 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: NimNodecase 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, ...): Tvar 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: TinputCall = 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 yproc `%=`*(x: var SomeInteger; y: SomeInteger) = x = x mod yproc `<?=`*[T](x: var T; y: T) = x = min(x, y)proc `>?=`*[T](x: var T; y: T) = x = max(x, y)# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #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 = 0for it {.inject.} in items(a):if pred: result.incresult# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #proc reversed*(s: string): string =result = newString(s.len)for i, c in s: result[s.len - i - 1] = c# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #from sequtils import newSeqWith, allIttemplate 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)# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #when not defined(release):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 vtemplate stderrEcho*(x: seq[string]) =for v in x: stderrEcho velse:template stderrEcho*(x: untyped) = discard# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #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 =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 = int(n)#--- 逆元 ---#proc inverse*(n: mint): mint =## 逆元 O(log(MOD))## 非再帰extGcd版: ax + by = 1 を満たす x が b を法とした a の逆元## 参考: https://topcoder.g.hatena.ne.jp/iwiwi/20130105/1357363348var (a, x, b, y) = (MOD, 0, n.toInt, 1)while b != 0:let tmp = a div ba -= tmp * b; swap(a, b)x -= tmp * y; swap(x, y)assert(x.toMint.toInt * n.toInt mod MOD == 1)return x.toMintproc `~`*(n: mint): mint = n.inverse#--- 単項演算子 ---#proc `+`*(n: mint): mint {.borrow.}proc `-`*(n: mint): mint = mint(MOD - n.toInt)proc `$`*(n: mint): string {.borrow.}#--- 二項演算子 ---## 比較 #template extendComparisonOperatorToInt(op: untyped) =proc op*(n: mint; m: int): bool = op(n, m.toMint)proc op*(n: int; m: mint): bool = 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) =proc op*(n: mint; m: int): mint = op(n, m.toMint)proc op*(n: int; m: mint): mint = op(n.toMint, m)proc `mod`*(n, m: mint): mint = (n.toInt mod m.toInt).toMintproc `mod`*(n: mint, m: int): mint = (n.toInt mod m).toMintproc `mod`*(n: int, m: mint): mint = (n mod m.toInt).toMintproc `%`*(n, m: mint): mint = n mod mproc `%`*(n: mint; m: int): mint = n mod mproc `%`*(n: int; m: mint): mint = n mod mproc `+`*(n, m: mint): mint = (n.toInt + m.toInt).toMintextendArithmeticOperatorToInt(`+`)proc `-`*(n, m: mint): mint = n + (-m)extendArithmeticOperatorToInt(`-`)proc `*`*(n, m: mint): mint = (n.toInt * m.toInt).toMintextendArithmeticOperatorToInt(`*`)proc `div`*(n, m: mint): mint =# O(log(MOD))n * m.inverseextendArithmeticOperatorToInt(`div`)proc `/`*(n, m: mint): mint = n div mextendArithmeticOperatorToInt(`/`)proc mul*(n: mint; m: int): mint =## MOD が大きすぎるとき用の掛け算 O(log(m)) (足し算で掛け算を計算するので)result = m.toMintvar (n, m) = (n, m)while m != 0:if (m and 1) == 1: result = result + nn = n + nm = m shr 1proc 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) = (n = n % m.int)proc `+=`*(n: var mint; m: mint | int) = (n = n + m.int)proc `-=`*(n: var mint; m: mint | int) = (n = n - m.int)proc `*=`*(n: var mint; m: mint | int) = (n = n * m.int)proc `/=`*(n: var mint; m: mint | int) = (n = n / m.int)#--- 累乗 ---#proc pow*(n: mint; m: int): mint =# O(log(m))if m < 0: return pow(n.inverse, -m)var (nn, mm) = (n, m)result = 1.toMintwhile mm != 0:if (mm and 1) == 1: result = result * nnnn = nn * nnmm = mm shr 1proc pow*(n, m: mint): mint = n.pow(m.toInt)proc pow*(n: int; m: mint): mint = n.toMint.pow(m.toInt)proc `^`*(n, m: mint): mint = n.pow(m)proc `^`*(n: mint; m: int): mint = n.pow(m)proc `^`*(n: int; m: mint): mint = n.pow(m) # これは戻り値が mint でいいのか疑問ではある#--- その他関数 ---#proc succ*(x: mint; y: int = 1): mint = x + yproc succ*(x: mint; y: mint): mint = x + yproc pred*(x: mint; y: int = 1): mint = x - yproc pred*(x: mint; y: mint): mint = x - yproc 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) # => 10proc 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] * iresult.facInvs[size] = result.facs[size].inversefor i in countdown(size - 1, 0):result.facInvs[i] = result.facInvs[i + 1] * (i + 1)let (facs, facInvs) = init() # const にすると too many iterationstemplate 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)).toIntproc 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 = 998244353useMint(MOD)useNumberOfCases(2_000_000)inputs:(N, M): intvar result = 0.toMintif N == 1:result = 1.toMintelse:for t in 0..M: # 縦に置くピースの数let W = M - tif W mod N == 0:result += (t + W div N).C(t)stderrEcho (M:M,N:N,t:t,C:(t + W div N).C(t))echo result