結果
| 問題 |
No.3315 FPS Game
|
| コンテスト | |
| ユーザー |
 umimel
|
| 提出日時 | 2025-10-24 22:02:12 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 266 ms / 3,250 ms |
| コード長 | 9,718 bytes |
| コンパイル時間 | 4,330 ms |
| コンパイル使用メモリ | 243,116 KB |
| 実行使用メモリ | 36,764 KB |
| 最終ジャッジ日時 | 2025-10-24 22:02:22 |
| 合計ジャッジ時間 | 8,692 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
enum Mode {
FAST = 1,
NAIVE = -1,
};
template <class T, Mode mode = FAST>
struct FormalPowerSeries : std::vector<T> {
using std::vector<T>::vector;
using std::vector<T>::size;
using std::vector<T>::resize;
using F = FormalPowerSeries;
F &operator+=(const F &g) {
for(int i = 0; i < int(std::min((*this).size(), g.size())); i++) (*this)[i] += g[i];
return *this;
}
F &operator+=(const T &t) {
assert(int((*this).size()));
(*this)[0] += t;
return *this;
}
F &operator-=(const F &g) {
for(int i = 0; i < int(std::min((*this).size(), g.size())); i++) (*this)[i] -= g[i];
return *this;
}
F &operator-=(const T &t) {
assert(int((*this).size()));
(*this)[0] -= t;
return *this;
}
F &operator*=(const T &t) {
for(int i = 0; i < int((*this).size()); ++i) (*this)[i] *= t;
return *this;
}
F &operator/=(const T &t) {
T div = t.inv();
for(int i = 0; i < int((*this).size()); ++i) (*this)[i] *= div;
return *this;
}
F &operator>>=(const int sz) const {
assert(sz >= 0);
int n = (*this).size();
(*this).erase((*this).begin(), (*this).begin() + std::min(sz, n));
(*this).resize(n);
return *this;
}
F &operator<<=(const int sz) const {
assert(sz >= 0);
int n = (*this).size();
(*this).insert((*this).begin(), (*this).begin() + sz, 0);
(*this).resize(n);
return *this;
}
F &operator%=(const F &g) { return *this -= *this / g * g; }
F &operator=(const std::vector<T> &v) {
int n = (*this).size();
for(int i = 0; i < n; ++i) (*this)[i] = v[i];
return *this;
}
F operator-() const {
F ret = *this;
return ret * -1;
}
F &operator*=(const F &g) {
if(mode == FAST) {
int n = (*this).size();
auto tmp = atcoder::convolution(*this, g);
for(int i = 0; i < n; ++i) (*this)[i] = tmp[i];
return *this;
} else {
int n = (*this).size(), m = g.size();
for(int i = n - 1; i >= 0; --i) {
(*this)[i] *= g[0];
for(int j = 1; j < std::min(i + 1, m); j++)
(*this)[i] += (*this)[i - j] * g[j];
}
return *this;
}
}
F &operator/=(const F &g) {
if(mode == FAST) {
int n = (*this).size();
(*this) = atcoder::convolution(*this, g.inv());
return *this;
} else {
assert(g[0] != T(0));
T ig0 = g[0].inv();
int n = (*this).size(), m = g.size();
for(int i = 0; i < n; ++i) {
for(int j = 1; j < std::min(i + 1, m); ++j)
(*this)[i] -= (*this)[i - j] * g[j];
(*this)[i] *= ig0;
}
return *this;
}
}
F operator+(const F &g) const { return F(*this) += g; }
F operator+(const T &t) const { return F(*this) += t; }
F operator-(const F &g) const { return F(*this) -= g; }
F operator-(const T &t) const { return F(*this) -= t; }
F operator*(const F &g) const { return F(*this) *= g; }
F operator*(const T &t) const { return F(*this) *= t; }
F operator/(const F &g) const { return F(*this) /= g; }
F operator/(const T &t) const { return F(*this) /= t; }
F operator%(const F &g) const { return F(*this) %= g; }
T eval(const T &t) const {
int n = (*this).size();
T res = 0, tmp = 1;
for(int i = 0; i < n; ++i) res += (*this)[i] * tmp, tmp *= t;
return res;
}
F inv(int deg = -1) const {
int n = (*this).size();
assert(mode == FAST and n and (*this)[0] != 0);
if(deg == -1) deg = n;
assert(deg > 0);
F res{(*this)[0].inv()};
while(int(res.size()) < deg) {
int m = res.size();
F f((*this).begin(), (*this).begin() + std::min(n, m * 2)), r(res);
f.resize(m * 2), atcoder::internal::butterfly(f);
r.resize(m * 2), atcoder::internal::butterfly(r);
for(int i = 0; i < m * 2; ++i) f[i] *= r[i];
atcoder::internal::butterfly_inv(f);
f.erase(f.begin(), f.begin() + m);
f.resize(m * 2), atcoder::internal::butterfly(f);
for(int i = 0; i < m * 2; ++i) f[i] *= r[i];
atcoder::internal::butterfly_inv(f);
T iz = T(m * 2).inv();
iz *= -iz;
for(int i = 0; i < m; ++i) f[i] *= iz;
res.insert(res.end(), f.begin(), f.begin() + m);
}
res.resize(deg);
return res;
}
F &diff_inplace() {
int n = (*this).size();
for(int i = 1; i < n; ++i) (*this)[i - 1] = (*this)[i] * i;
(*this)[n - 1] = 0;
return *this;
}
F diff() const { F(*this).diff_inplace(); }
F &integral_inplace() {
int n = (*this).size(), mod = T::mod();
std::vector<T> inv(n);
{
inv[1] = 1;
for(int i = 2; i < n; ++i)
inv[i] = T(mod) - inv[mod % i] * (mod / i);
}
for(int i = n - 2; i >= 0; --i) (*this)[i + 1] = (*this)[i] * inv[i + 1];
(*this)[0] = 0;
return *this;
}
F integral() const { return F(*this).integral_inplace(); }
F &log_inplace() {
int n = (*this).size();
assert(n and (*this)[0] == 1);
F f_inv = (*this).inv();
(*this).diff_inplace();
(*this) *= f_inv;
(*this).integral_inplace();
return *this;
}
F log() const { return F(*this).log_inplace(); }
F &deriv_inplace() {
int n = (*this).size();
assert(n);
for(int i = 2; i < n; ++i) (*this)[i] *= i;
(*this).erase((*this).begin());
(*this).push_back(0);
return *this;
}
F deriv() const { return F(*this).deriv_inplace(); }
F &exp_inplace() {
int n = (*this).size();
assert(n and (*this)[0] == 0);
F g{1};
(*this)[0] = 1;
F h_drv((*this).deriv());
for(int m = 1; m < n; m *= 2) {
F f((*this).begin(), (*this).begin() + m);
f.resize(2 * m), atcoder::internal::butterfly(f);
auto mult_f = [&](F &p) {
p.resize(2 * m);
atcoder::internal::butterfly(p);
for(int i = 0; i < 2 * m; ++i) p[i] *= f[i];
atcoder::internal::butterfly_inv(p);
p /= 2 * m;
};
if(m > 1) {
F g_(g);
g_.resize(2 * m), atcoder::internal::butterfly(g_);
for(int i = 0; i < 2 * m; ++i) g_[i] *= g_[i] * f[i];
atcoder::internal::butterfly_inv(g_);
T iz = T(-2 * m).inv();
g_ *= iz;
g.insert(g.end(), g_.begin() + m / 2, g_.begin() + m);
}
F t((*this).begin(), (*this).begin() + m);
t.deriv_inplace();
{
F r{h_drv.begin(), h_drv.begin() + m - 1};
mult_f(r);
for(int i = 0; i < m; ++i) t[i] -= r[i] + r[m + i];
}
t.insert(t.begin(), t.back());
t.pop_back();
t *= g;
F v((*this).begin() + m, (*this).begin() + std::min(n, 2 * m));
v.resize(m);
t.insert(t.begin(), m - 1, 0);
t.push_back(0);
t.integral_inplace();
for(int i = 0; i < m; ++i) v[i] -= t[m + i];
mult_f(v);
for(int i = 0; i < std::min(n - m, m); ++i)
(*this)[m + i] = v[i];
}
return *this;
}
F exp() const { return F(*this).exp_inplace(); }
F &pow_inplace(long long k) {
int n = (*this).size(), l = 0;
assert(k >= 0);
if(!k) {
for(int i = 0; i < n; ++i) (*this)[i] = !i;
return *this;
}
while(l < n and (*this)[l] == 0) ++l;
if(l > (n - 1) / k or l == n) return *this = F(n);
T c = (*this)[l];
(*this).erase((*this).begin(), (*this).begin() + l);
(*this) /= c;
(*this).log_inplace();
(*this).resize(n - l * k);
(*this) *= k;
(*this).exp_inplace();
(*this) *= c.pow(k);
(*this).insert((*this).begin(), l * k, 0);
return *this;
}
F pow(const long long k) const { return F(*this).pow_inplace(); }
};
using mint = modint998244353;
using fps = FormalPowerSeries<mint, FAST>;
template<typename T>
struct combination{
vector<T> fac, ifac;
combination(size_t n=0) : fac(1, 1), ifac(1, 1){
make_table(n);
}
void make_table(size_t n){
if(fac.size()>n) return;
size_t now = fac.size();
n = max(n, now*2);
fac.resize(n+1);
ifac.resize(n+1);
for(size_t i=now; i<=n; i++) fac[i] = fac[i-1]*i;
ifac[n]=T(1)/fac[n];
for(size_t i=n; i-->now; ) ifac[i] = ifac[i+1]*(i+1);
}
T factorial(size_t n){
make_table(n);
return fac[n];
}
T invfac(size_t n){
make_table(n);
return ifac[n];
}
T P(size_t n, size_t k){
if(n < k) return 0;
make_table(n);
return fac[n]*ifac[n-k];
}
T C(size_t n, size_t k){
if(n < k) return 0;
make_table(n);
return fac[n]*ifac[n-k]*ifac[k];
}
T H(size_t n, size_t k){
if(n==0) return k==0?1:0;
return C(n-1+k, k);
}
};
combination<mint> comb;
fps product_of_polynomial_sequence(vector<fps> F){
queue<fps> Q;
Q.push({1});
for(auto f : F) Q.push(f);
int cnt = 0;
while((int)Q.size()>1){
fps f = Q.front();
Q.pop();
fps g = Q.front();
Q.pop();
for(int i=0; i<(int)g.size(); i++) f.push_back(0);
f *= g;
Q.push(f);
}
return Q.front();
};
int main(){
int n, s, t; cin >> n >> s >> t;
s--; t--;
vector<vector<int>> T(n);
vector<pair<int, int>> es(n-1);
for(int i=0; i<n-1; i++){
int u, v; cin >> u >> v;
u--; v--;
T[u].push_back(v);
T[v].push_back(u);
es[i] = {u, v};
}
vector<int> P;
function<bool(int, int)> dfs = [&](int v, int p){
if(es[t].first==v || es[t].second==v){
P.push_back(v);
return true;
}
for(int to : T[v]) if(to != p){
if(dfs(to, v)){
P.push_back(v);
return true;
}
}
return false;
};
dfs(es[s].first, es[s].second);
dfs(es[s].second, es[s].first);
if((int)P.size() == 1){
}
int siz = (int)P.size();
vector<fps> F(siz);
int D = 0;
for(int i=0; i<siz; i++){
int d = T[P[i]].size()-2;
D += d;
fps f(d+1);
for(int j=0; j<=d; j++) f[j] = comb.P(d, j);
F[i] = f;
}
fps pr = product_of_polynomial_sequence(F);
vector<mint> ans(n+1, 0);
for(int i=0; i<=D; i++){
ans[(int)P.size()+1+i] = pr[i];
}
for(int i=1; i<=n; i++) cout << ans[i].val() << " \n"[i==n];
}