問題一覧 > 通常問題

No.2257 Swim and Sleep

レベル : / AI推定難易度 : 3300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 6
作問者 : noya2 / テスター : shobonvip 👑 Nachia kaichou243
お気に入りにしたユーザー ProblemId : 9252 / 自分の提出
問題文最終更新日: 2023-03-24 21:54:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 382 (順位表) の他の問題:

Problem Statement

$A\times B$ whales have gathered in a $2$-dimensional toroidal sea.

Coordinates on the torus are denoted by $(x,y)$. The $2$ coordinates $(x_1,y_1),\ (x_2,y_2)$ are considered the same if and only if $x_1-x_2,y_1-y_2$ are integer multiples of $A,B$, respectively.

At time $t=0$, for every integer pair $(x,y)$ satisfying $0\le x\lt A, 0\le y\lt B$, $1$ whale is resting at the coordinate $(x,y)$.

Every whale wants to sleep while swimming, but a safe plan must be made so that no collisions occur.

Each whale is assigned a swimming direction, which is one of the following $4$ options. The correspondence between directions and movement is as follows. These hold for any positive real number $t$.

  • Direction R : When a whale is at the coordinate $(x,y)$, it moves to $(x+t,y)$ after $t$ seconds.
  • Direction L : When a whale is at the coordinate $(x,y)$, it moves to $(x-t,y)$ after $t$ seconds.
  • Direction U : When a whale is at the coordinate $(x,y)$, it moves to $(x,y+t)$ after $t$ seconds.
  • Direction D : When a whale is at the coordinate $(x,y)$, it moves to $(x,y-t)$ after $t$ seconds.
  • After the whales all start swimming simultaneously at $t=0$, no collision may ever occur within $10^{100}$ seconds. Here, a collision means that different whales move to the same coordinate at the same time.

    Among the $A\times B$ whales, the directions of $K$ whales have already been decided. The $i$-th of them is resting at $(x_i,y_i)$, and its direction is $d_i$. Find the number of ways to assign one of the $4$ directions to each of the remaining $A\times B-K$ whales, modulo $998244353$.

    For $1$ input, solve each of the $T$ cases.

    Constraints

  • $T,A,B,K,x_i,y_i$ are integers
  • $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$ is one of RLUD $(1\le i\le K)$
  • $(x_i,y_i)\neq (x_j,y_j)\ (i\neq j)$
  • Input

    The input is given from standard input in the following format. Here, $\mathrm{test}_i$ denotes the $i$-th test case.

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

    Each test case is given in the following format.

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

    Output

    Find the number of ways to assign one of the $4$ directions to the $A\times B-K$ whales whose directions are not decided, modulo $998244353$.

    Print a newline after every $1$ test case.

    Sample

    Sample 1
    Input
    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
    Output
    6
    2
    0
    417706019

    For the $1$st test case, the possible ways to assign directions to the whales at $(0,0),(1,0)$ are the following $6$: RR, LL, UU, DD, DU, UD .

    For the $2$nd test case, the direction that can be assigned to the whale at $(0,1)$ is either R L. Assigning U causes a collision after $1$ second, and assigning D causes a collision after $0.5$ seconds.

    For the $3$rd test case, there are cases where no assignment satisfies the condition.

    Note that you should output the remainder when divided by $998244353$.

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