D题题解(乱搞+背包)

想法其实比较简单, 我们考虑先假设往一个方向一直移动完, 这时候如果某一次移动后悔, 相当于反向走原来的两倍, 我们直接用01背包, 在最坏 O(nm) 的时间内找出能否拼凑出一个值,使得 sum(a)-value = 0 (mod n)

ac代码:

import sys
from collections import deque
from heapq import heappop,heappush
from math import ceil,inf,sqrt
input = sys.stdin.readline

def solve():
    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(m):
        a[i] %= n
    su = sum(a) % n
    for i in range(n):
        a[i] = (2*a[i]) % n
    f = [0]*(su+1)
    f[0] = 1
    for i in range(n):
        for j in range(su,a[i]-1,-1):
            f[j] += f[j-a[i]]
    print("YES" if f[su] != 0 else "NO")

# for _ in range(int(input())):
#     solve()
solve()