G. 抵抗器 - TUATPC 2025 Spring

G - 抵抗器

問題文

抵抗器が接続された回路図が文法 $G$ によって生成されます。

文法 $G$ を以下に示します。

終端記号は o, -, ^v^v^v, +, |, および空白文字（ASCII 32）からなる。
非終端記号は <回路>, <直列抵抗>, <並列抵抗>, <始点>, <終点>, <抵抗> からなる。
生成規則は図 1 に示す。（参考 : BNF 記法）

図 1 : 生成規則

開始記号は <回路> である。開始記号に非終端記号が無くなるまで生成規則を適用する。
<回路> を除く非終端記号および終端記号は高さと幅を持つ $2$ 次元の矩形の文字領域である。<回路> は $2$ 次元の文字領域である。
全ての終端記号の高さは $1$ であり、幅は文字列の長さである。
ある $2$ つの記号 $\alpha, \beta$ をこの順に左から連結するとは、$\alpha$ の最も右上の位置と $\beta$ の最も左上の位置を連結し、空白文字（ASCII 32）を挿入することで矩形領域にすることを指す。具体例を図 2 に示す。
- 同様に $3$ つの記号 $\alpha, \beta, \gamma$ をこの順に左から連結するとは、$\alpha$ の最も右上の位置と $\beta$ の最も左上の位置を連結し、さらに $\beta$ の最も右上の位置と $\gamma$ の左上の位置を連結し、最後に空白文字（ASCII 32）を挿入することで矩形領域にすることを指す。

図 2 : $2$ つの記号の連結例

<回路> は <始点>, <直列回路>, <終点> をこの順に左から連結したものから、その各行の末尾の空白文字 (ASCII 32) を全て削除したものに置換される。<回路> の高さは置換後の各記号の高さの最大値であり、幅は置換後の各記号の幅の和である。
<直列抵抗> は <並列抵抗> に置換されるか、<並列抵抗>, ---, <直列抵抗> をこの順に左から連結したものに置換される。<直列抵抗> の高さは置換後の各記号の高さの最大値であり、幅は置換後の各記号の幅の和である。
<並列抵抗> は <抵抗> に置換されるか、$2$ つ以上の <直列抵抗> を +, |, - を使って上下に連結したものに置換される。前者の場合、<並列抵抗> の高さと幅は <抵抗> の高さと幅に一致する。後者の場合の連結方法と高さと幅は以下のようになる。
- <並列抵抗> から置換される <直列抵抗> の数を $n$、上から $i$ 番目の <直列抵抗> の高さと幅をそれぞれ $H_i, W_i$ とする。
- 上から $i$ 番目の <直列抵抗> $\alpha_i$ について、+---, $\alpha_i$, --- をこの順に左から連結する。さらに、右側の --- の右端からハイフン - を延長するように $\left( \underset{1 \leq i \leq n}{\max}W_i - W_i \right)$ 個の - を連結する。最後に末尾に + を連結する。
- $1$ 以上 $n - 1$ 以下の $i$ について、上から $i$ 番目の <直列抵抗> と上から $(i + 1)$ 番目の <直列抵抗> の間の行について、上から $i$ 番目の <直列抵抗> に接続された両端の + の直下に | を $H_i$ 個連結させる。
- この <並列抵抗> の高さは $\sum_{i=1}^{n} H_i + n - 1$ であり、幅は $\underset{1 \leq i \leq n}{\max}W_i + 8$ である。
- 上記の高さと幅の矩形領域のうち、非終端記号に置換されていない位置の文字は空白文字 (ASCII 32) に置換する。
- 具体例を図 3 に示す。入力例も参考にせよ。

図 3 : <並列抵抗> の置換例

さて、文法 $G$ によって生成される文字列が示す始点と終点の間の合成抵抗とは、開始記号 <回路> が生成する <直列抵抗> の合成抵抗です。

<直列抵抗> の合成抵抗は <並列抵抗> のみに置き換えられる場合は、<並列抵抗> の合成抵抗です。そうでないとき、<直列抵抗> から置換された <並列抵抗> と <直列抵抗> の合成抵抗の値をそれぞれ $R_1, R_2$ とすると、合成抵抗は $R_1 + R_2$ となります。

<並列抵抗> の合成抵抗は、 <抵抗> のみに置き換えられる場合の合成抵抗は $1$ です。そうでないとき、<並列抵抗> から置換された $n$ 個の <直列抵抗> の合成抵抗の値をそれぞれ $R_1, R_2, \dots, R_n$ とすると、合成抵抗は $\displaystyle \frac{1}{\frac{1}{R_1} + \frac{1}{R_2} + \cdots + \frac{1}{R_n}}$ です。

文法 $G$ に従って $N$ 行からなる文字列 $S$ が与えられます。$S$ が示す始点と終点の間の合成抵抗を $\mathrm{mod}\ 998244353$ で求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

注記

$\mathrm{mod}\ 998244353$ で求めるとは

求める合成抵抗は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P, Q$ を用いて $\frac{P}{Q}$ と表したとき、$R \times Q \equiv P \pmod{998244353}$ かつ $0 \leq R < 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。

制約

$ 1 \leq T \leq 100{,}000 $
$N, T$ は整数
$S$ は文法 $G$ に従って得られる文字列
$S$ に含まれる ^v^v^v の数は $ 30 $ 個以下
$i$ 番目のテストケースの $N$ を $N_i$ とし、$S$ の $j$ 行目の文字列の長さを $L_{i,j}$ として、$\displaystyle\sum_{1 \leq i \leq T, 1 \leq j \leq N_i} L_{i,j} \leq 1{,}500{,}000$

部分点

この問題に部分点は存在しません。

入力

入力は以下の形式で標準入力から与えられます。

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

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

$N$
$S_1$
$\vdots$
$S_N$

出力

標準出力に $T$ 行出力してください。

$i$ 行目には $\mathrm{case}_i$ に対する答えを標準出力に出力してください。

入力例 1

4
1
o---^v^v^v---^v^v^v---o
3
o---+---^v^v^v---+---o
    |            |
    +---^v^v^v---+
9
o---+---^v^v^v-----------+---^v^v^v---o
    |                    |
    +---+---^v^v^v---+---+
    |   |            |   |
    |   +---^v^v^v---+   |
    |                    |
    +---^v^v^v-----------+
    |                    |
    +---^v^v^v-----------+
21
o---+---^v^v^v---------------------------------------------------------------------------+---o
    |                                                                                    |
    +---+---^v^v^v-------------------------------------------------------------------+---+
        |                                                                            |
        +---+---^v^v^v-----------------------------------------------------------+---+
            |                                                                    |
            +---+---^v^v^v---------------------------------------------------+---+
                |                                                            |
                +---+---^v^v^v-------------------------------------------+---+
                    |                                                    |
                    +---+---^v^v^v-----------------------------------+---+
                        |                                            |
                        +---+---^v^v^v---------------------------+---+
                            |                                    |
                            +---+---^v^v^v-------------------+---+
                                |                            |
                                +---+---^v^v^v-----------+---+
                                    |                    |
                                    +---+---^v^v^v---+---+
                                        |            |
                                        +---^v^v^v---+

出力例 1

$\mathrm{case}_1$ について

$2$ つの抵抗が直列に繋がっているため、合成抵抗は $1 + 1 = 2$ です。

よって、出力するべき値は $2$ です。

$\mathrm{case}_2$ について

$2$ つの抵抗が並列に繋がっているため、合成抵抗は $\frac{1}{\frac{1}{1} + \frac{1}{1}} = \frac{1}{2}$ です。

よって、出力するべき値は $499{,}122{,}177$ です。

$\mathrm{case}_3$ について

与えられた回路図を一般的な電気用図記号で表すと以下のようになります。

具体回路

この回路の合成抵抗は $\frac{6}{5}$ になるので、出力するべき値は $598{,}946{,}613$ です。

提出

ソースファイルを選択