#1178264 (C++17) No.3635 Probability trip

• 問題: No.3635 Probability trip
• ユーザー: achapi
• 提出日時: 2026-08-21 23:03:29
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 54 ms / 2,000 ms
• コード長: 3,349 bytes
• コンパイル時間: 3,100 ms
• コンパイル使用メモリ: 282,028 KB
• 実行使用メモリ: 9,408 KB
• 最終ジャッジ日時: 2026-08-21 23:03:37
• 合計ジャッジ時間: 6,209 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_1

ファイルパターン	結果
sample	AC * 3
other	AC * 43

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using mint = atcoder::modint998244353;
using namespace std;
template<class T> struct Matrix{
	vector<vector<T>> A;
	Matrix(){}
	Matrix(int n, int m): A(n, vector<T>(m, 0)){}
	Matrix(int n): A(n, vector<T>(n, 0)){}
	int height() const{
		return A.size();
	}
	int width() const{
		return A[0].size();
	}
	const vector<T>& operator[](int k) const{
		return A[k];
	}
	vector<T>& operator[](int k){
		return A[k];
	}
	static Matrix I(int n){
		Matrix res(n);
		for (int i = 0; i < n; i++) res[i][i] = 1;
		return res;
	}
	Matrix& operator+=(const Matrix& B){
		int n = height(), m = width();
		assert(n == B.height() && m == B.width());
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){
				A[i][j] += B[i][j];
			}
		}
		return *this;
	}
	Matrix& operator-=(const Matrix& B){
		int n = height(), m = width();
		assert(n == B.height() && m == B.width());
		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++){
				A[i][j] -= B[i][j];
			}
		}
		return *this;
	}
	Matrix& operator*=(const Matrix& B){
		int n = height(), m = B.width(), p = width();
		assert(p == B.height());
		vector<vector<T>> C(n, vector<T>(m, 0));
		for (int i = 0; i < n; i++){
			for (int k = 0; k < p; k++){
				for (int j = 0; j < m; j++){
					C[i][j] += A[i][k] * B[k][j];
				}
			}
		}
		A.swap(C);
		return *this;
	}
	Matrix& operator^=(long long k){
		Matrix res = I(height());
		Matrix x = *this;
		while(k){
			if (k & 1) res *= x;
			x *= x;
			k >>= 1;
		}
		A.swap(res.A);
		return *this;
	}
	Matrix operator+(const Matrix& B) const{
		Matrix res = *this;
		return res += B;
	}
	Matrix operator-(const Matrix& B) const{
		Matrix res = *this;
		return res -= B;
	}
	Matrix operator*(const Matrix& B) const{
		Matrix res = *this;
		return res *= B;
	}
	Matrix operator^(long long k) const{
		Matrix res = *this;
		return res ^= k;
	}
	friend ostream& operator<<(ostream& os, const Matrix& M){
		for (int i = 0; i < M.height(); i++){
			os << "[";
			for (int j = 0; j < M.width(); j++){
				os << M[i][j].val() << (j + 1 == M.width() ? "]\n" : ",");
			}
		}
		return os;
	}
	T determinant() const{
		Matrix B = *this;
		assert(height() == width());
		T res = 1;
		for (int i = 0; i < width(); i++){
			int p = -1;
			for (int j = i; j < width(); j++){
				if (B[j][i] != 0){
					p = j;
					break;
				}
			}
			if (p == -1) return 0;
			if (i != p){
				swap(B[i], B[p]);
				res *= -1;
			}
			res *= B[i][i];
			T v = B[i][i];
			for (int j = 0; j < width(); j++){
				B[i][j] /= v;
			}
			for (int j = i + 1; j < width(); j++){
				T c = B[j][i];
				for (int k = 0; k < width(); k++){
					B[j][k] -= B[i][k] * c;
				}
			}
		}
		return res;
	}
};
int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vector<vector<int>> E(N);
	for (int i = 0; i < M; i++){
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	long long S, T;
	int A, B;
	cin >> S >> T >> A >> B;
	A--;
	B--;
	Matrix<mint> G(N, N);
	for (int i = 0; i < N; i++){
		for (int j : E[i]){
			G[i][j] = mint(1) / E[i].size();
		}
	}
	Matrix<mint> a(1, N);
	a[0][0] = 1;
	a *= G ^ (S - 1);
	Matrix<mint> b(1, N);
	b[0][B] = 1;
	b *= G ^ (S - T);
	Matrix<mint> c(1, N);
	c[0][0] = 1;
	c *= G ^ (T - 1);
	cout << (c[0][B] * b[0][A] / a[0][A]).val() << endl;
}