結果
| 問題 | No.3394 Big Binom |
| コンテスト | |
| ユーザー |
 kemuniku
|
| 提出日時 | 2025-12-01 00:43:28 |
| 言語 | Nim (2.2.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 18,130 bytes |
| 記録 | |
| コンパイル時間 | 3,889 ms |
| コンパイル使用メモリ | 77,124 KB |
| 実行使用メモリ | 11,176 KB |
| 最終ジャッジ日時 | 2025-12-01 00:43:37 |
| 合計ジャッジ時間 | 8,761 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 16 TLE * 1 -- * 4 |
ソースコード
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
ImportExpand "cplib/tmpl/sheep.nim" <=== "when not declared CPLIB_TMPL_SHEEP:\n const CPLIB_TMPL_SHEEP* = 1\n {.warning[UnusedImport]: off.}\n {.hint[XDeclaredButNotUsed]: off.}\n import algorithm\n import sequtils\n import tables\n import macros\n import math\n import sets\n import strutils\n import strformat\n import sugar\n import heapqueue\n import streams\n import deques\n import bitops\n import std/lenientops\n import options\n #入力系\n proc scanf(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n proc getchar(): char {.importc: \"getchar_unlocked\", header: \"<stdio.h>\", discardable.}\n proc ii(): int {.inline.} = scanf(\"%lld\\n\", addr result)\n proc lii(N: int): seq[int] {.inline.} = newSeqWith(N, ii())\n proc si(): string {.inline.} =\n result = \"\"\n var c: char\n while true:\n c = getchar()\n if c == ' ' or c == '\\n' or c == '\\255':\n break\n result &= c\n #chmin,chmax\n template `max=`(x, y) = x = max(x, y)\n template `min=`(x, y) = x = min(x, y)\n proc chmin[T](x: var T, y: T):bool=\n if x > y:\n x = y\n return true\n return false\n proc chmax[T](x: var T, y: T):bool=\n if x < y:\n x = y\n return true\n return false\n #bit演算\n proc `%`*(x: int, y: int): int =\n result = x mod y\n if y > 0 and result < 0: result += y\n if y < 0 and result > 0: result += y\n proc `//`*(x: int, y: int): int{.inline.} =\n result = x div y\n if y > 0 and result * y > x: result -= 1\n if y < 0 and result * y < x: result -= 1\n proc `%=`(x: var int, y: int): void = x = x%y\n proc `//=`(x: var int, y: int): void = x = x//y\n proc `**`(x: int, y: int): int = x^y\n proc `**=`(x: var int, y: int): void = x = x^y\n proc `^`(x: int, y: int): int = x xor y\n proc `|`(x: int, y: int): int = x or y\n proc `&`(x: int, y: int): int = x and y\n proc `>>`(x: int, y: int): int = x shr y\n proc `<<`(x: int, y: int): int = x shl y\n proc `~`(x: int): int = not x\n proc `^=`(x: var int, y: int): void = x = x ^ y\n proc `&=`(x: var int, y: int): void = x = x & y\n proc `|=`(x: var int, y: int): void = x = x | y\n proc `>>=`(x: var int, y: int): void = x = x >> y\n proc `<<=`(x: var int, y: int): void = x = x << y\n proc `[]`(x: int, n: int): bool = (x and (1 shl n)) != 0\n #便利な変換\n proc `!`(x: char, a = '0'): int = int(x)-int(a)\n #定数\n #[ include cplib/utils/constants ]#\n when not declared CPLIB_UTILS_CONSTANTS:\n const CPLIB_UTILS_CONSTANTS* = 1\n const INF32*: int32 = 1001000027.int32\n const INF64*: int = int(3300300300300300491)\n const INF = INF64\n #converter\n\n #range\n iterator range(start: int, ends: int, step: int): int =\n var i = start\n if step < 0:\n while i > ends:\n yield i\n i += step\n elif step > 0:\n while i < ends:\n yield i\n i += step\n iterator range(ends: int): int = (for i in 0..<ends: yield i)\n iterator range(start: int, ends: int): int = (for i in\n start..<ends: yield i)\n\n #joinが非stringでめちゃくちゃ遅いやつのパッチ\n proc join*[T: not string](a: openArray[T], sep: string = \"\"): string = a.mapit($it).join(sep)\n\n proc dump[T](arr:seq[seq[T]])=\n for i in 0..<len(arr):\n echo arr[i]\n\n proc sum(slice:HSlice[int,int]):int=\n return (slice.a+slice.b)*len(slice)//2\n \n proc `<`[T](l,r:seq[T]):bool=\n for i in 0..<min(len(l),len(r)):\n if l[i] > r[i]:\n return false\n elif l[i] < r[i]:\n return true\n return len(l) < len(r)\n"
ImportExpand "cplib/modint/modint.nim" <=== "when not declared CPLIB_MODINT_MODINT:\n const CPLIB_MODINT_MODINT* = 1\n #[ include cplib/modint/barrett_impl ]#\n when not declared CPLIB_MODINT_MODINT_BARRETT:\n const CPLIB_MODINT_MODINT_BARRETT* = 1\n import std/macros\n type StaticBarrettModint*[M: static[uint32]] = object\n a: uint32\n type DynamicBarrettModint*[M: static[uint32]] = object\n a: uint32\n type BarrettModint* = StaticBarrettModint or DynamicBarrettModint\n \n proc get_im*(M: uint32): uint = cast[uint](-1) div M + 1\n func get_param*[M: static[uint32]](self: typedesc[DynamicBarrettModint[M]]): ptr[tuple[M, im: uint]] =\n {.cast(noSideEffect).}:\n #FIXME: nim 2.0 で global の動作が怪しいので、変更したい\n var p {.global.}: tuple[M, im: uint] = (998244353u, get_im(998244353u32))\n return p.addr\n template get_M*(T: typedesc[BarrettModint]): uint =\n when T is StaticBarrettModint: T.M.uint\n else: (get_param(T))[].M.uint\n proc setMod*[T: static[uint32]](self: typedesc[DynamicBarrettModint[T]], M: SomeInteger or SomeUnsignedInt) =\n (get_param(self))[] = (M: M.uint, im: get_im(M.uint32))\n \n template umod*[T: BarrettModint](self: typedesc[T] or T): uint32 =\n when self is typedesc:\n when self is StaticBarrettModint: self.M\n else: cast[uint32](((get_param(self))[]).M)\n else: T.umod\n template `mod`*[T: BarrettModint](self: typedesc[T] or T): int32 = (T.umod).int32\n {.emit: \"\"\"\n #include <cstdio>\n inline unsigned long long calc_mul(const unsigned long long &a, const unsigned long long &b) {\n return (unsigned long long)(((__uint128_t)(a) * b) >> 64);\n }\n \"\"\".}\n proc calc_mul*(a, b: culonglong): culonglong {.importcpp: \"calc_mul(#, #)\", nodecl, inline.}\n proc rem*(T: typedesc[BarrettModint], a: uint): uint32 =\n when T is StaticBarrettModint:\n const im = get_im(T.M)\n const M = get_M(T)\n var x = (calc_mul(cast[culonglong](a), cast[culonglong](im))).uint\n var r = a - x * M\n if M <= r: r += M\n return cast[uint32](r)\n else:\n var p = get_param(T)[]\n var x = (calc_mul(cast[culonglong](a), cast[culonglong](p.im))).uint\n var r = a - x * p.M\n if p.M <= r: r += p.M\n return cast[uint32](r)\n proc init*(T: typedesc[BarrettModint], a: T or SomeInteger): auto =\n when a is T: return a\n else:\n if a in 0..<T.mod.int: return T(a: a.uint32)\n var a = a mod T.mod.int\n if a < 0: a += T.mod.int\n return T(a: a.uint32)\n \n proc `-`*[T: BarrettModint](a: T): T = T(a: T.umod - a.a)\n proc `+=`*[T: BarrettModint](a: var T, b: T or SomeInteger) =\n a.a += init(T, b).a\n if a.a >= T.umod: a.a -= T.umod\n proc `-=`*[T: BarrettModint](a: var T, b: T or SomeInteger) =\n a.a -= init(T, b).a\n if a.a >= T.umod: a.a += T.umod\n proc `*=`*[T: BarrettModint] (a: var T, b: T or SomeInteger) =\n a.a = rem(T, (a.a).uint * (init(T, b).a).uint)\n proc inv*[T: BarrettModint](x: T): T =\n assert x.val != 0\n var x: int32 = int32(x.val)\n var y: int32 = T.mod\n var u = 1i32\n var v, t = 0i32\n while y > 0:\n t = x div y\n x -= t * y\n u -= t * v\n swap(x, y)\n swap(u, v)\n return init(T, u)\n proc `/=`*[T: BarrettModint](a: var T, b: T or SomeInteger) = a *= init(T, b).inv\n proc val*(a: BarrettModint): int = a.a.int\n macro declarStaticBarrettModint*(name, M) =\n let converter_name = ident(\"to\" & $`name`)\n quote do:\n type `name`* = StaticBarrettModint[`M`]\n converter `converter_name`*(a: int): StaticBarrettModint[`M`] = init(StaticBarrettModint[`M`], a)\n macro declarDynamicBarrettModint*(name, id) =\n let converter_name = ident(\"to\" & $`name`)\n quote do:\n type `name`* = DynamicBarrettModint[`id`]\n converter `converter_name`*(a: int): DynamicBarrettModint[`id`] = init(DynamicBarrettModint[`id`], a)\n #[ include cplib/modint/montgomery_impl ]#\n when not declared CPLIB_MODINT_MODINT_MONTGOMERY:\n const CPLIB_MODINT_MODINT_MONTGOMERY* = 1\n import std/macros\n type StaticMontgomeryModint*[M: static[uint32]] = object\n a: uint32\n type DynamicMontgomeryModint*[M: static[uint32]] = object\n a: uint32\n type MontgomeryModint* = StaticMontgomeryModint or DynamicMontgomeryModint\n \n proc get_r*(M: uint32): uint32 =\n result = M\n for _ in 0..<4: result *= 2u32 - M * result\n proc get_n2*(M: uint32): uint32 = uint32((not uint(M - 1u32)) mod uint(M))\n proc check_params(M, r: uint32) =\n assert M < (1u32 shl 30), \"invalid mod >= 2^30\"\n assert (M and 1u32) == 1u32, \"invalid mod % 2 == 0\"\n assert r * M == 1, \"r * mod != 1\"\n func get_param*[M: static[uint32]](self: typedesc[DynamicMontgomeryModint[M]]): ptr[tuple[M, r, n2: uint32]] =\n {.cast(noSideEffect).}:\n #FIXME: nim 2.0 で global の動作が怪しいので、変更したい\n var p {.global.}: tuple[M, r, n2: uint32] = (998244353u32, get_r(998244353u32), get_n2(998244353u32))\n return p.addr\n template get_M*(T: typedesc[MontgomeryModint]): uint32 =\n when T is StaticMontgomeryModint: T.M\n else: (get_param(T))[].M\n proc setMod*[T: static[uint32]](self: typedesc[DynamicMontgomeryModint[T]], M: SomeInteger or SomeUnsignedInt) =\n var r = get_r(M.uint32)\n var n2 = get_n2(M.uint32)\n var p = (M.uint32, r, n2)\n (get_param(self))[] = p\n check_params(M.uint32, r)\n \n template umod*[T: MontgomeryModint](self: typedesc[T] or T): uint32 =\n when self is typedesc:\n when self is StaticMontgomeryModint: self.M\n else: ((get_param(self))[]).M\n else: T.umod\n template `mod`*[T: MontgomeryModint](self: typedesc[T] or T): int32 = (T.umod).int32\n \n func reduce(T: typedesc[MontgomeryModint], b: uint): uint32 =\n when T is StaticMontgomeryModint:\n const r = get_r(T.M)\n return cast[uint32]((b + uint(cast[uint32](b) * (not (r - 1u32))) * T.M) shr 32)\n else:\n var p = (get_param(T))[]\n return cast[uint32]((b + uint(cast[uint32](b) * (not (p.r - 1u32))) * p.M) shr 32)\n proc init*(T: typedesc[MontgomeryModint], a: T or SomeInteger): auto =\n when a is T: return a\n elif T is StaticMontgomeryModint:\n const r = get_r(T.M)\n const n2 = get_n2(T.M)\n check_params(T.M, r)\n var ai = reduce(T, uint(a.int32 mod T.M.int32 + T.M.int32) * n2)\n result = StaticMontgomeryModint[T.M](a: ai)\n elif T is DynamicMontgomeryModint:\n var p = (get_param(T))[]\n var ai = reduce(T, uint(a.int32 mod p.M.int32 + p.M.int32) * p.n2)\n result = DynamicMontgomeryModint[T.M](a: ai)\n \n proc `+=`*[T: MontgomeryModint](a: var T, b: T or SomeInteger) =\n a.a += init(T, b).a - T.get_M * 2u32\n if cast[int32](a.a) < 0i32: a.a += T.get_M * 2u32\n proc `-=`*[T: MontgomeryModint](a: var T, b: T or SomeInteger) =\n a.a -= init(T, b).a\n if cast[int32](a.a) < 0i32: a.a += T.get_M * 2u32\n proc val*[T: MontgomeryModint](a: T): int =\n result = reduce(T, a.a).int\n if result.uint32 >= T.get_M: result -= T.get_M.int\n \n proc `-`*[T: MontgomeryModint](a: T): T = init(T, 0) - a\n proc `*=`*[T: MontgomeryModint] (a: var T, b: T or SomeInteger) = a.a = reduce(T, uint(a.a) * init(T, b).a)\n proc inv*[T: MontgomeryModint](x: T): T =\n assert x.val != 0\n var x: int32 = int32(x.val)\n var y: int32 = T.mod\n var u = 1i32\n var v, t = 0i32\n while y > 0:\n t = x div y\n x -= t * y\n u -= t * v\n swap(x, y)\n swap(u, v)\n return init(T, u)\n proc `/=`*[T: MontgomeryModint](a: var T, b: T or SomeInteger) = a *= init(T, b).inv\n \n macro declarStaticMontgomeryModint*(name, M) =\n let converter_name = ident(\"to\" & $`name`)\n quote do:\n type `name`* = StaticMontgomeryModint[`M`]\n converter `converter_name`*(a: int): StaticMontgomeryModint[`M`] = init(StaticMontgomeryModint[`M`], a)\n macro declarDynamicMontgomeryModint*(name, id) =\n let converter_name = ident(\"to\" & $`name`)\n quote do:\n type `name`* = DynamicMontgomeryModint[`id`]\n converter `converter_name`*(a: int): DynamicMontgomeryModint[`id`] = init(DynamicMontgomeryModint[`id`], a)\n import std/math\n import std/algorithm\n #[ import cplib/math/isqrt ]#\n when not declared CPLIB_MATH_ISQRT:\n const CPLIB_MATH_ISQRT* = 1\n proc isqrt*(n: int): int =\n var x = n\n var y = (x + 1) shr 1\n while y < x:\n x = y\n y = (x + n div x) shr 1\n return x\n declarStaticMontgomeryModint(modint998244353_montgomery, 998244353u32)\n declarStaticMontgomeryModint(modint1000000007_montgomery, 1000000007u32)\n declarDynamicMontgomeryModint(modint_montgomery, 1u32)\n declarStaticBarrettModint(modint998244353_barrett, 998244353u32)\n declarStaticBarrettModint(modint1000000007_barrett, 1000000007u32)\n declarDynamicBarrettModint(modint_barrett, 1u32)\n func `+`*(a, b: MontgomeryModint or BarrettModint): auto = (result = a; result += b)\n func `-`*(a, b: MontgomeryModint or BarrettModint): auto = (result = a; result -= b)\n func `*`*(a, b: MontgomeryModint or BarrettModint): auto = (result = a; result *= b)\n func `/`*(a, b: MontgomeryModint or BarrettModint): auto = (result = a; result /= b)\n func `+`*(a: MontgomeryModint or BarrettModint, b: SomeInteger): auto = (result = a; result += b)\n func `-`*(a: MontgomeryModint or BarrettModint, b: SomeInteger): auto = (result = a; result -= b)\n func `*`*(a: MontgomeryModint or BarrettModint, b: SomeInteger): auto = (result = a; result *= b)\n func `/`*(a: MontgomeryModint or BarrettModint, b: SomeInteger): auto = (result = a; result /= b)\n func `+`*[ModInt: MontgomeryModint or BarrettModint](a: SomeInteger, b: Modint): auto = init(Modint, a) + b\n func `-`*[ModInt: MontgomeryModint or BarrettModint](a: SomeInteger, b: Modint): auto = init(Modint, a) - b\n func `*`*[ModInt: MontgomeryModint or BarrettModint](a: SomeInteger, b: Modint): auto = init(Modint, a) * b\n func `/`*[ModInt: MontgomeryModint or BarrettModint](a: SomeInteger, b: Modint): auto = init(Modint, a) / b\n proc `/`*[ModInt: MontgomeryModint or BarrettModint](a: ModInt, b: static int): auto =\n const tmp = init(Modint, b).inv\n return a * tmp\n func pow*(a: MontgomeryModint or BarrettModint, n: int): auto =\n result = init(typeof(a), 1)\n var a = a\n var n = n\n while n > 0:\n if (n and 1) == 1: result *= a\n a *= a\n n = (n shr 1)\n func `$`*(a: MontgomeryModint or BarrettModint): string = $(a.val)\n proc estimate_rational*(a: MontgomeryModint or BarrettModint, ub: int = isqrt(typeof(a).mod)): string =\n var v: seq[tuple[s, n, d: int]]\n for d in 1..ub:\n var n = (a * d).val\n if n * 2 > a.mod:\n n = - (a.mod - n)\n if gcd(n, d) > 1: continue\n v.add((n.abs + d, n, d))\n v.sort\n return $v[0].n & \"/\" & $v[0].d\n"
type mint = modint998244353_montgomery
var fact = @[1,295201906,160030060,957629942,545208507,213689172,760025067,939830261,506268060,39806322,808258749,440133909,686156489,741797144,390377694,12629586,544711799,104121967,495867250,421290700,117153405,57084755,202713771,675932866,79781699,956276337,652678397,35212756,655645460,468129309,761699708,533047427,287671032,206068022,50865043,144980423,111276893,259415897,444094191,593907889,573994984,892454686,566073550,128761001,888483202,251718753,548033568,428105027,742756734,546182474,62402409,102052166,826426395,159186619,926316039,176055335,51568171,414163604,604947226,681666415,511621808,924112080,265769800,955559118,763148293,472709375,19536133,860830935,290471030,851685235,242726978,169855231,612759169,599797734,961628039,953297493,62806842,37844313,909741023,689361523,887890124,380694152,669317759,367270918,806951470,843736533,377403437,945260111,786127243,80918046,875880304,364983542,623250998,598764068,804930040,24257676,214821357,791011898,954947696,183092975,0]
proc get_fact(x:int):mint=
var f = mint(fact[x//(10**7)])
for k in (x//(10**7)*(10**7)+1)..x:
f *= k
return f
proc ncr*(n, r: int):mint=
if n < 0 or r < 0 or n < r:
return 0
return get_fact(n)/get_fact(n-r)/get_fact(r)
var N,K = ii()
if N >= 998244353:
if K >= 998244353:
K = N-K
var ans = mint(1)
var tmp = mint(1)
for x in range(K):
ans *= N-x
tmp *= x+1
echo ans/tmp
else:
echo ncr(N,K)