問題一覧 > 通常問題

No.1388 Less than K

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 8
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
3 ProblemId : 5565 / 出題時の順位表
問題文最終更新日: 2021-02-08 08:53:37

問題文

縦に$\ H\ $個、横に$\ W\ $個のマス目状に区切られた全部で$\ HW\ $個の区画からなる都市があります。

上から$\ i\ $番目、左から$\ j\ $番目の区画を$\ (i,j)\ $とします。また、二つの区画$\ A,B\ $に対し、二区画間の距離を以下のように定義します。

  • 区画$\ A\ $を$\ (p,q)\ $,区画$\ B\ $を$\ (r,s)\ $とした時、区画$\ A\ $と区画$\ B\ $の二区画間の距離は$\ |p-r|+|q-s|$

今ミツバチ君とミタルシ君は共に$\ (1,1)\ $におり、下か右に隣接する区画を選んで同時かつ同速度で移動することを繰り返し、$\ (H,W)\ $を目指します。(二人が違う移動方向を選んでも構いません。)
この時、二人のいる二区画間の距離が常に$\ K\ $以下となるような二人の移動経路の通り数はいくつでしょうか。

答えは非常に大きくなる可能性があるので、$\ 998244353\ $で割った余りを求めてください。

ただし、二つの二人の移動経路が異なるとは以下のことを指します。

  • 移動経路の$\ i\ $番目の区画について、「ミツバチ君の存在する区画が同じ かつ ミタルシ君の存在する区画が同じ」でないような整数$\ i\ $が存在する

入力

$H\ W\ K$

  • $ 2 \leq H,W \leq 2 \times 10^5$
  • $ 0 \leq K \leq H+W-2$
  • 入力は全て整数

出力

二人の移動経路としてありえる通り数を$\ 998244353\ $で割った余りを出力してください。
最後に改行してください。

サンプル

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

例えば、以下のような移動経路は条件を満たします。

ミツバチ君:$\ (1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (3,2) \rightarrow (3,3)$
ミタルシ君:$\ (1,1) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (3,2) \rightarrow (3,3)$
この時、二人のいる二区画間の距離は以下のように変化します。
$0 \rightarrow 2 \rightarrow 2 \rightarrow 0 \rightarrow 0$

サンプル2
入力
10 10 0
出力
48620

この場合、ミツバチ君とミタルシ君が同じ移動経路を通る必要があります。

サンプル3
入力
314 1592 653
出力
13839116

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

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