#1178224 (C++23) No.3635 Probability trip

• 問題: No.3635 Probability trip
• ユーザー: triangle_coder
• 提出日時: 2026-08-21 22:38:25
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 86 ms / 2,000 ms
• コード長: 3,631 bytes
• コンパイル時間: 4,701 ms
• コンパイル使用メモリ: 388,300 KB
• 実行使用メモリ: 9,408 KB
• 最終ジャッジ日時: 2026-08-21 22:38:40
• 合計ジャッジ時間: 8,451 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_0

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

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
using namespace std;
using namespace atcoder;
typedef pair<ll,ll> pll;
ll p = 998244353;
ll INF = 2000000000000000010;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

void yn(bool a){
  if(a){
    cout << "Yes" <<endl;
  }
  else{
    cout << "No" << endl;
  }
}

ll mex(const vector<ll>& a){
  ll n = (ll)a.size();
  vector<int> b(n+1,0);
  for(ll i = 0;i<n;i++){
    if(a[i] < n && a[i] >= 0){
      b[a[i]]++;
    }
  }
  for(ll i = 0;i<n+1;i++){
    if(b[i] == 0){
      return i;
    }
  }
  return 0;
}

vector<ll> two(64,1);
void init() {
    std::cout << std::fixed << std::setprecision(10);
    for(ll i = 1;i<64;i++){
      two.at(i) = two.at(i-1)*2;
    }
}


vector<vector<ll>> vec_seki(const vector<vector<ll>>& a,const vector<vector<ll>>& b,ll p){
  if(a.size() == 0){
    return {};
  }
  assert(a[0].size() == b.size());
  assert(p != 0);
  vector<vector<ll>> ans(a.size(),vector<ll>(b[0].size(),0));
  for(ll i = 0;i<(ll)a.size();i++){
    for(ll k = 0;k<(ll)a[0].size();k++){
      for(ll j = 0;j<(ll)b[0].size();j++){
        ans[i][j] = (ans[i][j]+a[i][k] * b[k][j])%p;
      }
    }
  }
  return ans;
}



template<class T>
vector<pair<T,ll>> runlength(const vector<T>& vec){
  vector<pair<T,ll>> ret;
  if(vec.size()==0){
    return ret;
  }
  pair<T,ll> temp;
  temp.first = vec[0];
  temp.second = 1;
  ret.push_back(temp);
  T mae = vec[0];
  for(ll i = 1;i<(ll)vec.size();i++){
    if(vec[i] != mae){
      temp.first = vec[i];
      temp.second = 1;
      ret.push_back(temp);
      mae = vec[i];
    }
    else{
      ret[ret.size()-1].second++;
    }
  }
  return ret;
}

ll bintoll(const string& S){
  ll ret = 0;
  ll n = (ll)S.size();
  for(ll i = 0;i<n;i++){
    if(S[i] == '1'){
      ret += 1LL<<(n-1-i);
    }
  }
  return ret;
}

string lltobin(const ll N){
    if(N==0) return "0";
    string S;
    ll Nco = N;
    while(Nco!= 0){
        S += char('0' + (Nco&1));
        Nco >>= 1;
    }
    reverse(S.begin(),S.end());
    return S;
}


int main() {
  init();

  ll N,M;
  cin >> N>>M;
  vector<vector<ll>> A(N,vector<ll>(N,0));
  vector<vector<ll>> B(N,vector<ll>(N,0));
  vector<vector<ll>> ans(N,vector<ll>(N,0));
  vector<vector<ll>> ans2(N,vector<ll>(N,0));
  vector<vector<ll>> ans3(N,vector<ll>(N,0));
  vector<ll> num(N,0);
  for(ll i = 0;i<N;i++){
    ans[i][i] = 1;
    ans2[i][i] = 1;
    ans3[i][i] = 1;
  }
  for(ll i = 0;i<M;i++){
    ll u,v;
    cin >> u >> v;
    u--;v--;
    A[u][v]=1;
    A[v][u]=1;
    num[u]++;
    num[v]++;
  }
  ll S,T,a,b;
  cin >> S >> T >> a >> b;a--;b--;
  for(ll i = 0;i<N;i++){
    for(ll j = 0;j<N;j++){
      if(A[i][j] == 1){
        B[i][j] = inv_mod(num[i],p);
      }
    }
  }
  vector<vector<vector<ll>>> dp(60,vector<vector<ll>>(N,vector<ll>(N,0)));
  vector<vector<vector<ll>>> dp2(60,vector<vector<ll>>(N,vector<ll>(N,0)));
  dp[0] =A;
  dp2[0]=B;
  for(ll i = 0;i<59;i++){
    dp[i+1] = vec_seki(dp[i],dp[i],p);
    dp2[i+1] = vec_seki(dp2[i],dp2[i],p);
  }
  S--;T--;
  for(ll i = 0;i<60;i++){
    if(S&(1LL<<i))ans = vec_seki(ans,dp2[i],p);
    if(T&(1LL<<i))ans2 = vec_seki(ans2,dp2[i],p);
    if((S-T)&(1LL<<i))ans3 = vec_seki(ans3,dp2[i],p);
  }
  ll kota = 1;
  kota = kota * inv_mod(ans[0][a],p);
  kota%=p;
  kota = kota * ans2[0][b];
  kota%=p;
  kota = kota * ans3[b][a];
  kota%=p;
  cout << kota << endl;
  
  // ここにプログラムを追記
}