結果
| 問題 |
No.1667 Forest
|
| コンテスト | |
| ユーザー |
 yuly3
|
| 提出日時 | 2021-11-06 13:33:36 |
| 言語 | Nim (2.2.0) |
| 結果 |
AC
|
| 実行時間 | 354 ms / 3,000 ms |
| コード長 | 6,180 bytes |
| コンパイル時間 | 4,359 ms |
| コンパイル使用メモリ | 73,308 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-07 09:49:46 |
| 合計ジャッジ時間 | 7,380 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 |
コンパイルメッセージ
/home/judge/data/code/Main.nim(13, 5) Warning: imported and not used: 'strformat' [UnusedImport] /home/judge/data/code/Main.nim(12, 5) Warning: imported and not used: 'sequtils' [UnusedImport] /home/judge/data/code/Main.nim(15, 5) Warning: imported and not used: 'sugar' [UnusedImport]
ソースコード
when not declared ATCODER_YULY3HEADER_HPP:
const ATCODER_YULY3HEADER_HPP* = 1
import
algorithm,
bitops,
deques,
heapqueue,
math,
macros,
sets,
sequtils,
strformat,
strutils,
sugar,
tables
proc transLastStmt(n, res, bracketExpr: NimNode): (NimNode, NimNode, NimNode) =
# Looks for the last statement of the last statement, etc...
case n.kind
of nnkIfExpr, nnkIfStmt, nnkTryStmt, nnkCaseStmt:
result[0] = copyNimTree(n)
result[1] = copyNimTree(n)
result[2] = copyNimTree(n)
for i in ord(n.kind == nnkCaseStmt)..<n.len:
(result[0][i], result[1][^1], result[2][^1]) = transLastStmt(n[i], res, bracketExpr)
of nnkStmtList, nnkStmtListExpr, nnkBlockStmt, nnkBlockExpr, nnkWhileStmt,
nnkForStmt, nnkElifBranch, nnkElse, nnkElifExpr, nnkOfBranch, nnkExceptBranch:
result[0] = copyNimTree(n)
result[1] = copyNimTree(n)
result[2] = copyNimTree(n)
if n.len >= 1:
(result[0][^1], result[1][^1], result[2][^1]) = transLastStmt(n[^1],
res, bracketExpr)
of nnkTableConstr:
result[1] = n[0][0]
result[2] = n[0][1]
if bracketExpr.len == 1:
bracketExpr.add([newCall(bindSym"typeof", newEmptyNode()), newCall(
bindSym"typeof", newEmptyNode())])
template adder(res, k, v) = res[k] = v
result[0] = getAst(adder(res, n[0][0], n[0][1]))
of nnkCurly:
result[2] = n[0]
if bracketExpr.len == 1:
bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
template adder(res, v) = res.incl(v)
result[0] = getAst(adder(res, n[0]))
else:
result[2] = n
if bracketExpr.len == 1:
bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
template adder(res, v) = res.add(v)
result[0] = getAst(adder(res, n))
macro collect*(init, body: untyped): untyped =
runnableExamples:
import sets, tables
let data = @["bird", "word"]
## seq:
let k = collect(newSeq):
for i, d in data.pairs:
if i mod 2 == 0: d
assert k == @["bird"]
## seq with initialSize:
let x = collect(newSeqOfCap(4)):
for i, d in data.pairs:
if i mod 2 == 0: d
assert x == @["bird"]
## HashSet:
let y = initHashSet.collect:
for d in data.items: {d}
assert y == data.toHashSet
## Table:
let z = collect(initTable(2)):
for i, d in data.pairs: {i: d}
assert z == {0: "bird", 1: "word"}.toTable
let res = genSym(nskVar, "collectResult")
expectKind init, {nnkCall, nnkIdent, nnkSym}
let bracketExpr = newTree(nnkBracketExpr,
if init.kind == nnkCall: init[0] else: init)
let (resBody, keyType, valueType) = transLastStmt(body, res, bracketExpr)
if bracketExpr.len == 3:
bracketExpr[1][1] = keyType
bracketExpr[2][1] = valueType
else:
bracketExpr[1][1] = valueType
let call = newTree(nnkCall, bracketExpr)
if init.kind == nnkCall:
for i in 1 ..< init.len:
call.add init[i]
result = newTree(nnkStmtListExpr, newVarStmt(res, call), resBody, res)
proc nextString*(f: auto = stdin): string =
var get = false
result = ""
while true:
let c = f.readChar
if c.int > ' '.int:
get = true
result.add(c)
elif get: return
proc nextInt*(f: auto = stdin): int = parseInt(f.nextString)
proc nextFloat*(f: auto = stdin): float = parseFloat(f.nextString)
proc chmax*[T](n: var T, m: T) {.inline.} = n = max(n, m)
proc chmin*[T](n: var T, m: T) {.inline.} = n = min(n, m)
proc `%=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = floorMod(n, m)
proc `|=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n or m
proc `&=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n and m
proc `^=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n xor m
proc `<<=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shl m
proc `>>=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shr m
when not declared ATCODER_BINOMIAL_COEFFICIENTS_HPP:
const ATCODER_BINOMIAL_COEFFICIENTS_HPP * = 1
type BinomialCoefficients*[N: static int] = object
M: int
fact, factInv, inv: array[0..N - 1, int]
proc initBinomialCoefficients*(N: static int, M: int): BinomialCoefficients[N] =
return BinomialCoefficients[N](M: M)
proc preprocess*[N: static int](self: var BinomialCoefficients[N]) =
self.fact[0] = 1; self.fact[1] = 1
self.factInv[0] = 1; self.factInv[1] = 1
self.inv[1] = 1
for i in 2..<N:
self.fact[i] = floorMod(self.fact[i - 1]*i, self.M)
self.inv[i] = floorMod(-self.inv[self.M mod i]*(self.M div i), self.M)
self.factInv[i] = floorMod(self.factInv[i - 1]*self.inv[i], self.M)
proc nCr*[N: static int](self: var BinomialCoefficients[N], n, r: int): int =
if r < 0 or n < r:
return 0
let r = min(r, n - r)
return (self.fact[n]*self.factInv[r] mod self.M)*self.factInv[n - r] mod self.M
proc nHr*[N: static int](self: var BinomialCoefficients[N], n, r: int): int =
return self.nCr(n + r - 1, r)
proc nPr*[N: static int](self: var BinomialCoefficients[N], n, r: int): int =
if r < 0 or n < r:
return 0
return self.fact[n]*self.factInv[n - r] mod self.M
proc modPow*(a: int, k: Natural, MOD = 10^9 + 7): int =
var
a = a
k = k
result = 1
while k > 0:
if bitand(k, 1) == 1:
result = floorMod(result*a, MOD)
a = floorMod(a*a, MOD)
k = k shr 1
when isMainModule:
let N, MOD = nextInt()
var binom = initBinomialCoefficients(310, MOD)
binom.preprocess()
var powK: array[301, int]
for i in 2..N:
powK[i] = modPow(i, i - 2, MOD)
var dp: array[301, array[300, int]]
dp[0][0] = 1
for i in 0..<N:
for j in 0..i:
dp[i + 1][j] += dp[i][j]
if dp[i + 1][j] >= MOD: dp[i + 1][j] -= MOD
for k in 2..N - i:
var v = binom.nCr(N - i - 1, k - 1)*powK[k] mod MOD
v = v*dp[i][j] mod MOD
dp[i + k][j + k - 1] += v
if dp[i + k][j + k - 1] >= MOD: dp[i + k][j + k - 1] -= MOD
echo dp[N][0..<N].join("\n")