切糕

NC233244. 切糕

描述

小沙觉得括号真是一个神奇的东西，以至于他看什么都觉得这东西像一串括号，小沙买来了切糕，他准备将它分成几份拿来吃，但是小沙突然希望把他眼中的括号切糕全部切成合法的括号切糕。

请问小沙有多少种切法，不同的切法仅看切的位置，如果有一个位置切的不同，那么切法就不一样。

如果你无论如何也切不出来合法切糕，那么输出-1

合法的括号：指对于一个字符串他的左括号数量和右括号一样多，且对于任意前缀左括号始终不小于右括号数。

字符串的前缀：指字符串的从第一个字符开始，到任意字符停止的一个字符串。

左括号 ( 右括号 )

答案对1e9+7取模

输入描述

输入一行字符串，仅包含'(' ')'两种字符 字符串长度不超过

输出描述

输出一个整数代表有多少种切法

示例1

输入:

()()

输出:

说明:

可以不切这样合法串为 ()()

可以切一次 () () 切成两个

示例2

输入:

(())

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

pypy3 解法, 执行用时: 107ms, 内存消耗: 23572K, 提交时间: 2023-07-02 01:06:33

s = input()
res = 1
sum = 0
ok = True
mod = 1000000007
inv2 = (mod + 1) // 2
for c in s:
  if c == '(':
    sum += 1
  if c == ')':
    sum -= 1
  if sum < 0:
    ok = False;
  if sum == 0:
    res = res * 2 % mod
res = res * inv2 % mod
if sum != 0:
  ok = False
if not ok:
  res = -1
print(res)

Python3 解法, 执行用时: 115ms, 内存消耗: 5572K, 提交时间: 2022-03-13 15:57:13

s=input()
w=0
cnt=0

for i in s:
    if i=='(':
        w+=1
    else:
        w-=1
        if w<0:
            break
    if w==0:cnt+=1

# print(cnt)
if w!=0:print(-1)
else:print(pow(2,cnt-1,10**9+7))

上一题

下一题

详情