反复求 NAND

题目描述

给定一个长度为 $N$、由 0 和 1 组成的字符串 $S$。 它描述了一个长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$。如果 $S$ 的第 $i$ 个字符 $(1 \le i \le N)$ 是 0,则 $A_i=0$;如果是 1,则 $A_i=1$。

求以下值:

$$\sum_{1 \le i \le j \le N}(\cdots((A_i \barwedge A_{i+1})\barwedge A_{i+2})\barwedge\cdots\barwedge A_j)$$

更正式地说,对于按如下方式定义的 $f(i,j)\ (1 \le i \le j \le N)$,求 $\displaystyle\sum_{i=1}^{N}\sum_{j=i}^{N}f(i,j)$:

[f(i,j)=\begin{cases} A_i & (i=j)\ f(i,j-1)\barwedge A_j & (i \lt j) \end{cases}]

这里,$\barwedge$ 表示 NAND,是满足以下条件的二元运算符:

$$0\barwedge0=1,\quad 0\barwedge1=1,\quad 1\barwedge0=1,\quad 1\barwedge1=0$$

输入格式

输入按以下格式从标准输入给出:

$N$
$S$

输出格式

在一行中输出答案。

样例

5
00110

9

下面是满足 $1 \le i \le j \le N$ 的每一对 $(i,j)$ 的 $f(i,j)$ 的值:

$f(1,1)=0=0$

$f(1,2)=0\barwedge0=1$

$f(1,3)=(0\barwedge0)\barwedge1=0$

$f(1,4)=((0\barwedge0)\barwedge1)\barwedge1=1$

$f(1,5)=(((0\barwedge0)\barwedge1)\barwedge1)\barwedge0=1$

$f(2,2)=0=0$

$f(2,3)=0\barwedge1=1$

$f(2,4)=(0\barwedge1)\barwedge1=0$

$f(2,5)=((0\barwedge1)\barwedge1)\barwedge0=1$

$f(3,3)=1=1$

$f(3,4)=1\barwedge1=0$

$f(3,5)=(1\barwedge1)\barwedge0=1$

$f(4,4)=1=1$

$f(4,5)=1\barwedge0=1$

$f(5,5)=0=0$

它们的和为 $0+1+0+1+1+0+1+0+1+1+0+1+1+1+0=9$,因此输出 $9$。

注意 $\barwedge$ 不满足结合律。 例如,$(1\barwedge1)\barwedge0=0\barwedge0=1\neq0=1\barwedge1=1\barwedge(1\barwedge0)$。

30
101010000100101011010011000010

326

数据范围

• $1 \le N \le 10^6$
• $S$ 是长度为 $N$、由 0 和 1 组成的字符串。
• 输入中的所有值均为整数。