問題一覧 > 通常問題

No.2409 Strange Werewolves

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 136
作問者 : AngrySadEightAngrySadEight / テスター : hamamuhamamu 遭難者遭難者
2 ProblemId : 9874 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-31 01:05:31

問題文

$X$ 人の人間と $Y$ 匹の狼がおり，全ての人間と狼は互いに区別できます．これから，人間と狼との間で，会議が開かれます．

会議は，次のような流れで行われます．

  • まだ追放されていない会議参加者の中から人間 $1$ 人または狼 $1$ 匹を選び，追放する．追放された人間，および狼は，以後の会議には参加できなくなる．
  • これを，人間または狼のどちらかが全員追放されるまで繰り返す．
  • 人間または狼のどちらかが全員追放された時点で会議は終了となる．

会議が終了したとき，まだ追放されていない人間は $Z$ 人であり，まだ追放されていない狼は $W$ 匹でした．ここで，$Z$ と $W$ のどちらか一方は $0$ です．このとき，追放のされ方の総数を $998244353$ で割った余りを求めてください．

なお，追放のされ方は，ある $i$ が存在して，$i$ 回目に追放された人間または狼が互いに異なる場合に区別されます．

制約

  • 入力はすべて整数である．
  • $1 \leq X, Y \leq 3 \times 10^5$
  • $0 \leq Z, W \leq 3 \times 10^5$
  • $Z \leq X$
  • $W \leq Y$
  • $Z = 0$ または $W = 0$
  • $(Z, W) \neq (0, 0)$

入力

入力は以下の形式で標準入力から与えられる．

$X$ $Y$ $Z$ $W$

出力

答えを出力せよ．

サンプル

サンプル1
入力
2 2 1 0
出力
8

便宜上，人間を人 $1,2$，狼を狼 $1,2$ と区別すると，次の $8$ 通りのケースが考えられます．

  • 人 $1$ →狼 $1$ →狼 $2$ の順に追放される．
  • 人 $1$ →狼 $2$ →狼 $1$ の順に追放される．
  • 人 $2$ →狼 $1$ →狼 $2$ の順に追放される．
  • 人 $2$ →狼 $2$ →狼 $1$ の順に追放される．
  • 狼 $1$ →人 $1$ →狼 $2$ の順に追放される．
  • 狼 $1$ →人 $2$ →狼 $2$ の順に追放される．
  • 狼 $2$ →人 $1$ →狼 $1$ の順に追放される．
  • 狼 $2$ →人 $2$ →狼 $1$ の順に追放される．

サンプル2
入力
2013 8 12 0
出力
212512743

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

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