Submission #70055732

---

Source Code Expand

from collections import defaultdict


def enum_left(a, m):
  n = len(a)
  out = []
  def dfs(i, prev, s):
    if i == n:
      out.append((s % m, 1 if prev else 0))
      return
    dfs(i + 1, False, s)
    if not prev:
      dfs(i + 1, True, (s + a[i]) % m)
  dfs(0, False, 0)
  return out

def enum_right(a, m):
  n = len(a)
  out = []
  def dfs(i, prev, s, first):
    if i == n:
      out.append((s % m, 1 if first else 0))
      return
    dfs(i + 1, False, s, first)
    if not prev:
      dfs(i + 1, True, (s + a[i]) % m, first or (i == 0))
  dfs(0, False, 0, False)
  return out

n, m = map(int, input().split())
a = list(map(int, input().split()))
mid = n // 2
l = a[:mid]
r = a[mid:]

left = enum_left(l, m)
right = enum_right(r, m)

cnt = defaultdict(int)
for s, first in right:
  cnt[(s, first)] += 1

ans = 0
for s_l, last in left:
  need = (-s_l) % m
  if last == 1:
    ans += cnt.get((need, 0), 0)
  else:
    ans += cnt.get((need, 0), 0) + cnt.get((need, 1), 0)

print(ans)

Submission Info

Judge Result