問題一覧 > 通常問題

No.1771 A DELETEQ

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : SPD_9X2SPD_9X2 / テスター : 👑 hitonanodehitonanode
5 ProblemId : 7125 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-02 21:44:08

注意

この問題の強化版として、 Many DELETEQs があります。入出力の形式が異なることに注意してください。

問題文

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

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

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

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

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

入力

$x\ y$

この問題の通常制約は以下のようになっています。この制約を満たす全てのテストケースについて正解すれば、判定はACとなります。

  • 入力は全て整数
  • $1 \le x \le 4000$
  • $1 \le y \le 4000$


また、この問題には高難易度の制約が、AC判定とは関係のないevilケースとして用意されています。余力のある方はぜひ挑戦してみてください。(Many DELETEQsよりも難しいと思います。)
evilケースの制約は以下のようになっています。

  • 入力は全て整数
  • $1 \le x \le 10^5$
  • $1 \le y \le 10^9$
なお、evilケースに挑戦しない場合、入力が通常制約を満たしていない場合に即座にプログラムを終了するようにしていただけると、ジャッジが早く終了します。

出力

答えを $1$ 行に出力してください。 最後に改行してください。

サンプル

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

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

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

サンプル3
入力
4000 4000
出力
622937044

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

サンプル4 (evil ケース限定)
入力
100000 1000000000
出力
825008896

このテストケースは、AC判定には関係のないevilケースのみに含まれている物です。

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