No.1772 Many DELETEQs
タグ : / 解いたユーザー数 30
作問者 : 👑 SPD_9X2 / テスター : hitonanode
注意
この問題は、 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もしくは右上の雲マークをクリックしてアカウントを作成してください。