問題一覧 > 通常問題

No.1873 Bracket Swapping

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : ytqm3 / テスター : ぷら shiomusubi496
お気に入りにしたユーザー ProblemId : 7091 / 自分の提出
問題文最終更新日: 2023-06-03 13:58:51
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 335 (順位表) の他の問題:

Problem Statement

You are given a regular bracket sequence $S$ and a non-negative integer $K$. Among the ways to perform the following operation on $S$ exactly $K$ times, find the number of ways such that $S$ after the operations is a regular bracket sequence, modulo $998244353$.

  • Choose a pair of integers $(i, j)$ satisfying $1 \le i < j \le |S|$. Swap the $i$-th and $j$-th characters of $S$.

Here, $2$ ways of performing the operations are considered different if and only if there exists an integer $l\ (1 \le l \le K)$ such that the pairs $(i,j)$ chosen in the $l$-th operation differ.


Definition of a regular bracket sequence (click to expand)

A string satisfying any of the following conditions is defined as a regular bracket sequence.

  • The empty string
  • A string obtained by concatenating ($,A,$) in this order, for some regular bracket sequence $A$
  • A string obtained by concatenating $A, B$ in this order, for some non-empty regular bracket sequences $A, B$

Input

$S$
$K$
  • $S$ is a regular bracket sequence
  • $2 \le |S| \le 200$
  • $0 \le K \le 10^9$

Output

Output the answer.

Sample

Sample 1
Input
(())
1
Output
3

The condition is satisfied when $(i,j)=(1,2),(2,3),(3,4)$ is chosen in operation number $1$.

Sample 2
Input
()
100
Output
1

Sample 3
Input
(()(()(())()))
924844033
Output
392727613

Do not forget to output the answer modulo $998244353$.

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