分数: 450 点
问题陈述
给你一个字符串 S 长度 N 组成 0 和 1。
它描述了一个长度-N 序列 A=(A _ 1,A _ 2,\ldots,A _ N)。如果 i- 第一个字符 S (1\leq i\leq N) is 0,那么 A _ i=0;如果是的话 1,那么 A _ i=1.
查找以下内容:
\[\sum _ {1\leq i\leq j\leq N}(\cdots((A _ i\barwedge A _ {i+1})\barwedge A _ {i+2})\barwedge\cdots\barwedge A _ j)\]
更正式地说,找到 \displaystyle\sum _ {i=1} ^ {N}\sum _ {j=i} ^ Nf(i,j) 为 f(i,j)\ (1\leq i\leq j\leq N) 定义如下:
\[f(i,j)=\left\{\begin{矩阵} A _ i&(i=j)\\ f(i,j-1)\barwedge A _ j\quad&(i\lt j) \end{矩阵}\右。\]
在这里, \barwedge,NAND,是满足以下条件的二元运算符:
\[0\barwedge0=1,0\barwedge1=1,1\barwedge0=1,1\barwedge1=0.\]
约束
- 1\leq N\leq10^6
- S 是一个长度为 N 组成
0和1. - 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N S
输出
在一行中打印答案。
示例输入 1
5 00110
示例输出 1
9
这是以下值 f(i,j) 为配对 (i,j) 这样 1\leq i\leq j\leq N:
- 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).
示例输入 2
30 101010000100101011010011000010
示例输出 2
326