QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB

# 5189. 形式语言与自动机

统计

题目背景

《形式语言与自动机》是 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$ 不相同;即使两种还原方案还原出的串相同,这两种还原方案也可能本质不同。

样例数据

样例 1 输入

()()()

样例 1 输出

6

样例 1 解释

所有可能的还原方案为(其中箭头前后分别为 $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$。

样例 2

见附加文件中的 2.in2.ans

样例 3

见附加文件中的 3.in3.ans

子任务

对于 $100\%$ 的数据,保证 $1\le |s| \le 10,000,000$。

提示

你不需要掌握《形式语言与自动机》这门课程的相关知识也能通过本题。

另外,《形式语言与自动机》这门课程“很简单”的说法只是本题中虚构人物小 A 的看法,不代表出题人的意见。