結果
問題 | No.1049 Zero (Exhaust) |
ユーザー | nadeshino |
提出日時 | 2020-05-08 22:14:41 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 4,840 bytes |
コンパイル時間 | 3,765 ms |
コンパイル使用メモリ | 67,892 KB |
実行使用メモリ | 18,712 KB |
最終ジャッジ日時 | 2023-09-17 03:01:44 |
合計ジャッジ時間 | 5,487 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 33 ms
13,776 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 27 ms
11,780 KB |
testcase_06 | AC | 47 ms
18,616 KB |
testcase_07 | AC | 8 ms
4,880 KB |
testcase_08 | AC | 15 ms
7,572 KB |
testcase_09 | AC | 36 ms
14,648 KB |
testcase_10 | AC | 38 ms
15,760 KB |
testcase_11 | AC | 37 ms
15,812 KB |
testcase_12 | AC | 44 ms
17,752 KB |
testcase_13 | AC | 12 ms
6,284 KB |
testcase_14 | AC | 21 ms
9,660 KB |
testcase_15 | AC | 33 ms
13,880 KB |
testcase_16 | AC | 27 ms
11,920 KB |
testcase_17 | AC | 29 ms
12,212 KB |
testcase_18 | AC | 40 ms
16,032 KB |
testcase_19 | AC | 33 ms
14,112 KB |
testcase_20 | AC | 15 ms
7,460 KB |
testcase_21 | AC | 34 ms
14,308 KB |
testcase_22 | AC | 21 ms
9,288 KB |
testcase_23 | AC | 47 ms
18,584 KB |
testcase_24 | AC | 47 ms
18,712 KB |
ソースコード
import algorithm, macros, math, sequtils, strutils, tables # import bitops, lenientops, deques, # heapqueue, sets, sugar let read* = iterator: string = while true: (for s in stdin.readLine.split: yield s) template input*(T: static[typedesc]): untyped = when T is int: read().parseInt elif T is float: read().parseFloat elif T is string: read() elif T is char: read()[0] macro dump*(args: varargs[typed]): untyped = result = newNimNode(nnkStmtList) for x in args: let s = toStrLit(x) result.add quote do: stderr.write `s`, " = ", `x`, " " result.add quote do: stderr.write "\n" 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))) proc newSeq4*[T](n1, n2, n3, n4: Natural): seq[seq[seq[seq[T]]]] = newSeqWith(n1, newSeqWith(n2, newSeqWith(n3, newSeq[T](n4)))) # -------------------------------------------------- # 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.} = toModInt(int(n) + m) proc `+`*(n: int, m: ModInt): ModInt {.inline.} = toModInt(n + int(m)) 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.} = toModInt(int(n) - m) proc `-`*(n: int, m: ModInt): ModInt {.inline.} = toModInt(- + int(m)) 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 # -------------------------------------------------- # useModInt(10 ^ 9 + 7) let p, K = input(int) let P = ModInt(p) var dp: array[0 .. 10 ^ 6, array[0 .. 1, ModInt]] dp[0][0] = ModInt(1) #dump(0) #dump(dp[0]) for i in 1 .. K: #dump(i) # + dp[i][0] += dp[i - 1][0] + dp[i - 1][1] dp[i][1] += (P - 1) * (dp[i - 1][0] + dp[i - 1][1]) #dump(dp[i]) # * dp[i][0] += P * dp[i - 1][0] + dp[i - 1][1] dp[i][1] += (P - 1) * dp[i - 1][1] #dump(dp[i]) echo dp[K][0]