問題一覧 > 通常問題

No.1772 Many DELETEQs

レベル : / AI推定難易度 : 2550 / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 32
作問者 : SPD_9X2 / テスター : 👑 hitonanode
お気に入りにしたユーザー ProblemId : 7360 / 自分の提出
問題文最終更新日: 2021-12-04 19:12:53
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

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もしくは右上の雲マークをクリックしてアカウントを作成してください。