結果

問題 No.3635 Probability trip
コンテスト
ユーザー kidodesu
提出日時 2026-08-21 22:04:07
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,178 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 235 ms
コンパイル使用メモリ 96,100 KB
実行使用メモリ 93,520 KB
最終ジャッジ日時 2026-08-21 22:04:21
合計ジャッジ時間 8,410 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 23 RE * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

mod = 998244353
def main():
    n, m = list(map(int, input().split()))
    node = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(lambda x: int(x)-1, input().split()))
        node[u].append(v)
        node[v].append(u)
    s, t, a, b = list(map(lambda x: int(x)-1, input().split()))
    def cal(t, s):
        dp = [0] * n
        dp[s] = 1
        A = [[0 for x in range(n)] for y in range(n)]
        for u in range(n):
            for v in node[u]:
                A[u][v] = pow(len(node[u]), -1, mod)
        while t:
            if t & 1:
                ndp = [0] * n
                for u in range(n):
                    for v in range(n):
                        ndp[v] = (ndp[v] + dp[u]*A[u][v]) % mod
                dp = ndp
            NA = [[0 for _ in range(n)] for _ in range(n)]
            for u in range(n):
                for w in range(n):
                    for v in range(n):
                        NA[u][v] = (NA[u][v] + A[u][w]*A[w][v]) % mod
            A = NA
            t //= 2
        return dp
    ans1 = cal(s, 0)[b]
    ans0 = cal(t, 0)[a] * cal(s-t, a)[b] % mod
    return ans0 * pow(ans1, -1, mod) % mod
print(main())
0