結果
| 問題 |
No.2277 Honest or Dishonest ?
|
| コンテスト | |
| ユーザー |
 Daylight
|
| 提出日時 | 2023-04-21 21:55:05 |
| 言語 | Nim (2.2.0) |
| 結果 |
AC
|
| 実行時間 | 96 ms / 2,000 ms |
| コード長 | 17,179 bytes |
| コンパイル時間 | 6,629 ms |
| コンパイル使用メモリ | 78,208 KB |
| 実行使用メモリ | 9,984 KB |
| 最終ジャッジ日時 | 2024-11-08 06:30:48 |
| 合計ジャッジ時間 | 10,827 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 50 |
コンパイルメッセージ
/home/judge/data/code/Main.nim(25, 12) Warning: imported and not used: 'sugar' [UnusedImport]
ソースコード
import macros
macro Please(x): untyped = nnkStmtList.newTree()
Please use Nim-ACL
Please use Nim-ACL
Please use Nim-ACL
#[ include daylight/base ]#
when not declared DAYLIGHT_BASE_HPP:
const DAYLIGHT_BASE_HPP* = 1
import system
import macros
import algorithm
import tables
import sets
import lists
import intsets
import critbits
import sequtils
import strutils
import std/math
import strformat
import sugar
let readToken* = iterator(oneChar: bool = false): string {.closure.}=
while true:
var line = stdin.readLine.split
for s in line:
if oneChar:
for i in 0..<s.len():
yield s[i..i]
else:
yield s
proc read*(t: typedesc[string]): string =
result = readToken()
while result == "":
result = readToken()
proc read*(t: typedesc[int]): int = read(string).parseInt
proc read*(t: typedesc[float]): float = read(string).parseFloat
proc read*(t: typedesc[char]): char = readToken(true)[0]
macro readSeq*(t: typedesc, n: varargs[int]): untyped =
var repStr = ""
for arg in n:
repStr &= &"({arg.repr}).newSeqWith "
parseExpr(&"{repStr}read({t})")
macro read*(ts: varargs[auto]): untyped=
var tupStr = ""
for t in ts:
tupStr &= &"read({t.repr}),"
parseExpr(&"({tupStr})")
macro readTupleSeq*(n: int, ts:varargs[auto]): untyped=
for typ in ts:
if typ.typeKind != ntyAnything:
error("Expected typedesc, got " & typ.repr, typ)
parseExpr(&"({n.repr}).newSeqWith read({ts.repr})")
macro initSeq*(t: typedesc, n: varargs[int]): untyped =
var repStr = ""
for i, arg in n:
if i == n.len - 1:
repStr &= &"newSeq[{t}]({arg.repr}) "
else:
repStr &= &"({arg.repr}).newSeqWith "
parseExpr(repStr)
proc `-`*(a,b: char): int = ord(a) - ord(b)
proc `+`*(a: char,b: int): char = char(ord(a) + b)
proc `-`*(a: char,b: int): char = char(ord(a) - b)
proc `++`*(a: var int) = a += 1
proc `--`*(a: var int) = a += 1
proc chmin*[T](a: var T, b: T): bool {.discardable.} =
if a > b:
a = b
return true
return false
proc chmax*[T](a: var T, b: T): bool {.discardable.} =
if a < b:
a = b
return true
return false
const INF* = (1e9+100).int
const LINF* = (4e18 + 100).int
discard
#[ import atcoder/dsu ]#
when not declared ATCODER_DSU_HPP:
const ATCODER_DSU_HPP* = 1
import std/sequtils
type
DSU* = ref object
n: int
par_or_siz: seq[int]
proc initDSU*(n: int): DSU {.inline.} =
return DSU(n: n, par_or_siz: newSeqWith(n, -1))
proc leader*(self: DSU; a: int): int {.inline.} =
if self.par_or_siz[a] < 0: return a
self.par_or_siz[a] = self.leader(self.par_or_siz[a])
return self.par_or_siz[a]
proc same*(self: DSU; a, b: int): bool {.inline.} =
self.leader(a) == self.leader(b)
proc size*(self: DSU; a: int): int {.inline.} =
- self.par_or_siz[self.leader(a)]
proc merge*(self: DSU; a, b: int): int {.inline, discardable.} =
var
x = self.leader(a)
y = self.leader(b)
if x == y: return x
if self.par_or_siz[x] > self.par_or_siz[y]: swap(x, y)
self.par_or_siz[x] += self.par_or_siz[y]
self.par_or_siz[y] = x
return x
proc groups*(self: DSU): seq[seq[int]] {.inline.} =
var
leaderBuf = newSeq[int](self.n)
groupsize = newSeq[int](self.n)
for i in 0 ..< self.n:
leaderBuf[i] = self.leader(i)
groupsize[leaderBuf[i]].inc
result = (0 ..< self.n).mapIt(newSeqOfCap[int](groupsize[it]))
for i, ldr in leaderBuf:
result[ldr].add i
result.keepItIf(it.len > 0)
discard
#[ import atcoder/modint ]#
when not declared ATCODER_MODINT_HPP:
const ATCODER_MODINT_HPP* = 1
import std/macros
#[ import atcoder/generate_definitions ]#
when not declared ATCODER_GENERATE_DEFINITIONS_NIM:
const ATCODER_GENERATE_DEFINITIONS_NIM* = 1
import std/macros
type hasInv* = concept x
x.inv()
template generateDefinitions*(name, l, r, typeObj, typeBase, body: untyped): untyped {.dirty.} =
proc name*(l, r: typeObj): auto {.inline.} =
type T = l.type
body
proc name*(l: typeBase; r: typeObj): auto {.inline.} =
type T = r.type
body
proc name*(l: typeObj; r: typeBase): auto {.inline.} =
type T = l.type
body
template generatePow*(name) {.dirty.} =
proc pow*(m: name; p: SomeInteger): name {.inline.} =
when name is hasInv:
if p < 0: return pow(m.inv(), -p)
else:
doAssert p >= 0
if (p.type)(0) <= p:
var
p = p.uint
m = m
result = m.unit()
while p > 0'u:
if (p and 1'u) != 0'u: result *= m
m *= m
p = p shr 1'u
proc `^`*[T:name](m: T; p: SomeInteger): T {.inline.} = m.pow(p)
macro generateConverter*(name, from_type, to_type) =
let fname = ident("to" & $`name` & "OfGenerateConverter")
quote do:
type `name`* = `to_type`
converter `fname`*(a:`from_type`):`name` {.used.} =
`name`.init(a)
discard
type
StaticModInt*[M: static[int]] = object
a:uint32
DynamicModInt*[T: static[int]] = object
a:uint32
type ModInt* = StaticModInt or DynamicModInt
proc isStaticModInt*(T:typedesc[ModInt]):bool = T is StaticModInt
proc isDynamicModInt*(T:typedesc[ModInt]):bool = T is DynamicModInt
proc isStatic*(T:typedesc[ModInt]):bool = T is StaticModInt
#[ import atcoder/internal_math ]#
when not declared ATCODER_INTERNAL_MATH_HPP:
const ATCODER_INTERNAL_MATH_HPP* = 1
import std/math
type Barrett* = object
m*, im*:uint
proc initBarrett*(m:uint):auto = Barrett(m:m, im:cast[uint](-1) div m + 1)
proc umod*(self: Barrett):uint =
self.m
{.emit: """
inline unsigned long long calc_mul(const unsigned long long &a, const unsigned long long &b){
return (unsigned long long)(((unsigned __int128)(a)*b) >> 64);
}
""".}
proc calc_mul*(a,b:culonglong):culonglong {.importcpp: "calc_mul(#,#)", nodecl, inline.}
proc quo*(self: Barrett, n:int | uint):int =
let n = n.uint
let x = calc_mul(n.culonglong, self.im.culonglong).uint
let r = n - x * self.m
return int(if self.m <= r: x - 1 else: x)
proc rem*(self: Barrett, n:int | uint):int =
let n = n.uint
let x = calc_mul(n.culonglong, self.im.culonglong).uint
let r = n - x * self.m
return int(if self.m <= r: r + self.m else: r)
proc quorem*(self: Barrett, n:int | uint):(int, int) =
let n = n.uint
let x = calc_mul(n.culonglong, self.im.culonglong).uint
let r = n - x * self.m
return if self.m <= r: (int(x - 1), int(r + self.m)) else: (int(x), int(r))
proc pow*(self: Barrett, n:uint | int, p:int):int =
var
a = self.rem(n)
r:uint = if self.m == 1: 0 else: 1
p = p
while p > 0:
if (p and 1) != 0: r = self.mul(r, a.uint)
a = self.mul(a.uint, a.uint).int
p = p shr 1
return int(r)
proc mul*(self: Barrett, a:uint, b:uint):uint {.inline.} =
let z = a * b
return self.rem(z).uint
proc pow_mod_constexpr*(x, n, m:int):int =
if m == 1: return 0
var
r = 1
y = floorMod(x, m)
n = n
while n != 0:
if (n and 1) != 0: r = (r * y) mod m
y = (y * y) mod m
n = n shr 1
return r.int
proc is_prime_constexpr*(n:int):bool =
if n <= 1: return false
if n == 2 or n == 7 or n == 61: return true
if n mod 2 == 0: return false
var d = n - 1
while d mod 2 == 0: d = d div 2
for a in [2, 7, 61]:
var
t = d
y = pow_mod_constexpr(a, t, n)
while t != n - 1 and y != 1 and y != n - 1:
y = y * y mod n
t = t shl 1
if y != n - 1 and t mod 2 == 0:
return false
return true
proc is_prime*[n:static[int]]():bool = is_prime_constexpr(n)
proc inv_gcd*(a, b:int):(int,int) =
var a = floorMod(a, b)
if a == 0: return (b, 0)
var
s = b
t = a
m0 = 0
m1 = 1
while t != 0:
var u = s div t
s -= t * u;
m0 -= m1 * u; # |m1 * u| <= |m1| * s <= b
var tmp = s
s = t;t = tmp;
tmp = m0;m0 = m1;m1 = tmp;
if m0 < 0: m0 += b div s
return (s, m0)
proc primitive_root_constexpr*(m:int):int =
if m == 2: return 1
if m == 167772161: return 3
if m == 469762049: return 3
if m == 754974721: return 11
if m == 998244353: return 3
var divs:array[20, int]
divs[0] = 2
var cnt = 1
var x = (m - 1) div 2
while x mod 2 == 0: x = x div 2
var i = 3
while i * i <= x:
if x mod i == 0:
divs[cnt] = i
cnt.inc
while x mod i == 0:
x = x div i
i += 2
if x > 1:
divs[cnt] = x
cnt.inc
var g = 2
while true:
var ok = true
for i in 0..<cnt:
if pow_mod_constexpr(g, (m - 1) div divs[i], m) == 1:
ok = false
break
if ok: return g
g.inc
proc primitive_root*[m:static[int]]():auto =
primitive_root_constexpr(m)
proc floor_sum_unsigned*(n, m, a, b:uint):uint =
result = 0
var (n, m, a, b) = (n, m, a, b)
while true:
if a >= m:
result += n * (n - 1) div 2 * (a div m)
a = a mod m
if b >= m:
result += n * (b div m)
b = b mod m
let y_max = a * n + b
if y_max < m: break
n = y_max div m
b = y_max mod m
swap(m, a)
discard
proc getBarrett*[T:static[int]](t:typedesc[DynamicModInt[T]]):ptr Barrett =
var Barrett_of_DynamicModInt {.global.} = initBarrett(998244353.uint)
return Barrett_of_DynamicModInt.addr
proc getMod*[T:static[int]](t:typedesc[DynamicModInt[T]]):uint32 {.inline.} =
(t.getBarrett)[].m.uint32
proc setMod*[T:static[int]](t:typedesc[DynamicModInt[T]], M:SomeInteger){.inline.} =
(t.getBarrett)[] = initBarrett(M.uint)
proc val*(m: ModInt): int {.inline.} = int(m.a)
proc `$`*(m: StaticModInt or DynamicModInt): string {.inline.} = $(m.val())
template umod*[T:ModInt](self: typedesc[T] or T):uint32 =
when T is typedesc:
when T is StaticModInt:
T.M.uint32
elif T is DynamicModInt:
T.getMod()
else:
static: assert false
else: T.umod
template `mod`*[T:ModInt](self:typedesc[T] or T):int = T.umod.int
proc init*[T:ModInt](t:typedesc[T], v: SomeInteger or T): auto {.inline.} =
when v is T: return v
else:
when v is SomeUnsignedInt:
if v.uint < T.umod:
return T(a:v.uint32)
else:
return T(a:(v.uint mod T.umod.uint).uint32)
else:
var v = v.int
if 0 <= v:
if v < T.mod: return T(a:v.uint32)
else: return T(a:(v mod T.mod).uint32)
else:
v = v mod T.mod
if v < 0: v += T.mod
return T(a:v.uint32)
proc unit*[T:ModInt](t:typedesc[T] or T):T = T.init(1)
template initModInt*(v: SomeInteger or ModInt; M: static[int] = 1_000_000_007): auto =
StaticModInt[M].init(v)
proc raw*[T:ModInt](t:typedesc[T], v:SomeInteger):auto = T(a:v)
proc inv*[T:ModInt](v:T):T {.inline.} =
var
a = v.a.int
b = T.mod
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 T.init(u)
proc `-`*[T:ModInt](m: T): T {.inline.} =
if int(m.a) == 0: return m
else: return T(a:m.umod() - m.a)
proc `+=`*[T:ModInt](m: var T; n: SomeInteger | T):T {.inline discardable.} =
m.a += T.init(n).a
if m.a >= T.umod: m.a -= T.umod
return m
proc `-=`*[T:ModInt](m: var T; n: SomeInteger | T):T {.inline discardable.} =
m.a -= T.init(n).a
if m.a >= T.umod: m.a += T.umod
return m
proc `*=`*[T:ModInt](m: var T; n: SomeInteger | T):T {.inline discardable.} =
when T is StaticModInt:
m.a = (m.a.uint * T.init(n).a.uint mod T.umod).uint32
elif T is DynamicModInt:
m.a = T.getBarrett[].mul(m.a.uint, T.init(n).a.uint).uint32
else:
static: assert false
return m
proc `/=`*[T:ModInt](m: var T; n: SomeInteger | T):T {.inline discardable.} =
m.a = (m.a.uint * T.init(n).inv().a.uint mod T.umod).uint32
return m
generateDefinitions(`+`, m, n, ModInt, SomeInteger):
result = T.init(m)
result += n
generateDefinitions(`-`, m, n, ModInt, SomeInteger):
result = T.init(m)
result -= n
generateDefinitions(`*`, m, n, ModInt, SomeInteger):
result = T.init(m)
result *= n
generateDefinitions(`/`, m, n, ModInt, SomeInteger):
result = T.init(m)
result /= n
generateDefinitions(`==`, m, n, ModInt, SomeInteger):
result = (T.init(m).val() == T.init(n).val())
proc inc*(m: var ModInt):ModInt {.inline discardable.} =
m.a.inc
if m.a == m.umod.uint32:
m.a = 0
return m
proc `++`*(m: var ModInt):ModInt {.inline discardable.} = m.inc
proc dec*(m: var ModInt):ModInt {.inline discardable.} =
if m.a == 0.uint32:
m.a = m.umod - 1
else:
m.a.dec
return m
proc `--`*(m: var ModInt):ModInt {.inline discardable.} = m.dec
generatePow(ModInt)
template useStaticModint*(name, M) =
generateConverter(name, int, StaticModInt[M])
template useDynamicModInt*(name, M) =
generateConverter(name, int, DynamicModInt[M])
useStaticModInt(modint998244353, 998244353)
useStaticModInt(modint1000000007, 1000000007)
useDynamicModInt(modint, -1)
import std/math as math_lib_modint
proc estimateRational*(a:ModInt, ub:int = int(sqrt(float(ModInt.mod))), output_stderr:static[bool] = false):string =
var v:seq[tuple[s, n, d: int]]
for d in 1 .. ub:
var n = (a * d).val
if n * 2 > a.mod:
n = - (a.mod - n)
if gcd(n, d) > 1: continue
v.add((n.abs + d, n, d))
v.sort
when output_stderr:
stderr.write "estimation result: ", v
return $v[0].n & "/" & $v[0].d
discard
type mint = modint998244353
proc solve() =
var
N = read(int)
Q = read(int)
dsu = initDSU(2 * N)
dsu2 = initDSU(N)
for i in 0..<Q:
var
(A, B, C) = read(int,int,int)
A -= 1
B -= 1
if C == 0:
dsu.merge(A, B)
dsu.merge(A+N, B+N)
else:
dsu.merge(A, B+N)
dsu.merge(A+N,B)
dsu2.merge(A, B)
for i in 0..<N:
if dsu.same(i,i+N):
echo 0
return
echo mint(2)^(dsu2.groups().len())
solve()