P7263 Something Comforting
Background
> Cause getting made you want more
>
> And hoping made you hurt more
>
> Someone tell me
>
> Something comforting
Description
Porter Robinson spent five years making the song Something Comforting, and Mivik spent five days making a problem related to bracket sequences. But Mivik is not happy, because he found that he does not know how to generate testdata anymore.
Mivik needs to randomly generate a **valid** bracket sequence, so after thinking for a while, he wrote the following algorithm:
```cpp
#include
#include
std::string generate(int n) { // generate a bracket sequence of length n * 2
const int len = n * 2;
bool arr[len]; // 0 means left bracket, 1 means right bracket
for (int i = 0; i < n; ++i) arr[i] = 0;
for (int i = n; i < len; ++i) arr[i] = 1;
std::random_shuffle(arr, arr + len); // randomly shuffle this array
for (int i = 0, j, sum = 0; i < len; ) {
sum += arr[i]? -1: 1;
if (sum < 0) { // an invalid position appears
for (j = i + 1; j < len; ++j) {
sum += arr[j]? -1: 1;
if (sum == 0) break;
}
// now i is the first invalid position, and j is the first valid position after i
// ( ( ) ) ) ) ( ( ( ) ( )
// i j
for (int k = i; k
Input Format
The first line contains an integer $n$, with the same meaning as in the statement.
Next, input a valid bracket sequence of length $2n$, with the same meaning as in the statement.
Output Format
Output one line with one integer, representing this probability modulo $998244353$.
Explanation/Hint
### Sample Explanation
Sample 1: When $n$ is 1, no matter what, the only possible valid bracket sequence that can be generated is `()`, so the probability is 1.
### Constraints
For all data, $1\le n\le 5\cdot 10^5$, and the input bracket sequence is valid.
Subtask 1 (20 pts): $1\le n\le 5$.
Subtask 2 (30 pts): $1\le n\le 1000$.
Subtask 3 (50 pts): No additional constraints.
Translated by ChatGPT 5