Правильная скобочная последовательность

Ниже приведён пример максимально оптимизированного (по асимптотике) кода на Python, решающего задачу подсчёта количества способов заменить символы «?» на правильные скобки так, чтобы получилась корректная скобочная последовательность. Алгоритм использует динамическое программирование за $O(N^3)$, что для $N \le 200$ является реалистичным при хорошей реализации и аккуратном обращении с памятью.

python
import sys
sys.setrecursionlimit(10**7)

MOD = 10**9 + 7

def solve():
    # Считываем входные данные
    N = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    
    # Если длина нечётная, решений быть не может
    # (но по условию N чётно, так что можно не проверять, оставим на всякий случай)
    if N % 2 == 1:
        print(0)
        return
    
    # Предварительно зададим вспомогательные структуры:
    # 1) Пары открывающих/закрывающих скобок
    valid_pairs = {('(', ')'), ('[', ']'), ('{', '}')}
    
    # 2) Функции, возвращающие набор возможных открывающих/закрывающих
    #    скобок при учёте символа '?'
    def possible_openings(ch):
        # Если ch - открывающая скобка или '?'
        if ch == '(' or ch == '[' or ch == '{':
            return [ch]
        elif ch == '?':
            return ['(', '[', '{']
        else:
            return []
    
    def possible_closings(ch):
        # Если ch - закрывающая скобка или '?'
        if ch == ')' or ch == ']' or ch == '}':
            return [ch]
        elif ch == '?':
            return [')', ']', '}']
        else:
            return []
    
    # 3) Функция, которая подсчитывает, сколько способов
    #    «совместить» символ s[i] (открывающий) и s[j] (закрывающий)
    #    в пару, учитывая возможность '?'.
    def match_count(a, b):
        count = 0
        for oa in possible_openings(a):
            for cb in possible_closings(b):
                if (oa, cb) in valid_pairs:
                    count += 1
        return count
    
    # dp[i][j] будет хранить количество способов получить
    # правильную скобочную подпоследовательность из подстроки s[i..j].
    dp = [[0]*(N) for _ in range(N)]
    
    # База динамики: подстроки длины 1 (i.e. j - i + 1 = 1) не могут быть валидными,
    # потому что одна скобка не может образовать ПСП. Но в классическом варианте
    # мы чаще инициализируем dp[i][i-1] = 1 для пустой подстроки.
    # Здесь сделаем явную обработку длины 0 отдельно:
    
    # Удобнее завести dp[i][i-1] = 1, но индексы будут выходить за границы,
    # поэтому сделаем дополнительное условие в цикле.
    
    # Реализация через увеличение длины подстроки от меньшей к большей:
    for length in range(2, N+1):          # length - длина подстроки
        for i in range(N - length + 1):  # i - начало подстроки
            j = i + length - 1           # j - конец подстроки
            
            # Если длина подстроки нечетная (length % 2 != 0),
            # она не может быть правильной - пропускаем.
            if (length % 2) == 1:
                dp[i][j] = 0
                continue
            
            # Перебираем позицию k, которая будет парой к i-му элементу.
            # В классическом алгоритме мы делаем:
            # dp[i][j] = суммарное количество dp[i+1][k-1] * dp[k+1][j],
            # умноженное на количество способов "скрестить" s[i] и s[k].
            # k идёт с шагом 2 (т.к. между i и k чётное расстояние, чтобы внутри была
            # корректная скобочная подпоследовательность).
            
            total_ways = 0
            for k in range(i+1, j+1, 2):  # шаг 2, т.к. внутри пара i..k должна иметь чётную длину
                ways_to_match = match_count(s[i], s[k])
                if ways_to_match == 0:
                    continue
                
                left_part = dp[i+1][k-1] if (k-1 >= i+1) else 1
                right_part = dp[k+1][j] if (k+1 <= j) else 1
                
                total_ways += (left_part * ways_to_match * right_part) % MOD
                total_ways %= MOD
            
            dp[i][j] = total_ways % MOD
    
    # Результат - dp[0][N-1]
    print(dp[0][N-1] % MOD)

# Если требуется запуск из данного файла:
# if __name__ == "__main__":
#     solve()

Пояснение решения

1. Динамическое программирование по отрезкам
   Мы используем классический подход: $\text{dp}[i][j]$ хранит количество способов получить правильную скобочную последовательность из подстроки $s[i \dots j]$.

2. Основная рекуррентная формула
   Пусть скобка на позиции $i$ хочет «спариться» со скобкой на позиции $k$ ($i < k \le j$, причём $k - i$ нечётно, чтобы внутри мог уместиться «парный» участок). Если $s[i]$ и $s[k]$ действительно могут образовать пару (учитывая возможные варианты «?»), то

   $$\text{dp}[i][j] \;{+}{=}\; \text{dp}[i+1][k-1] \times \text{dp}[k+1][j] \times \text{match\_count}(s[i], s[k]),$$

   где:

   • $\text{dp}[i+1][k-1]$ — количество способов сделать правильную скобочную последовательность из подстроки внутри пары (между $i$ и $k$),
   • $\text{dp}[k+1][j]$ — количество способов «закрыть» оставшуюся часть после $k$,
   • $\text{match\_count}(s[i], s[k])$ — число способов сопоставить скобки $s[i]$ и $s[k]$ (например, если обе — «?», тогда можно выбрать любую из трёх возможных пар «()», «[]», «{}»).

3. Подсчёт количества пар
   Функция match_count(a, b) учитывает ситуации, когда:

   • Оба символа уже фиксированы (например, «(» и «)»), либо
   • Один или оба — «?», что позволяет выбрать среди соответствующих открывающих/закрывающих вариантов.

4. Сложность
   При длине $N$ перебираются все пары $(i, j)$, их $\approx O(N^2)$. Для каждого $(i, j)$ мы перебираем $k$ с шагом 2, это $\approx O(N)$. Итого асимптотика $O(N^3)$. При $N \le 200$ и аккуратном коде это выполнимо за разумное время в Python (в пределах нескольких секунд).

5. Память
   $dp$ — это двумерный массив $N \times N$, что при $N = 200$ даёт всего 40 000 элементов. Это достаточно мало для современной системы.

Таким образом, данный код выводит количество способов заменить «?» на скобки так, чтобы итоговая скобочная последовательность стала правильной, по модулю $10^9 + 7$.