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