結果

問題 No.3315 FPS Game
コンテスト
ユーザー tau1235
提出日時 2025-10-24 23:19:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 246 ms / 3,250 ms
コード長 1,564 bytes
コンパイル時間 5,588 ms
コンパイル使用メモリ 335,064 KB
実行使用メモリ 26,596 KB
最終ジャッジ日時 2025-10-24 23:19:54
合計ジャッジ時間 10,162 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;

using mint=atcoder::modint998244353;
vector<mint> fact,ifact;
void factcalc(int n){
  fact.assign(n+1,0);
  ifact.assign(n+1,0);
  fact[0]=1;ifact[0]=1;
  for (int i=1;i<=n;i++){
    fact[i]=fact[i-1]*i;
    ifact[i]=ifact[i-1]*mint(i).inv();
  }
}
mint comb(int n,int k){
  if (n<k||n<0||k<0) return 0;
  return fact[n]*ifact[k]*ifact[n-k];
}

int main(){
  int n,s,t;
  cin>>n>>s>>t;
  s--;t--;
  factcalc(n+10);
  vector<vector<int>> g(n);
  vector<pair<int,int>> edge(n-1);
  for (int i=0;i<n-1;i++){
    int u,v;
    cin>>u>>v;
    u--;v--;
    g[u].push_back(i);
    g[v].push_back(i);
    edge[i]={u,v};
  }
  vector<int> vec;
  auto dfs=[&](auto dfs,int v,int par)-> bool {
    if (par==t) return true;
    for (int i:g[v]){
      if (i==par) continue;
      auto [u1,u2]=edge[i];
      int u=u1^u2^v;
      if (dfs(dfs,u,i)){
        int c=(int)g[v].size()-2;
        if (c>=0) vec.push_back(c);
        return true;
      }
    }
    return false;
  };
  auto [v1,v2]=edge[s];
  dfs(dfs,v1,s);
  dfs(dfs,v2,s);
  deque<pair<int,vector<mint>>> q;
  for (int c:vec){
    vector<mint> f(c+2);
    for (int i=1;i<=c+1;i++) f[i]=comb(c,i-1)*fact[i-1];
    q.push_front({c+1,f});
  }
  while (q.size()>1){
    auto [c1,f1]=q.front();
    q.pop_front();
    auto [c2,f2]=q.front();
    q.pop_front();
    q.push_back({c1+c2,atcoder::convolution(f1,f2)});
  }
  auto [c,f]=q.front();
  for (int k=0;k<n;k++){
    if (k>c) cout<<0<<" \n"[k==n-1];
    else cout<<f[k].val()<<" \n"[k==n-1];
  }
}
0