
ZOJ Problem Set  4054
BaoBao is taking a walk in the interval $[0, n]$ on the number axis, but he is not free to move, as at every point $(i  0.5)$ for all $i \in [1, n]$, where $i$ is an integer, stands a traffic light of type $t_i$ ($t_i \in \{0, 1\}$). BaoBao decides to begin his walk from point $p$ and end his walk at point $q$ (both $p$ and $q$ are integers, and $p < q$). During each unit of time, the following events will happen in order:
A traffic light of type 0 is initially red, and a traffic light of type 1 is initially green. Denote $t(p, q)$ as the total units of time BaoBao needs to move from point $p$ to point $q$. For some reason, BaoBao wants you to help him calculate $$\sum_{p=0}^{n1}\sum_{q=p+1}^n t(p, q)$$ where both $p$ and $q$ are integers. Can you help him? InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first and only line contains a string $s$ ($1 \le s \le 10^5$, $s = n$, $s_i \in \{\text{'0'}, \text{'1'}\}$ for all $1 \le i \le s$), indicating the types of the traffic lights. If $s_i = \text{'0'}$, the traffic light at point $(i  0.5)$ is of type 0 and is initially red; If $s_i = \text{'1'}$, the traffic light at point $(i  0.5)$ is of type 1 and is initially green. It's guaranteed that the sum of $s$ of all test cases will not exceed $10^6$. OutputFor each test case output one line containing one integer, indicating the answer. Sample Input3 101 011 11010 Sample Output12 15 43 HintFor the first sample test case, it's easy to calculate that $t(0, 1) = 1$, $t(0, 2) = 2$, $t(0, 3) = 3$, $t(1, 2) = 2$, $t(1, 3) = 3$ and $t(2, 3) = 1$, so the answer is $1 + 2 + 3 + 2 + 3 + 1 = 12$. For the second sample test case, it's easy to calculate that $t(0, 1) = 2$, $t(0, 2) = 3$, $t(0, 3) = 5$, $t(1, 2) = 1$, $t(1, 3) = 3$ and $t(2, 3) = 1$, so the answer is $2 + 3 + 5 + 1 + 3 + 1 = 15$. Author: WENG, Caizhi Source: The 2018 ACMICPC Asia Qingdao Regional Contest, Online 