結果

問題 No.3635 Probability trip
コンテスト
ユーザー 回転
提出日時 2026-08-23 14:27:36
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 334 ms / 2,000 ms
+ 855µs
コード長 3,379 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,228 ms
コンパイル使用メモリ 96,228 KB
実行使用メモリ 93,440 KB
最終ジャッジ日時 2026-08-23 14:27:53
合計ジャッジ時間 13,759 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from typing import Callable, TypeVar
T = TypeVar("T")

class MatrixCalculator:
    plus: Callable[[T, T], T]
    e_plus: T
    times: Callable[[T, T], T]
    e_times: T

    def __init__(
        self,
        plus: Callable[[T, T], T],
        e_plus: T,
        times: Callable[[T, T], T],
        e_times: T,
    ):
        self.plus = plus
        self.e_plus = e_plus
        self.times = times
        self.e_times = e_times

    def add(self, A: list[list[T]], B: list[list[T]]) -> list[list[T]]:
        """A + B を計算する"""
        h_a, w_a = len(A), len(A[0])
        h_b, w_b = len(B), len(B[0])

        assert h_a == h_b and w_a == w_b

        res = self._zero(h_a, w_a)
        
        # 関数呼び出しのオーバーヘッドを削減
        plus = self.plus

        for i in range(h_a):
            for j in range(w_a):
                # 修正: 組み込みの + ではなく self.plus を使用する
                res[i][j] = plus(A[i][j], B[i][j])

        return res

    def mul(self, A: list[list[T]], B: list[list[T]]) -> list[list[T]]:
        """A * B を計算する"""
        h_a, w_a = len(A), len(A[0])
        h_b, w_b = len(B), len(B[0])

        assert w_a == h_b

        res = self._zero(h_a, w_b)

        # ローカル変数に退避して関数呼び出しを高速化
        plus = self.plus
        times = self.times
        e_plus = self.e_plus

        # i-k-j ループに変更し、内側のループを軽くする
        for i in range(h_a):
            row_res = res[i]
            row_a = A[i]
            for k in range(w_a):
                val_a = row_a[k]
                # A[i][k] が加法単位元（0など）なら掛け算しても0なのでスキップ (定数倍高速化)
                if val_a == e_plus:
                    continue
                row_b = B[k]
                for j in range(w_b):
                    row_res[j] = plus(row_res[j], times(val_a, row_b[j]))

        return res

    def power(self, A: list[list[T]], e: int) -> list[list[T]]:
        """A**e を計算する"""
        n, m = len(A), len(A[0])

        assert n == m

        res = self._identity(n)
        base = A

        # 下からの繰り返し二乗法（簡素で書きやすい定石）
        while e > 0:
            if e & 1:
                res = self.mul(res, base)
            base = self.mul(base, base)
            e >>= 1

        return res

    def _zero(self, h: int, w: int):
        """h 行 w 列の零行列"""
        return [[self.e_plus for _ in range(w)] for _ in range(h)]

    def _identity(self, n: int):
        """n 次単位行列"""
        return [
            [self.e_times if i == j else self.e_plus for j in range(n)]
            for i in range(n)
        ]

MOD = 998244353
N,M = list(map(int,input().split()))
edge = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    u,v = list(map(int,input().split()))
    u -= 1;v -= 1
    edge[u][v] = 1
    edge[v][u] = 1
for i in range(N):
    length = len([j for j in edge[i] if j != 0])
    inv = pow(length,-1,MOD)
    for j in range(N):edge[i][j] *= inv
S,T,A,B = list(map(lambda x:int(x)-1,input().split()))

MC = MatrixCalculator(lambda x,y:(x+y) % MOD,0,lambda x,y:x*y % MOD,1)
ALL = MC.power(edge,S)[0][A]

v = MC.power(edge,T)[0][B]
vv = MC.power(edge,S-T)[B][A]

print(v * vv * pow(ALL,-1,MOD) % MOD)
0