問題一覧 > 通常問題

No.1772 Many DELETEQs

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : 👑 SPD_9X2SPD_9X2 / テスター : 👑 hitonanodehitonanode
1 ProblemId : 7360 / 自分の提出
問題文最終更新日: 2021-12-04 19:12:53

注意

この問題は、 A DELETEQ の強化版です。入出力の形式が異なることに注意してください。

問題文

あなたは、$x$ 個の文字列"AB"と、$y$ 個の文字列"BA"を持っています。

あなたは、この $x+y$ 個の全ての文字列を好きな順番で並べて連結します。(連結後の文字列を $S$ とします。)その後、以下の操作を $0$ 回以上の任意の回数行います。

  • $S$ の連続する $2$ 文字で、等しい文字のペアを選び、選んだ $2$ 文字を $S$ から削除する。その後、残った前後の文字列を元の順番で連結する。

操作後、残った文字列 $S$ として考えられるものは何通り存在しますか。場合の数を $998244353$ で割った余りを答えてください。

なお、操作後の文字列 $S$ が空文字列になりうる場合、空文字列も $1$ 通りとして数えます。


この問題が $Q$ 個与えられるので、そのそれぞれに関して答えを求めてください。

入力

$Q$
$x_1\ y_1$
$...$
$x_Q\ y_Q$

  • 入力は全て整数
  • $1 \le Q \le 2 \times 10^5$
  • $1 \le x_i \le 4000$
  • $1 \le y_i \le 4000$

出力

$i$ 行目には、 $x = x_i\ ,\ y = y_i$ の場合の答えを出力し、改行してください。

サンプル

サンプル1
入力
1
1 1
出力
5

"ABBA"
"BAAB"
"AA" ( "ABBA" → "AA" で構築可能)
"BB" ( "BAAB" → "BB" で構築可能)
"" ( "ABBA" → "AA" → "" で構築可能)
以上の $5$ 通りの文字列が考えられます。

サンプル2
入力
2
3 1
4000 4000
出力
11
622937044

$998244353$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。