結果

問題 No.3635 Probability trip
コンテスト
ユーザー 👑 ssmbc2929_bartok
提出日時 2026-07-09 13:47:07
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 34 ms / 2,000 ms
+ 453µs
コード長 1,539 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,313 ms
コンパイル使用メモリ 345,284 KB
実行使用メモリ 7,336 KB
最終ジャッジ日時 2026-08-21 20:55:56
合計ジャッジ時間 5,154 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
using Matrix = vector<vector<mint>>;

Matrix operator*(const Matrix& A, const Matrix& B) {
    int n = A.size();
    Matrix C(n, vector<mint>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            for (int j = 0; j < n; j++)
                C[i][j] += A[i][k] * B[k][j];
    return C;
}

Matrix matpow(Matrix A, ll n) {
    int sz = A.size();
    Matrix res(sz, vector<mint>(sz, 0));
    for (int i = 0; i < sz; i++) res[i][i] = 1;
    while (n > 0) {
        if (n & 1) res = res * A;
        A = A * A;
        n >>= 1;
    }
    return res;
}

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<pair<int,int>> edges(M);
    vector<int> deg(N, 0);
    for (auto& [u, v] : edges) {
        cin >> u >> v;
        u--; v--;
        deg[u]++; deg[v]++;
    }
    
    int A, B;
    ll S, T;
    cin >> S >> T >> A >> B;
    A--; B--;
    
    // 遷移確率行列
    Matrix P(N, vector<mint>(N, 0));
    for (auto [u, v] : edges) {
        P[u][v] = mint(1) / deg[u];
        P[v][u] = mint(1) / deg[v];
    }
    
    // P^(T-1) と P^(S-T) を計算
    Matrix PT = matpow(P, T - 1);
    Matrix PST = matpow(P, S - T);
    
    // P^(S-1) = P^(T-1) * P^(S-T)
    Matrix PS = PT * PST;
    
    mint numerator = PT[0][B] * PST[B][A];
    mint denominator = PS[0][A];
    mint ans = numerator / denominator;
    
    cout << ans.val() << endl;
}
0