結果
| 問題 |
No.3315 FPS Game
|
| コンテスト | |
| ユーザー |
👑  ArcAki
|
| 提出日時 | 2025-04-17 07:03:51 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 173 ms / 3,250 ms |
| コード長 | 8,902 bytes |
| コンパイル時間 | 4,353 ms |
| コンパイル使用メモリ | 309,432 KB |
| 実行使用メモリ | 28,500 KB |
| 最終ジャッジ日時 | 2025-05-02 20:03:03 |
| 合計ジャッジ時間 | 7,700 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 |
ソースコード
// GPT-o4-mini-highによる生成コード
#include <bits/stdc++.h>
using namespace std;
static const int MOD = 998244353;
static const int G = 3; // primitive root
// Fast exponentiation modulo MOD
int modpow(int a, long long e) {
long long r = 1, x = a;
while (e) {
if (e & 1) r = r * x % MOD;
x = x * x % MOD;
e >>= 1;
}
return int(r);
}
// ----- NTT (in-place) -----
void ntt(vector<int>& a, bool invert) {
int n = a.size();
static vector<int> rev;
static vector<int> roots{0,1};
// build bit-reversed indices
if ((int)rev.size() != n) {
int k = __builtin_ctz(n);
rev.assign(n, 0);
for (int i = 0; i < n; i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
for (int i = 0; i < n; i++)
if (i < rev[i]) swap(a[i], a[rev[i]]);
// build roots of unity
if ((int)roots.size() < n) {
int k = __builtin_ctz(roots.size());
roots.resize(n);
while ((1 << k) < n) {
int e = modpow(G, (MOD - 1) >> (k + 1));
for (int i = 1 << (k - 1); i < (1 << k); i++) {
roots[2 * i] = roots[i];
roots[2 * i + 1] = int((long long)roots[i] * e % MOD);
}
k++;
}
}
// Cooley–Tukey
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += 2 * len) {
for (int j = 0; j < len; j++) {
int u = a[i + j];
int v = int((long long)a[i + j + len] * roots[len + j] % MOD);
a[i + j] = u + v < MOD ? u + v : u + v - MOD;
a[i + j + len] = u - v >= 0 ? u - v : u - v + MOD;
}
}
}
if (invert) {
reverse(a.begin() + 1, a.end());
int inv_n = modpow(n, MOD - 2);
for (int &x : a) x = int((long long)x * inv_n % MOD);
}
}
// multiply two polynomials via NTT
vector<int> multiply(const vector<int>& A, const vector<int>& B) {
int need = int(A.size() + B.size()) - 1;
int n = 1;
while (n < need) n <<= 1;
vector<int> fa(A.begin(), A.end()), fb(B.begin(), B.end());
fa.resize(n);
fb.resize(n);
ntt(fa, false);
ntt(fb, false);
for (int i = 0; i < n; i++)
fa[i] = int((long long)fa[i] * fb[i] % MOD);
ntt(fa, true);
fa.resize(need);
return fa;
}
// factorials and inverse factorials
vector<int> fact, invfact;
void init_factorials(int n) {
fact.assign(n + 1, 1);
for (int i = 1; i <= n; i++)
fact[i] = int((long long)fact[i - 1] * i % MOD);
invfact.assign(n + 1, 1);
invfact[n] = modpow(fact[n], MOD - 2);
for (int i = n; i > 0; i--)
invfact[i - 1] = int((long long)invfact[i] * i % MOD);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, S, T;
cin >> N >> S >> T;
vector<int> U(N), V(N);
vector<vector<pair<int,int>>> adj(N+1);
for(int i = 1; i <= N-1; i++){
cin >> U[i] >> V[i];
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
// --- Build LCA structure on vertices ---
int LOG = __lg(N) + 2;
vector<int> depth(N+1, 0);
vector<vector<int>> up(LOG, vector<int>(N+1, 0));
function<void(int,int)> dfs = [&](int u, int p){
up[0][u] = p;
for (auto &pr : adj[u]){
int v = pr.first;
if (v == p) continue;
depth[v] = depth[u] + 1;
dfs(v, u);
}
};
dfs(1, 0);
for (int k = 1; k < LOG; k++){
for (int v = 1; v <= N; v++){
up[k][v] = up[k-1][ up[k-1][v] ];
}
}
auto lca = [&](int a, int b){
if (depth[a] < depth[b]) swap(a,b);
int d = depth[a] - depth[b];
for (int k = 0; k < LOG; k++)
if (d >> k & 1) a = up[k][a];
if (a == b) return a;
for (int k = LOG-1; k >= 0; k--){
if (up[k][a] != up[k][b]){
a = up[k][a];
b = up[k][b];
}
}
return up[0][a];
};
auto dist = [&](int a, int b){
int w = lca(a,b);
return depth[a] + depth[b] - 2*depth[w];
};
// Determine which endpoints of edges S and T give minimal vertex-distance
int us = U[S], vs = V[S], ut = U[T], vt = V[T];
array<pair<int,pair<int,int>>,4> cand = {{
{dist(us,ut),{us,ut}},
{dist(us,vt),{us,vt}},
{dist(vs,ut),{vs,ut}},
{dist(vs,vt),{vs,vt}}
}};
sort(cand.begin(), cand.end(),
[](auto &a, auto &b){ return a.first < b.first; });
int D = cand[0].first;
int p = cand[0].second.first;
int q = cand[0].second.second;
int L = D + 2; // minimal number of stages
// Retrieve the unique simple path of vertices from p to q
vector<int> path_u, path_v;
int w = lca(p, q);
for (int x = p; x != w; x = up[0][x]) path_u.push_back(x);
path_u.push_back(w);
for (int x = q; x != w; x = up[0][x]) path_v.push_back(x);
reverse(path_v.begin(), path_v.end());
for (int x : path_v) path_u.push_back(x);
// path_u is now the vertex-path from p to q
// Collect the edge-indices along that vertex-path
vector<int> vertexPathEdges;
vertexPathEdges.reserve(path_u.size()-1);
for (int i = 0; i + 1 < (int)path_u.size(); i++){
int a = path_u[i], b = path_u[i+1];
// find the edge index a--b
for (auto &pr : adj[a]){
if (pr.first == b){
vertexPathEdges.push_back(pr.second);
break;
}
}
}
// Build the "main path" of edges from S to T
vector<int> mainEdges;
mainEdges.reserve(vertexPathEdges.size() + 2);
mainEdges.push_back(S);
for (int e : vertexPathEdges){
if (e != S && e != T) mainEdges.push_back(e);
}
mainEdges.push_back(T);
// Now mainEdges.size() == L
// Gather the (deg-2) counts for each segment between consecutive main-edges
vector<int> xs;
xs.reserve(mainEdges.size());
for (int i = 0; i + 1 < (int)mainEdges.size(); i++){
int e1 = mainEdges[i], e2 = mainEdges[i+1];
// find their shared vertex
int a1 = U[e1], b1 = V[e1];
int a2 = U[e2], b2 = V[e2];
int shared = (a1==a2||a1==b2) ? a1 : b1;
int d = adj[shared].size();
int x = d - 2;
if (x > 0) xs.push_back(x);
}
// If no segments have extra branches, the only path is the minimal one
if (xs.empty()) {
for (int k = 1; k <= N; k++){
cout << (k==L ? 1 : 0) << (k==N?'\n':' ');
}
return 0;
}
// Precompute factorials up to max(xs)
int mx = *max_element(xs.begin(), xs.end());
init_factorials(mx);
// Build each polynomial f_i(t) of degree x: f_i[k] = P(x, k) = x*(x-1)*...*(x-k+1)
vector<vector<int>> polys;
polys.reserve(xs.size());
for (int x : xs){
vector<int> p(x+1, 0);
// p[k] = fact[x] * invfact[x-k] mod
for (int k = 0; k <= x; k++){
p[k] = int((long long)fact[x] * invfact[x - k] % MOD);
}
polys.push_back(move(p));
}
// Multiply all polynomials via a min‑heap to merge smallest first
auto cmp = [&](const vector<int>& A, const vector<int>& B){
return A.size() > B.size();
};
priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
for (auto &p : polys) pq.push(p);
while (pq.size() > 1) {
auto A = move(const_cast<vector<int>&>(pq.top())); pq.pop();
auto B = move(const_cast<vector<int>&>(pq.top())); pq.pop();
vector<int> C;
// Fast paths for very small or scalar polys:
if (A.size() == 1) {
int c0 = A[0];
C = B;
if (c0 != 1)
for (int &v : C) v = int((long long)v * c0 % MOD);
}
else if (B.size() == 1) {
int c0 = B[0];
C = A;
if (c0 != 1)
for (int &v : C) v = int((long long)v * c0 % MOD);
}
else if ((long long)A.size() * B.size() < 4096) {
// naive O(n*m) convolution for small sizes
C.assign(A.size() + B.size() - 1, 0);
for (int i = 0; i < (int)A.size(); i++)
for (int j = 0; j < (int)B.size(); j++)
C[i+j] = (C[i+j] + (long long)A[i] * B[j]) % MOD;
}
else {
// use NTT
C = multiply(A, B);
}
pq.push(move(C));
}
auto F = pq.top(); // the full generating function
// Prepare answers: f[k] = coefficient of t^(k-L) in F, for k >= L
vector<int> ans(N+1, 0);
for (int k = L; k <= N; k++){
int idx = k - L;
if (idx < (int)F.size())
ans[k] = F[idx];
}
// Output
for (int k = 1; k <= N; k++){
cout << ans[k] << (k==N?'\n':' ');
}
return 0;
}