题解 | #D. 我不是大富翁#

注意到这是一个 Modular Subset Sum 模板题。算法参见 SOSA'21 的这两篇文章：
https://arxiv.org/abs/2008.08417
https://arxiv.org/abs/2008.10577

复杂度 ，可优化到 。

以下是直接从 paper 里抄的模板：

import random

def ModularSubsetSum(W, m):
    p = 1234567891                              # large prime p > m^2 log m
    r = random.randint(0,p)                     # random number r in [0,p)
    powr = [1]                                  # Precompute powers of r
    for i in range (2*m):                       # powr[i] = r^i (mod p)
        powr.append((powr[-1] * r) % p)
    
    # Binary Indexed Tree for prefix sums
    tree = [0] * (2*m)
    
    def read(i):                                # Prefix sum of [0,i)
        if i<=0: return 0
        return tree[i-1] + read(i-(i&-i))
    
    def update(i, v):                           # add v to position i
        while i < len(tree):
            tree[i] += v
            i += (i+1)&-(i+1)
    
    # Functions for finding new subset sums and adding them
    def FindNewSums(a, b, w):
        h1 = (read(b)-read(a))*powr[m-w] % p    # hash of S ∩ [a, b)
        h2 = (read(b+m-w)-read(a+m-w)) % p      # hash of (S+w) ∩ [a, b)
        if h1 == h2: return []
        if b == a+1:
            if sums[a] is None: return [a]      #a is a new sum
            return []                           #a is a ghost sum
        return FindNewSums(a,(a+b)//2,w) + FindNewSums((a+b)//2,b,w)
    
    def AddNewSum(s, w):
        sums[s] = w
        update(s,powr[s]), update(s+m,powr[s+m])
    
    # Main routine for computing subset sums
    sums = [None] * m
    AddNewSum(0,0)
    W = [w%m for w in W]
    for w in W:
        for s in FindNewSums(0,m,w):
            AddNewSum(s,w)
    
    return sums
    
def RecoverSubset(sums, s):
    if sums[s] is None: return None
    if s <= 0: return []
    return RecoverSubset(sums,(s-sums[s])%len(sums))+[sums[s]]

m,n = map(int,input().split())
a = list(map(int,input().split()))
ans = ModularSubsetSum([2*x for x in a], m)
s=sum(a)%m
print("YES" if ans[s] != None else "NO")