Submission #70049576

---

Source Code Expand

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)
if 0:
    import pypyjit
    pypyjit.set_param('max_unroll_recursion=-1')

n, m = map(lambda s_: int(s_), input().split())
a = tuple(map(lambda s_: int(s_), input().split()))

from collections import defaultdict
acc = [[defaultdict(int) for _ in range(2)]]

def dfs(b, i, s):
    nn = len(b)
    if i >= nn:
        acc[-1][0][s] += 1
        return
    # no take
    dfs(b, i + 1, s)
    # take
    ns = (s + b[i]) % m
    if i == nn - 1:
        acc[-1][1][ns] += 1
    else:
        dfs(b, i + 2, ns)

h = n // 2
dfs(a[:h], 0, 0)
acc.append([defaultdict(int) for _ in range(2)])
dfs(a[h:][::-1], 0, 0)

ans = 0
for i0, c0 in enumerate(acc[0]):
    for i1, c1 in enumerate(acc[1]):
        if i0 and i1:
            continue
        for s0, f0 in c0.items():
            ans += f0 * c1[-s0 % m]
print(ans)

Submission Info

Judge Result