33074번 - SSHS 프로토콜

문제

SSHS 프로토콜은 0ドル$과 1ドル$로만 구성된 짝수 길이의 데이터를 전송할 수 있는 프로토콜이다. SSHS 프로토콜을 사용하여 데이터를 전송할 때 청구되는 비용은 다음과 같다.

• 전송하려고 하는 데이터를 0ドル$과 1ドル$로 구성된 길이 2ドルk$의 수열 $T$라고 하자. (단, $k \ge 1$)
• 청구 비용은 $\left( \sum_{i=1}^{k} T_i2^{k-i} \right) \times \left( \sum_{i=k+1}^{2k} T_i2^{2k-i} \right)$이다.
• 즉, $T$를 절반으로 자른 후 각각을 이진법 표기로 생각했을 때의 값의 곱만큼 비용이 청구된다.

SSHS 프로토콜을 사용할 때는 데이터의 길이가 길수록 청구되는 비용이 기하급수적으로 증가하기 때문에 데이터를 분할하여 전송하는 경우가 많다. 데이터를 분할하여 전송할 경우, 전체 청구 비용은 분할된 데이터의 청구 비용의 합이다. 길이 $N$의 데이터 $S$가 주어졌을 때, 전체 청구 비용의 최솟값을 구하여라.

엄밀한 설명은 다음과 같다:

• 데이터 $T$의 청구 비용을 $f(T)$라고 정의하자.
• 0ドル$과 1ドル$로 구성된 길이 $N$의 데이터 $S$가 주어진다. (단, $N$은 짝수)
• 1ドル = i_0 < i_1 < i_2 < \cdots < i_p < i_{p+1} = N+1,ドル 0ドル \le j \le p$인 모든 정수 $j$에 대해 $i_{j+1}-i_j$가 짝수인 $p$개의 정수 $i_1, i_2, \cdots, i_p$를 선택한다. (단, $p$는 0ドル$ 이상의 정수)
• 이때, 전체 청구 비용 $g(\{ i_1, i_2, \cdots, i_p \}) = \sum_{j=0}^{p} f(S_{i_j : (i_{j+1}-1)})$이다. ($s_{l : r}$은 $s$의 부분수열 $(s_l, s_{l+1}, \cdots, s_r)$를 나타낸다.)
• 전체 청구 비용 $g$의 최솟값을 구하여라.

데이터를 분할하지 않고 원본 그대로 전송하는 것도 가능함에 유의하자. 즉, $g(\emptyset)=f(S)$의 비용으로 $S$를 전송할 수 있다.

입력

첫 번째 줄에 데이터의 길이 $N$이 주어진다.

두 번째 줄에 0ドル$과 1ドル$로 구성된 길이 $N$의 데이터 $S$가 공백 없이 주어진다.

출력

$S$를 보낼 때 전체 청구 비용의 최솟값을 출력한다.

제한

• 2ドル \le N \le 2 \times 10^5$
• $N$은 짝수

힌트