P7604 [THUPC 2021] 形式语言与自动机

《形式语言与自动机》是 T 大学 C 系开设的一门专业基础课，在这门课程中，你能学到“常用语言类及其相应的计算模型，以及计算模型之间的联系”。这门课程涉及到不少较为晦涩难懂的理论知识；但对于你的好朋友，曾经在国际比赛中捧杯的小 A 来说，它似乎有些太简单了。

不知道为什么，小 A 虽然上课总在做自己的事情，但是每次布置的作业他用了十几分钟就做完了。你很好奇小 A 为什么这么熟练，但眼下，小 A 上课做的事情似乎更吸引你。 “你每周上课都不认真听，是在做什么？” “我觉得老师上课讲得还挺水的，就随便做点东西玩玩。不过充其量也就是跟课程相关的吧，随便设计点自动机什么的，测试一下它能接受什么状态。”小 A 盯着他电脑前的草稿纸说道。 过了一会，小 A 看到他屏幕上出现了一堆圆括号。你猜想他可能是设计了一个判断括号序列是否匹配的自动机。但正当你准备和小 A 搭话时，他突然指着屏幕对你说：“你说说这合理吗，我本来输了一个测试用的括号序列，结果手一滑，把光标蹭到了奇怪的地方。我就想着怎么看半天没看出来程序哪里有问题，原来是我输错了。” 你苦笑着回复说：“这不常有的事吗，反正知道问题在哪就好了。” 没想到，这句话反而让小 A 更烦躁了。 “你说常有，那我给你这个串，你试试有多少种方法把它变回一个合法的括号序列。” 诚然，你不是不会算，但是你更想听课。可惜，你没来得及打断小 A 的下一句话。 “那就这么说定了，你要是下课前没算出来，请我吃香锅。”

输入仅包括一个串 $s$，表示小 A 实际输入的串。保证 $s$ 仅包括 `(` 和 `)`，且二者数量相等。

输出一个整数，表示**本质不同**的还原方案的个数。 我们定义一种方案可以还原一个括号序列 $s=s_1 s_2 \cdots s_n$，当且仅当存在一个划分 $s=uvw$ 使得 $uwv$ 是合法的括号序列。其中，$u=s_1\cdots s_l$ 可以为空串（此时 $l=0$），但 $v=s_{l+1}\cdots s_r$ 和 $w=s_{r+1}\cdots s_n$ 不是空串。我们称两种还原方案**本质不同**，当且仅当两种方案中的 $l$ 不相同或 $r$ 不相同；即使两种还原方案还原出的串相同，这两种还原方案也可能本质不同。

**【样例解释】** 所有可能的还原方案为（其中箭头前后分别为 $s=u+v+w$ 和 $uwv$）： 1. $l=0,r=2$，对应 $\varepsilon$（空串，下同）$+$`()`$+$`()()` $\Rightarrow$ `()()()`； 2. $l=0,r=4$，对应 $\varepsilon+$`()()`$+$`()`$\Rightarrow$`()()()`； 3. $l=1,r=2$，对应 `(`$+$`)`$+$`()()`$\Rightarrow$`(()())`； 4. $l=1,r=4$，对应 `(`$+$`)()`$+$`()`$\Rightarrow$`(())()`； 5. $l=2,r=4$，对应 `()`$+$`()`$+$`()`$\Rightarrow$`()()()`； 6. $l=3,r=4$，对应 `()(`$+$`)`$+$`()`$\Rightarrow$`()(())`。 这些划分方案中，方案 $1,2,5$ 还原出的串和输入的串相同，但这并不影响它们划分的方式不同。 另外，`()()`$+$`()`$+\varepsilon$ 和 `()()`$+\varepsilon+$`()` 都不是合法的还原方案，因为在前一种划分中 $w=\varepsilon$，而在后一种划分中 $v=\varepsilon$。 **【数据范围】** 对于 $100\%$ 的数据，保证 $1\le |s| \le 10,000,000$。 **【提示】** 你不需要掌握《形式语言与自动机》这门课程的相关知识也能通过本题。 另外，《形式语言与自动机》这门课程“很简单”的说法只是本题中虚构人物小 A 的看法，不代表出题人的意见。 **【题目来源】** 来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。 题解等资源可在 [https://github.com/yylidiw/thupc_0/tree/master](https://github.com/yylidiw/thupc_0/tree/master) 查看。