#961071 (Nim) No.2672 Subset Xor Sum

• 問題: No.2672 Subset Xor Sum
• ユーザー: 寝癖
• 提出日時: 2024-03-15 23:46:46
• 言語: Nim (2.2.0)
• 結果: AC
• 実行時間: 66 ms / 2,000 ms
• コード長: 6,929 bytes
• コンパイル時間: 4,474 ms
• コンパイル使用メモリ: 76,800 KB
• 実行使用メモリ: 7,168 KB
• 最終ジャッジ日時: 2024-09-30 04:25:34
• 合計ジャッジ時間: 6,931 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 66

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
ImportExpand "neguse/tmpl.nim" <=== "when not declared NEGUSE_TMPL:\n  const NEGUSE_TMPL* = 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  # ACL\n  #[ import atcoder/header ]#\n  when not declared ATCODER_HEADER_HPP:\n    const ATCODER_HEADER_HPP* = 1\n    {.hints
    :off checks:off assertions:on optimization:speed.}\n    {. warning[UnusedImport]:off .}\n    import std/algorithm as algorithm_lib\n    import std
    /sequtils as sequils_lib\n    import std/tables as tables_lib\n    import std/macros as macros_lib\n    import std/math as math_lib\n    import 
    std/sets as sets_lib\n    import std/strutils as strutils_lib\n    import std/streams as streams_lib\n    import std/strformat as strformat_lib\n 
     \n    proc scanf*(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n    proc getchar*(): char {.header: \"<stdio.h>\", varargs.}\n    proc 
    nextInt*(base:int = 0): int =\n      scanf(\"%lld\",addr result)\n      result -= base\n    proc nextFloat*(): float = scanf(\"%lf\",addr result
    )\n    proc nextString*(): string =\n      var get = false;result = \"\"\n      while true:\n        var c = getchar()\n        if int(c) > int(' 
    '): get = true;result.add(c)\n        elif get: break\n    template `max=`*(x,y:typed):void = x = max(x,y)\n    template `min=`*(x,y:typed):void = 
    x = min(x,y)\n    template inf*(T): untyped = \n      when T is SomeFloat: T(Inf)\n      elif T is SomeInteger: T.high div 2\n      else: assert
    (false)\n  \n    discard\n  #[ import atcoder/extra/other/inf ]#\n  when not declared ATCODER_INF_HPP:\n    const ATCODER_INF_HPP* = 1\n    import 
    sequtils\n    template inf*(T: typedesc): untyped =\n      when T is SomeFloat: T(Inf)\n      elif T is SomeInteger: T.high div 2\n      else:\n  
          static: assert(false)\n    template infRepr*[T](x: T): string =\n      when T is seq or T is array:\n        \"@[\" & x.mapIt(it.infRepr
    ).join(\", \") & \"]\"\n      elif x is SomeInteger or x is SomeFloat:\n        when x is SomeUnsignedInt:\n          if x >= T.inf: \"inf\"\n    
          else: $x\n        else:\n          if x >= T.inf: \"inf\"\n          elif x <= -T.inf: \"-inf\"\n          else: $x\n      else:\n        
    $x\n    proc isInf*[T](x: T): bool = x >= T.inf\n    proc `∞`*(T: typedesc): T = T.inf\n    proc `*!`*[T: SomeInteger](a, b: T): T =\n      if a 
    == T(0) or b == T(0): return T(0)\n      var sgn = T(1)\n      if a < T(0): sgn = -sgn\n      if b < T(0): sgn = -sgn\n      let a = abs(a)\n     
     let b = abs(b)\n      if b > T.inf div a: result = T.inf\n      else: result = min(T.inf, a * b)\n      result *= sgn\n    proc `+!`*[T: 
    SomeInteger](a, b: T): T =\n      result = a + b\n      result = min(T.inf, result)\n      result = max(-T.inf, result)\n    proc `-!`*[T: 
    SomeInteger](a, b: T): T =\n      result = a - b\n      result = min(T.inf, result)\n      result = max(-T.inf, result)\n    discard\n\n  # const 
    INF = int.inf\n  const mod998 = 998244353\n  const mod107 = 1000000007\n  const mod109 = 1000000009\n\n  # 演算子\n  proc `%`(x: int, y: int): int 
    = (((x mod y)+y) mod y)\n  proc `//`(x: int, y: int): int = (((x) - (x%y)) div (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, 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  proc mul128(a, b, m: int): int {
    .importcpp: \"(__int128)(#) * (#) % (#)\", nodecl.}\n  proc powmod(a, n, m: int): int =\n    result = 1\n    var\n      a = a\n      n = n\n    
    while n > 0:\n      if n mod 2 != 0: result = mul128(result, a, m)\n      if n > 1: a = mul128(a, a, m)\n      n = n shr 1\n    return result\n  # 
    入出力\n  proc print(args: varargs[string, infRepr]) = echo args.join(\" \")\n  let readNext = iterator(getsChar: bool = false): string {.closure
    .} =\n    while true:\n      var si: string\n      try: si = stdin.readLine\n      except EOFError: yield \"\"\n      for s in si.split:\n        
    if getsChar:\n          for i in 0..<s.len():\n              yield s[i..i]\n        else:\n          if s.isEmptyOrWhitespace: continue\n         
     yield s\n  proc chmin[T](a: var T, b: T): bool {.discardable.} =\n    if a > b:\n      a = b\n      result = true\n    else:\n      result = 
    false\n  proc chmax[T](a: var T, b: T): bool {.discardable.} =\n    if a < b:\n      a = b\n      result = true\n    else:\n      result = false\n 
     iterator range(stop: int): int =\n    for i in 0..<stop: yield i\n  iterator range(start: int, stop: int, step: int = 1): int =\n    var i = 
    start\n    if step > 0:\n      while i < stop:\n        yield i\n        i += step\n    elif step < 0:\n      while i > stop:\n        yield i\n  
          i += step\n    else:\n      discard\n  iterator permutation[T](a: openArray[T], r: int): seq[T] =\n    let n = a.len\n    var p = toSeq(0
    ..<r) & newSeqWith(n-r, INF)\n    var loc = toSeq(0..<r)\n    yield loc.mapIt(a[it])\n    while nextPermutation(p):\n      for i, v in p:\n       
     if v != INF:\n          loc[v] = i\n      yield loc.mapIt(a[it])\n  iterator combinations[T](a: openArray[T], r: int): seq[T] =\n    let n = a
    .len\n    var p = newSeqWith(r, false) & newSeqWith(n-r, true)\n    let indices = toSeq(0..<n)\n    yield indices.filterIt(not p[it]).mapIt(a[it]
    )\n    while nextPermutation(p):\n      yield indices.filterIt(not p[it]).mapIt(a[it])\n  discard\n"
var N = nextInt()
var A = newSeqWith(N, nextInt())
var S = foldl(A, a ^ b, 0)
if S != 0 or (N == 2 and A[0] == A[1]):
  print("No")
  quit()
var d = initTable[int, int]()
for a in A:
  if not d.hasKey(a):
    d[a] = 0
  d[a] += 1
for k, v in d:
  if v >= 2 or k == 0:
    print("Yes")
    quit()
var ans = false
let M = 1<<13
var dp = newSeqWith(M, false)
dp[A[0]] = true
for i in range(1, N):
  var nxt_dp = newSeqWith(M, false)
  for j in range(M):
    nxt_dp[j] = nxt_dp[j] or dp[j]
    nxt_dp[j xor A[i]] = nxt_dp[j xor A[i]] or dp[j]
  if i == N-1 and not dp[0] and nxt_dp[0]:
    print("No")
    quit()
  dp = nxt_dp
if dp[0]:
  print("Yes")
else:
  print("No")
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX