J - Strangely Familiar...
問題文
$H \times W$の $2$ 次元グリッドが与えられ、このグリッド上を魚が泳ぎ回ります。初めグリッドには 0 から 9 の数字、/、\、;のいずれかが書いてあります。上から $i$ 番目、左から $j$ 番目のマスを $(i,j)$ と表すことにし、初期位置 $(x_i, y_i)$ がクエリとして $Q$ 個与えられます。各クエリについて次の問題を解いて下さい。
魚は最初右を向いており初期位置にいます。魚は次を繰り返します。
- 自分がいるマスに書いてあるのが
- 数字なら自身のスタックにその数字を追加します。
/なら上を向いているときは右、下を向いているときは左、左を向いているときは下、右を向いているときは上を向きます。\なら上を向いているときは左、下を向いているときは右、左を向いているときは上、右を向いているときは下を向きます。;なら以降移動をしません。
- 文字の処理を終えた後自分の向いている方向に $1$ マス進みます。グリッドの範囲を超えるときは反対側の端に向きを変えずにワープします。
この一連の処理を $1$ ステップと呼ぶ時、$10^{18}$ ステップ後の状態について次を考えます。
文字列 $S$ を空文字列で初期化しておきます。魚が停止した時この魚のスタックにある数字を前側から順に取り出し、$S$に右側から連結していきます。できた文字列を $10$ 進数の数字として見て、 $998244353$ で割った余りを求めて下さい。初期位置には数字が書いてあるので連結後の $S$ が空文字列になることはありません。
制約
- $H \times W \leq 10^5$
- $s_{i,j}$ は
0から9の数字、/、\、;のいずれかである。 - $s_{x_i, y_i}$ は
0から9の数字である。 - $1 \leq Q \leq 10^5$
- $1 \leq x_i \leq H$
- $1 \leq y_i \leq W$
入力
入力は以下の形式で標準入力から与えられる。
$H\ W$
$s_{1,1}\ s_{1,2}\ ... \ s_{1,W}$
$\vdots$
$s_{H,1}\ s_{H,2}\ ... \ s_{H,W}$
$Q$
$x_1\ y_1$
$\vdots$
$x_Q\ y_Q$
出力
答えを $Q$ 行に出力せよ。
3 6
12345\
6/789/
0\123;
2
1 1
2 1
235135025
26
どちらのクエリも ; が書いてあるマスに至るステップがあり、それ以降は魚は移動しません。
1行目は $32178954321$ を $998244353$ で割った余りである $235135025$ を出力します。
2行目は連結後の $S$ が 026 となるので、それを $10$ 進数として見た $26$ を $998244353$ で割った余りである $26$ を出力します。
3 3
/1\
234
\5/
3
2 3
1 2
3 2
220864560
847636536
41398292
$10^{18}$ ステップ後でも ; によって停止していない場合があります。
例えば1つ目のクエリでは、$(2,3)$ → $(2,1)$ → $(2,2)$ → $(2,3)$ を繰り返します。周期は $3$ ステップです。
2つ目のクエリでは、$(1,2)$ → $(1,3)$ → $(2,3)$ → $(3,3)$ → $(3,2)$ → $(3,1)$ → $(2,1)$ → $(1,1)$ → $(1,2)$ を繰り返します。周期は $8$ ステップです。連結後の $S$ は 2541 を $\frac{10^{18}}{8}$ 個連結したものになります。
3 6
012\34
5/6/78
9\01/2
3
1 1
1 3
3 4
761583075
698971231
900937400