2022 T3 逻辑表达式

主知识点：模拟与字符串。交叉标签：表达式、栈、深搜、树形动态规划。
暴力标注：有非 DP 满分解。
OJ 使用标准输入与标准输出。原比赛文件名为 expr.in / expr.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 20；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

给出只含 0、1、&、|、(、) 的合法逻辑表达式。先算括号内，& 优先于 |，同优先级从左到右计算。

逻辑与的左侧为 0 时，右侧不再计算；逻辑或的左侧为 1 时，右侧不再计算。求表达式的值，以及两类短路分别发生的次数。被更外层短路跳过的子表达式中，所有内部短路都不计数。例如 1|(0&1) 仅计一次或短路。

输入格式

输入共一行，一个非空字符串 $s$ 表示待计算的逻辑表达式。

输出格式

输出共两行，第一行输出一个字符 0 或 1，表示这个逻辑表达式的值；第二行输出两个非负整数，分别表示计算上述逻辑表达式的过程中，形如 a&b 和 a|b 的“短路”各出现了多少次。

样例

样例 1

输入：

0&(1|0)|(1|1|1&0)

输出：

1
1 2

样例 2

输入：

(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0

输出：

0
2 3

数据范围与特殊性质

设 $\lvert s \rvert$ 为字符串 $s$ 的长度。

对于所有数据，$1 \le \lvert s \rvert \le {10}^6$。保证 $s$ 中仅含有字符 0、1、&、|、(、) 且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证 $s$ 中没有重复的括号嵌套（即没有形如 ((a)) 形式的子串，其中 a 是符合规范的逻辑表达式）。

测试点编号	$\lvert s \rvert \le$	特殊条件
$1 \sim 2$	$3$	无
$3 \sim 4$	$5$
$5$	$2000$	1
$6$		2
$7$		3
$8 \sim 10$		无
$11 \sim 12$	${10}^6$	1
$13 \sim 14$		2
$15 \sim 17$		3
$18 \sim 20$		无

其中：
特殊性质 1 为：保证 $s$ 中没有字符 &。
特殊性质 2 为：保证 $s$ 中没有字符 |。
特殊性质 3 为：保证 $s$ 中没有字符 ( 和 )。

【提示】

以下给出一个“符合规范的逻辑表达式”的形式化定义：

• 字符串 0 和 1 是符合规范的；

• 如果字符串 s 是符合规范的，且 s 不是形如 (t) 的字符串（其中 t 是符合规范的），那么字符串 (s) 也是符合规范的；

• 如果字符串 a 和 b 均是符合规范的，那么字符串 a&b、a|b 均是符合规范的；

• 所有符合规范的逻辑表达式均可由以上方法生成。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

有非 DP 满分解。栈解析或递归下降直接实现短路语义即可满分。必须跳过被外层短路的右表达式内部计数；反复扫描子串找分割点可能退化到 O(|s|²)，只适合长度≤2000 的部分。

目标范围：线性解析可满分。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P8815
• 赛事：CSP-J 第二轮入门级 2022。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。