loj#P6765. 「THUPC 2021」形式语言与自动机
「THUPC 2021」形式语言与自动机
题目背景
《形式语言与自动机》是 T 大学 C 系开设的一门专业基础课,在这门课程中,你能学到“常用语言类及其相应的计算模型,以及计算模型之间的联系”。这门课程涉及到不少较为晦涩难懂的理论知识;但对于你的好朋友,曾经在国际比赛中捧杯的小 A 来说,它似乎有些太简单了。
题目描述
不知道为什么,小 A 虽然上课总在做自己的事情,但是每次布置的作业他用了十几分钟就做完了。你很好奇小 A 为什么这么熟练,但眼下,小 A 上课做的事情似乎更吸引你。
“你每周上课都不认真听,是在做什么?”
“我觉得老师上课讲得还挺水的,就随便做点东西玩玩。不过充其量也就是跟课程相关的吧,随便设计点自动机什么的,测试一下它能接受什么状态。”小 A 盯着他电脑前的草稿纸说道。
过了一会,小 A 看到他屏幕上出现了一堆圆括号。你猜想他可能是设计了一个判断括号序列是否匹配的自动机。但正当你准备和小 A 搭话时,他突然指着屏幕对你说:“你说说这合理吗,我本来输了一个测试用的括号序列,结果手一滑,把光标蹭到了奇怪的地方。我就想着怎么看半天没看出来程序哪里有问题,原来是我输错了。”
你苦笑着回复说:“这不常有的事吗,反正知道问题在哪就好了。”
没想到,这句话反而让小 A 更烦躁了。
“你说常有,那我给你这个串,你试试有多少种方法把它变回一个合法的括号序列。”
诚然,你不是不会算,但是你更想听课。可惜,你没来得及打断小 A 的下一句话。
“那就这么说定了,你要是下课前没算出来,请我吃香锅。”
输入格式
输入仅包括一个串 ,表示小 A 实际输入的串。保证 仅包括 (
和 )
,且二者数量相等。
输出格式
输出一个整数,表示本质不同的还原方案的个数。
我们定义一种方案可以还原一个括号序列 ,当且仅当存在一个划分 使得 是合法的括号序列。其中, 可以为空串(此时 ),但 和 不是空串。我们称两种还原方案本质不同,当且仅当两种方案中的 不相同或 不相同;即使两种还原方案还原出的串相同,这两种还原方案也可能本质不同。
()()()
6
样例 2
见附加文件中的 [2.in
](file:2.in) 与 [2.ans
](file:2.ans)。
样例 3
见附加文件中的 [3.in
](file:3.in) 与 [3.ans
](file:3.ans)。
子任务
对于 的数据,保证 。
提示
你不需要掌握《形式语言与自动机》这门课程的相关知识也能通过本题。
另外,《形式语言与自动机》这门课程“很简单”的说法只是本题中虚构人物小 A 的看法,不代表出题人的意见。