問題一覧 > 通常問題

No.2257 Swim and Sleep

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 6
作問者 : noya2noya2 / テスター : shobonvipshobonvip kaichou243kaichou243 👑 NachiaNachia
1 ProblemId : 9252 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-24 21:54:07

問題文

$2$ 次元トーラスの海に $A\times B$ 頭のくじらが集まってきました。

トーラス上の座標を $(x,y)$ で表します。$2$ つの座標 $(x_1,y_1),\ (x_2,y_2)$ は、$x_1-x_2,y_1-y_2$ がそれぞれ $A,B$ の整数倍であるとき、またそのときに限り同じ座標とみなします。

時刻 $t=0$ において, $0\le x\lt A, 0\le y\lt B$ を満たすすべての整数組 $(x,y)$ に対して、 座標 $(x,y)$ に $1$ 頭のくじらが停まっています。

どのくじらも泳ぎながら眠りたいですが、衝突が起こらないように安全な計画を立てなければいけません。

各くじらの泳ぐ方向を次の $4$ 通りのいずれかに割り当てます。方向と泳ぎ方の対応は次のとおりです。 ただし、任意の正の実数 $t$ に対して成り立ちます。

  • 方向 R : くじらが座標 $(x,y)$ にいるとき、 $t$ 秒後に $(x+t,y)$ に移動する。
  • 方向 L : くじらが座標 $(x,y)$ にいるとき、 $t$ 秒後に $(x-t,y)$ に移動する。
  • 方向 U : くじらが座標 $(x,y)$ にいるとき、 $t$ 秒後に $(x,y+t)$ に移動する。
  • 方向 D : くじらが座標 $(x,y)$ にいるとき、 $t$ 秒後に $(x,y-t)$ に移動する。
  • $t=0$ にくじらたちが一斉に泳ぎ始めたのち、$10^{100}$ 秒以内に一度も衝突が起きてはいけません。 ただし、衝突が起こるとは、同時刻に同じ座標に異なるくじらが移動することを指します。

    $A\times B$ 頭のくじらのうち、$K$ 頭のくじらの方向は既に決まっています。そのうち $i$ 番目のくじらは $(x_i,y_i)$ に停まっており、方向は $d_i$ です。 残りの $A\times B-K$ 頭のくじらを $4$ 方向のいずれかに割り当てる方法の数を $998244353$ で割ったあまりを求めてください。

    $1$ つの入力につき、$T$ ケースについてそれぞれ解いてください。

    制約

  • $T,A,B,K,x_i,y_i$ は整数
  • $1\le T\le 100$
  • $1\le A,B\le 10^9$
  • $0\le K\le \min(A\times B,2\times 10^3)$
  • $0\le x_i\lt A\ (1\le i\le K)$
  • $0\le y_i\lt B\ (1\le i\le K)$
  • $d_i$ は RLUDのいずれか $(1\le i\le K)$
  • $(x_i,y_i)\neq (x_j,y_j)\ (i\neq j)$
  • 入力

    入力は以下の形式で標準入力から与えられる。ここで、$\mathrm{test}_i$ は $i$ 番目のテストケースを意味する。

    $T$
    $\mathrm{test}_1$
    $\mathrm{test}_2$
    $\quad\vdots$
    $\mathrm{test}_T$

    各テストケースは以下の形式で与えられる。

    $A$ $B$ $K$
    $x_1$ $y_1$ $d_1$
    $x_2$ $y_2$ $d_2$
    $\qquad\vdots$
    $x_K$ $y_K$ $d_K$

    出力

    方向が決まっていない $A\times B-K$ 頭のくじらを $4$ 方向のいずれかに割り当てる方法の数を $998244353$ で割ったあまりを求めてください。

    $1$ テストケースごとに改行してください。

    サンプル

    サンプル1
    入力
    4
    2 1 0
    2 2 3
    0 0 U
    1 0 L
    1 1 D
    100 100 2
    0 0 U
    0 99 D
    314 159 2
    65 35 L
    89 79 R
    出力
    6
    2
    0
    417706019

    $1$ つ目のテストケースについて、$(0,0),(1,0)$ のくじらの方向の割り当て方として考えられるのは RR, LL, UU, DD, DU, UD の $6$ 通りです。

    $2$ つ目のテストケースについて、$(0,1)$ のくじらに割り当てられる方向は R L のいずれかです。 U に割り当てると $1$ 秒後に、D に割り当てると $0.5$ 秒後に衝突が起こってしまいます。

    $3$ つ目のテストケースについて、どのような割り当て方をしても条件を満たさないような場合があります。

    $998244353$ で割ったあまりを出力することに気をつけてください。

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