Submission #855848

---

Source Code Expand

from collections import defaultdict
def enum(n,x,A):
	D = defaultdict(int)
	D[0] = 1
	L = [None]*(1<<n)
	L[0] = 0
	for k in xrange(1<<n):
		for j in xrange(n):
			jbit = 1<<j
			if (k&jbit): continue
			nbit = k + jbit
			if L[nbit] is None: 
				nv = L[k] + x[j]
				L[nbit] = nv
				cnt = bin(nbit).count("1")
				D[nv-A*cnt] += 1
	return D
def solve():
	N,A = map(int,raw_input().split())
	x = map(int,raw_input().split())
	n1 = N/2; n2 = N - n1
	D1 = enum(n1,x[:n1],A)
	D2 = enum(n2,x[n1:],A)
	ans = 0
	for k,v in D1.iteritems():
		ans += D2[-k]*v
	print ans - 1
solve()

Submission Info

Judge Result