No.1873 Bracket Swapping
タグ : / 解いたユーザー数 32
作問者 :
ぷら
shiomusubi496
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もしくは右上の雲マークをクリックしてアカウントを作成してください。