No.2257 Swim and Sleep
タグ : / 解いたユーザー数 6
作問者 :
noya2
/ テスター :
Nachia
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$.
R : When a whale is at the coordinate $(x,y)$, it moves to $(x+t,y)$ after $t$ seconds.
L : When a whale is at the coordinate $(x,y)$, it moves to $(x-t,y)$ after $t$ seconds.
U : When a whale is at the coordinate $(x,y)$, it moves to $(x,y+t)$ after $t$ seconds.
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
RLUD $(1\le i\le K)$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。