問題一覧 > 通常問題

No.3138 Minimum Bracket Subsequence

レベル : / AI推定難易度 : 2850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : 👑 potato167
お気に入りにしたユーザー ProblemId : 12214 / 自分の提出
問題文最終更新日: 2025-05-02 21:12:12
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 466 オムニバスコンテスト (順位表) の他の問題:

Problem Statement

You are given integers $N, K$ and a correct bracket sequence $S$ of length $K$ consisting of (,).

Find the number, modulo $998244353$, of strings $T$ of length $N$ consisting of (,) that satisfy all of the following conditions.

  • There exists a subsequence of $T$ that is a correct bracket sequence of length $K$.
  • Among the subsequences of $T$ that are correct bracket sequences of length $K$, the lexicographically smallest one is $S$.

For the lexicographic order on strings consisting of (,), the character ( is considered smaller than ).

A correct bracket sequence is a string that can be made empty by repeating the operation of deleting a substring equal to () $0$ or more times.

Constraints

  • $K\leq N\leq\boldsymbol{\textcolor{FF0000}{10^{18}}}$
  • $2\leq K\leq 5\times 10^{5}$
  • $N, K$ are integers.
  • $S$ is a correct bracket sequence of length $K$ consisting of (,).

Input

$N\ K$
$S$

Output

Output the answer.

Sample

Sample 1
Input
7 4
(())
Output
64

For example, when $T = $((()))), the only subsequence of $T$ that is a correct bracket sequence of length $4$ is (()), which equals $S$, so the conditions are satisfied.

When $T = $((())(), there are $2$ kinds of subsequences of $T$ that are correct bracket sequences of length $4$, namely ()() and (()), and the lexicographically smallest one is (()), so the conditions are satisfied.

Sample 2
Input
1000000000000000000 28
(()()(()))(()((()))())()(())
Output
118659188

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。