← 返回题目列表

AtCoder · abc310_e

H. NAND 反复

中文机器翻译题面 查看原题

分数: 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