NAND repeatedly

题目描述

给定长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串 $S$。 它表示长度为 $N$ 的序列 $A=(A _ 1,A _ 2,\ldots,A _ N)$。如果 $S$ 的第 $i$ 个字符 $(1\leq i\leq N)$ 为 $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{matrix} A _ i&(i=j)\ f(i,j-1)\barwedge A _ j\quad&(i\lt j) \end{matrix}\right.] 这里，$\barwedge$，NAND，是一个二元运算，满足以下关系： [0\barwedge0=1,0\barwedge1=1,1\barwedge0=1,1\barwedge1=0.]

输入格式

输入按下述格式从标准输入给出： $N$ $S$

输出格式

在一行中输出答案。

5
00110

9

30
101010000100101011010011000010

326

提示

$1\leq N\leq10^6$ $S$ 是长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串。 所有输入值均为整数。下面给出满足 $1\leq i\leq j\leq 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)$.

标签: AtCoder|abc310E

来源

AtCoder|abc310E