No.1772 Many DELETEQs
タグ : / 解いたユーザー数 32
作問者 :
SPD_9X2
/ テスター :
👑
hitonanode
Note
This problem is a harder version of A DELETEQ. Note that the input and output formats are different.
Problem Statement
You have $x$ copies of the string "AB" and $y$ copies of the string "BA".
You arrange all of these $x+y$ strings in any order you like and concatenate them. (Let $S$ be the concatenated string.) Then, you perform the following operation any number of times, possibly $0$ times.
- Choose a pair of equal characters among $2$ consecutive characters of $S$, and delete the chosen $2$ characters from $S$. Then, concatenate the remaining parts before and after them, keeping their original order.
How many strings are possible as the remaining string $S$ after the operations? Find the count modulo $998244353$.
If the string $S$ after the operations can be the empty string, the empty string is also counted as $1$ possibility.
You are given $Q$ instances of this problem. Find the answer for each of them.
Input
$Q$ $x_1\ y_1$ $...$ $x_Q\ y_Q$
- All inputs are integers.
- $1 \le Q \le 2 \times 10^5$
- $1 \le x_i \le 4000$
- $1 \le y_i \le 4000$
Output
On the $i$-th line, output the answer for the case $x = x_i\ ,\ y = y_i$, followed by a newline.
Sample
Sample 1
Input
1 1 1
Output
5
"ABBA"
"BAAB"
"AA" (obtainable by "ABBA" → "AA")
"BB" (obtainable by "BAAB" → "BB")
"" (obtainable by "ABBA" → "AA" → "")
These $5$ strings are possible.
Sample 2
Input
2 3 1 4000 4000
Output
11 622937044
Output the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。