import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
N,S = map(int,input().split())
seq = [*map(int,input().split())]
seq1 = seq[:N//2]
seq2 = seq[N//2:]
sum1 = []
sum2 = []
def SUM(seq,sumlist,x,start):
for i in range(start+1,len(seq)):
sumlist.append(x+seq[i])
SUM(seq,sumlist,x+seq[i],i)
SUM(seq1,sum1,0,-1)
SUM(seq2,sum2,0,-1)
sum1.append(0)
sum2.append(0)
sum1.sort()
sum2.sort()
cnt = 0
for num in sum1:
cnt += bisect_right(sum2,S-num)-bisect_left(sum2,S-num)
if S == 0:
print(cnt-1)
else:
print(cnt)
처음에는 대체 이 문제를 어떻게 접근해야하는건지 막막했다. 그래서 거의 일주일을 넘게 묵혀놨던 문제이다.
그러다가 이 문제의 태그를 봤는데, 중간에서 만나기 라는 태그가 있었다.
중간에서 만나기? 중간에서 만나기... 중간에서 만나기라.... 아하! 하는 순간이 왔다.
이 문제는 그냥 브루트포스로 풀면 경우의 수가 무려 2^40이 된다. 그러나 수열을 절반으로 쪼개고, 각각 20개, 20개 원소에 대해서 풀면 경우의 수를 2^20+2^20으로 감소시킬 수 있다.
그리고 나서는 이진 탐색을 이용해서 두 부분수열의 합이 S인 경우를 출력하면 된다. 이때의 알고리즘은 바로 전 문제인 두 배열의 합과 거의 유사하다.
한가지 유의할 점은 절반으로 쪼갠 각각의 수열에 대해서 그 수열 내의 합으로만 S가 나오는 경우가 존재한다는 것이다. 그래서 각 수열에 0을 대입해 주었다.
여기서 또 주의할 점은 문제가 요구하는 답이 0인 경우에 0+0으로 경우의 수가 한가지 더 추가된다는 것이다. 이 경우에 대한 코드가 마지막 줄에 있다.
오늘의 교훈) 둘로 분리해서 시간복잡도를 줄이는 방법을 고려하자