結果
| 問題 |
No.3315 FPS Game
|
| コンテスト | |
| ユーザー |
 aPNJ777
|
| 提出日時 | 2025-10-24 21:40:05 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 525 ms / 3,250 ms |
| コード長 | 34,649 bytes |
| コンパイル時間 | 4,815 ms |
| コンパイル使用メモリ | 334,320 KB |
| 実行使用メモリ | 192,456 KB |
| 最終ジャッジ日時 | 2025-10-24 21:40:24 |
| 合計ジャッジ時間 | 18,379 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
#define vv(type, name, h, w) vector<vector<type>> name(h, vector<type>(w))
#define vvv(type, name, h, w, l) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(l)))
#define vvvv(type, name, a, b, c, d) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(d))))
#define vvvvv(type, name, a, b, c, d, e) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(e)))))
#define elif else if
#define FOR1(a) for (long long _ = 0; _ < (long long)(a); _++)
#define FOR2(i, n) for (long long i = 0; i < (long long)(n); i++)
#define FOR3(i, l, r) for (long long i = l; i < (long long)(r); i++)
#define FOR4(i, l, r, c) for (long long i = l; i < (long long)(r); i += c)
#define FOR1_R(a) for (long long _ = (long long)(a) - 1; _ >= 0; _--)
#define FOR2_R(i, n) for (long long i = (long long)(n) - 1; i >= (long long)(0); i--)
#define FOR3_R(i, l, r) for (long long i = (long long)(r) - 1; i >= (long long)(l); i--)
#define FOR4_R(i, l, r, c) for (long long i = (long long)(r) - 1; i >= (long long)(l); i -= (c))
#define overload4(a, b, c, d, e, ...) e
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_in(a, A) for (auto a: A)
#define FOR_each(a, A) for (auto &&a: A)
#define FOR_subset(t, s) for(long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) int(x.size())
int popcount(int x) { return __builtin_popcount(x); }
int popcount(uint32_t x) { return __builtin_popcount(x); }
int popcount(long long x) { return __builtin_popcountll(x); }
int popcount(uint64_t x) { return __builtin_popcountll(x); }
// __builtin_clz(x)は最上位bitからいくつ0があるか.
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(uint32_t x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(long long x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(uint64_t x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// 入力
void rd() {}
void rd(char &c) { cin >> c; }
void rd(string &s) { cin >> s; }
void rd(int &x) { cin >> x; }
void rd(uint32_t &x) { cin >> x; }
void rd(long long &x) { cin >> x; }
void rd(uint64_t &x) { cin >> x; }
template<class T>
void rd(vector<T> &v) {
for (auto& x:v) rd(x);
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
rd(h), read(t...);
}
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define STRING(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define U32(...) \
uint32_t __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
long long __VA_ARGS__; \
read(__VA_ARGS__)
#define U64(...) \
uint64_t __VA_ARGS__; \
read(__VA_ARGS__)
#define VC(t, a, n) \
vector<t> a(n); \
read(a)
#define VVC(t, a, h, w) \
vector<vector<t>> a(h, vector<t>(w)); \
read(a)
//出力
void wt() {}
void wt(const char c) { cout << c; }
void wt(const string s) { cout << s; }
void wt(int x) { cout << x; }
void wt(uint32_t x) { cout << x; }
void wt(long long x) { cout << x; }
void wt(uint64_t x) { cout << x; }
void wt(double x) { cout << fixed << setprecision(16) << x; }
void wt(long double x) { cout << fixed << setprecision(16) << x; }
template<class T>
void wt(const vector<T> v) {
int n = v.size();
for (int i = 0; i < n; i++) {
if (i) wt(' ');
wt(v[i]);
}
}
void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
wt(head);
if (sizeof...(Tail)) wt(' ');
print(forward<Tail>(tail)...);
}
/////////////////////////////////////////////////////////////////////////////////////////
long long min(long long a, long long b) { return a < b ? a : b; }
template <class T>
T min(vector<T> A) {
assert (A.size());
T S = A[0];
for (T a : A) S = min(a, S);
return S;
}
long long max(long long a, long long b) { return a > b ? a : b; }
template <class T>
T max(vector<T> A) {
assert (A.size());
T S = A[0];
for (T a : A) S = max(a, S);
return S;
}
long long add(long long x, long long y) {return x + y; }
template <class mint>
mint add(mint x, mint y) { return x + y; }
template <class T>
bool chmin(T & x, T a) { return a < x ? (x = a, true) : false; }
template <class T>
bool chmax(T & x, T a) { return a > x ? (x = a, true) : false; }
template <class T>
T sum(vector<T> A) {
T S = 0;
for (int i = 0; i < int(A.size()); i++) S += A[i];
return S;
}
uint64_t random_u64(uint64_t l, uint64_t r) {
static std::random_device rd;
static std::mt19937_64 gen(rd());
std::uniform_int_distribution<uint64_t> dist(l, r);
return dist(gen);
}
long long gcd(long long a, long long b) {
while (a) {
b %= a;
if (b == 0) return a;
a %= b;
}
return b;
}
long long lcm(long long a, long long b) {
if (a * b == 0) return 0;
return a * b / gcd(a, b);
}
long long pow_mod(long long a, long long r, long long mod) {
long long res = 1, p = a % mod;
while (r) {
if ((r % 2) == 1) res = res * p % mod;
p = p * p % mod, r >>= 1;
}
return res;
}
long long mod_inv(long long a, long long mod) {
if (mod == 1) return 0;
a %= mod;
long long b = mod, s = 1, t = 0;
while (1) {
if (a == 1) return s;
t -= (b / a) * s;
b %= a;
if (b == 1) return t + mod;
s -= (a / b) * t;
a %= b;
}
}
long long Garner(vector<long long> Rem, vector<long long> Mod, int MOD) {
assert (Rem.size() == Mod.size());
long long mod = MOD;
Rem.push_back(0);
Mod.push_back(mod);
long long n = Mod.size();
vector<long long> coffs(n, 1);
vector<long long> constants(n, 0);
for (int i = 0; i < n - 1; i++) {
long long v = (Mod[i] + Rem[i] - constants[i]) % Mod[i];
v *= mod_inv(coffs[i], Mod[i]);
v %= Mod[i];
for (int j = i + 1; j < n; j++) {
constants[j] = (constants[j] + coffs[j] * v) % Mod[j];
coffs[j] = (coffs[j] * Mod[i]) % Mod[j];
}
}
return constants[n - 1];
}
long long Tonelli_Shanks(long long a, long long mod) {
a %= mod;
if (a < 2) return a;
if (pow_mod(a, (mod - 1) / 2, mod) != 1) return -1;
if (mod % 4 == 3) return pow_mod(a, (mod + 1) / 4, mod);
long long b = 3;
if (mod != 998244353) {
while (pow_mod(b, (mod - 1) / 2, mod) == 1) {
b = random_u64(2, mod - 1);
}
}
long long q = mod - 1;
long long Q = 0;
while (q % 2 == 0) {
Q++, q /= 2;
}
long long x = pow_mod(a, (q + 1) / 2, mod);
b = pow_mod(b, q, mod);
long long shift = 2;
while ((x * x) % mod != a) {
long long error = (((pow_mod(a, mod - 2, mod) * x) % mod) * x) % mod;
if (pow_mod(error, 1 << (Q - shift), mod) != 1) {
x = (x * b) % mod;
}
b = (b * b) % mod;
shift++;
}
return x;
}
/////////////////////////////////////////////////////////////////////////////////////////
template <int mod>
struct modint {
static constexpr uint32_t umod = uint32_t(mod);
static_assert(umod < (uint32_t(1) << 31));
uint32_t val;
static modint raw(uint32_t v) {
modint x;
x.val = v % umod;
return x;
}
constexpr modint() : val(0) {}
constexpr modint(uint32_t x) : val(x % umod) {}
constexpr modint(uint64_t x) : val(x % umod) {}
constexpr modint(__uint128_t x) : val(x % umod) {}
constexpr modint(int x) : val((x %= int(umod)) < 0 ? x + umod : x) {};
constexpr modint(long long x) : val((x %= int(umod)) < 0 ? x + umod : x) {};
constexpr modint(__int128_t x) : val((x %= int(umod)) < 0 ? x + umod : x) {};
bool operator<(const modint &other) const { return val < other.val; }
modint &operator+=(const modint &p) {
if ((val += p.val) >= umod) val -= umod;
return *this;
}
modint &operator-=(const modint &p) {
if ((val += umod - p.val) >= umod) val -= umod;
return *this;
}
modint &operator*=(const modint &p) {
val = uint64_t(val) * p.val % umod;
return *this;
}
modint &operator/=(const modint &p) {
val = uint64_t(val) * p.inverse().val % umod;
return *this;
}
modint operator-() const { return modint::raw(val ? umod - val : uint32_t(0)); }
modint operator+(const modint &p) const { return modint(*this) += p; }
modint operator-(const modint &p) const { return modint(*this) -= p; }
modint operator*(const modint &p) const { return modint(*this) *= p; }
modint operator/(const modint &p) const { return modint(*this) /= p; }
bool operator==(const modint &p) const { return val == p.val; }
bool operator!=(const modint &p) const { return val != p.val; }
modint inverse() const {
int a = val, b = umod, s = 1, t = 0;
while (1) {
if (a == 1) return modint(s);
t -= (b / a) * s;
b %= a;
if (b == 1) return modint(t + umod);
s -= (a / b) * t;
a %= b;
}
}
modint pow(long long n) const {
n %= (long long)(umod - 1);
if (n < 0) n += umod - 1;
modint res(1), a(val);
while (n > 0) {
if (n & 1) res *= a;
a *= a;
n >>= 1;
}
return res;
}
uint32_t get() const { return val; }
static constexpr int get_mod() { return mod; }
static constexpr pair<int, int> ntt_info() {
if (mod == 167772161) return {25, 17};
if (mod == 469762049) return {26, 30};
if (mod == 754974721) return {24, 362};
if (mod == 880803841) return {23, 211};
if (mod == 998244353) return {23, 31};
return {-1, -1};
}
};
template <int mod>
void rd(modint<mod> &x) {
uint32_t y;
cin >> y;
x = y;
}
template <int mod>
void wt(modint<mod> x) {
wt(x.val);
}
template <typename mint>
mint fact(long long n) {
static bool prepared = 0;
static int N = 20000000, mod = mint::get_mod();
if (N > mod - 1) N = mod - 1;
static vector<mint> res(N + 1, mint(1));
if (prepared == 0) {
prepared = 1;
for (int i = 2; i <= N; i++) res[i] = res[i - 1] * i;
}
if (n < 0) return mint(0);
assert (n <= N);
return res[n];
}
template <typename mint>
mint fact_inv(long long n) {
static bool prepared = 0;
static int N = 20000000, mod = mint::get_mod();
if (N > mod - 1) N = mod - 1;
static vector<mint> res(N + 1, mint(1));
if (prepared == 0) {
prepared = 1;
res[N] = fact<mint>(N).inverse();
for (int i = N - 1; i >= 1; i--) res[i] = res[i + 1] * (i + 1);
}
if (n < 0) return mint(0);
assert (n <= N);
return res[n];
}
template <typename mint>
mint binom(long long n, long long r) {
if (n < 0 || r < 0 || n < r) return 0;
mint res = fact<mint>(n) * (fact_inv<mint>(n - r) * fact_inv<mint>(r));
return res;
}
template <class mint>
void ntt(vector<mint> &a, bool inverse) {
const int mod = mint::get_mod();
const int rank2 = mint::ntt_info().first;
static array<mint, 30> root, rate2, rate3, iroot, irate2, irate3;
static bool prepared = 0;
if (!prepared) {
prepared = 1;
root[rank2] = mint::ntt_info().second;
iroot[rank2] = mint(1) / root[rank2];
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
mint prod = 1, iprod = 1;
for (int i = 0; i < rank2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
prod = 1, iprod = 1;
for (int i = 0; i < rank2 - 1; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
int n = int(a.size()), h = (n == 0 ? -1 : 31 - __builtin_clz(n));
if (!inverse) {
int le = 0;
while (le < h) {
if (h - le == 1) {
int p = 1 << (h - le - 1);
mint rot = 1;
for (int s = 0; s < (1 << le); s++) {
int offset = s << (h - le);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * rot;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
rot *= rate2[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
}
le++;
}
else {
int p = 1 << (h - le - 2);
mint rot = 1, imag = root[2];
for (int s = 0; s < (1 << le); s++) {
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = s << (h - le);
for (int i = 0; i < p; i++) {
uint64_t mod2 = uint64_t(mod) * mod;
uint64_t a0 = a[i + offset].get();
uint64_t a1 = uint64_t(a[i + offset + p].get()) * rot.get();
uint64_t a2 = uint64_t(a[i + offset + p * 2].get()) * rot2.get();
uint64_t a3 = uint64_t(a[i + offset + p * 3].get()) * rot3.get();
uint64_t a1na3imag = (a1 + mod2 - a3) % mod * imag.get();
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + offset + p * 2] = a0 + mod2 - a2 + a1na3imag;
a[i + offset + p * 3] = a0 + mod2 - a2 + (mod2 - a1na3imag);
}
rot = rot * rate3[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
}
le = le + 2;
}
}
}
else {
mint coef = mint(n).inverse();
for (int i = 0; i < n; i++) {
a[i] *= coef;
}
int le = h;
while (le) {
if (le == 1) {
int p = 1 << (h - le);
mint irot = 1;
for (int s = 0; s < (1 << (le - 1)); s++) {
int offset = s << (h - le + 1);
for (int i = 0; i < p; i++) {
uint64_t l = a[i + offset].get();
uint64_t r = a[i + offset + p].get();
a[i + offset] = l + r;
a[i + offset + p] = (mod + l - r) * irot.get();
}
irot *= irate2[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
}
le--;
}
else {
int p = 1 << (h - le);
mint irot = 1, iimag = iroot[2];
for (int s = 0; s < (1 << (le - 2)); s++) {
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = s << (h - le + 2);
for (int i = 0; i < p; i++) {
uint64_t a0 = a[i + offset].get();
uint64_t a1 = a[i + offset + p].get();
uint64_t a2 = a[i + offset + p * 2].get();
uint64_t a3 = a[i + offset + p * 3].get();
uint64_t a2na3iimag = (mod + a2 - a3) * iimag.get() % mod;
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + p] = (a0 + mod - a1 + a2na3iimag) * irot.get();
a[i + offset + p * 2] = (a0 + a1 + 2 * mod - a2 - a3) * irot2.get();
a[i + offset + p * 3] = (a0 + 2 * mod - a1 - a2na3iimag) * irot3.get();
}
irot *= irate3[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
}
le = le - 2;
}
}
}
}
template <typename mint>
void transposed_ntt(vector<mint> &a, bool inverse) {
if (!inverse) {
ntt(a, 1);
reverse(a.begin() + 1, a.end());
for (auto &x: a) {
x *= a.size();
}
}
else {
reverse(a.begin() + 1, a.end());
ntt(a, 0);
for (auto &x: a) {
x /= mint(a.size());
}
}
}
template <class mint>
void ntt_doubling(vector<mint> &a, bool inverse) {
const int rank2 = mint::ntt_info().first;
static array<mint, 30> root, rate2, rate3, iroot, irate2, irate3;
static bool prepared = 0;
if (!prepared) {
prepared = 1;
root[rank2] = mint::ntt_info().second;
iroot[rank2] = mint(1) / root[rank2];
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
mint prod = 1, iprod = 1;
for (int i = 0; i < rank2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
prod = 1, iprod = 1;
for (int i = 0; i < rank2 - 1; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
if (inverse == 0) {
int M = int(a.size());
vector<mint> b = a;
ntt(b, 1);
mint r = 1;
mint zeta = root[(2 * M == 0 ? -1 : 31 - __builtin_clz(2 * M))];
for (int i = 0; i < M; i++) {
b[i] *= r, r *= zeta;
}
ntt(b, 0);
for (auto x: b) {
a.push_back(x);
}
return;
}
else {
int M = int(a.size()) / 2;
vector<mint> b = {a.begin() + M, a.end()};
transposed_ntt(b, 0);
mint r = 1;
mint zeta = root[(2 * M == 0 ? -1 : 31 - __builtin_clz(2 * M))];
for (int i = 0; i < M; i++) {
b[i] *= r, r *= zeta;
}
transposed_ntt(b, 1);
for (int i = 0; i < M; i++) {
a[i] += b[i];
}
return;
}
}
template <class mint>
vector<mint> convolution_naive(vector<mint> a, vector<mint> b) {
vector<mint> res(size(a) + size(b) - 1);
for (int i = 0; i < int(size(a)); i++) {
if (a[i] == mint(0)) continue;
for (int j = 0; j < int(size(b)); j++) {
res[i + j] = res[i + j] + a[i] * b[j];
}
}
return res;
}
template <class mint>
vector<mint> convolution_ntt(vector<mint> a, vector<mint> b) {
int n = a.size();
int m = b.size();
if (min(n, m) <= 60) return convolution_naive(a, b);
int le = 1;
while (le < n + m - 1) le = le * 2;
a.resize(le), b.resize(le);
ntt(a, 0), ntt(b, 0);
for (int i = 0; i < le; i++) a[i] *= b[i];
ntt(a, 1);
a.resize(n + m - 1);
return a;
}
template <class mint>
vector<mint> convolution_garner(vector<mint> a, vector<mint> b) {
const int mod = mint::get_mod();
int n = int(a.size()), m = int(b.size());
if (min(n, m) <= 60) return convolution_naive(a, b);
const vector<long long> nttfriend = {167772161, 469762049, 754974721};
using mint1 = modint<167772161>;
using mint2 = modint<469762049>;
using mint3 = modint<754974721>;
vector<mint1> a1(n), b1(m);
vector<mint2> a2(n), b2(m);
vector<mint3> a3(n), b3(m);
for (int i = 0; i < n; i++) {
a1[i] = a[i].get(), a2[i] = a[i].get(), a3[i] = a[i].get();
}
for (int i = 0; i < m; i++) {
b1[i] = b[i].get(), b2[i] = b[i].get(), b3[i] = b[i].get();
}
vector<mint1> c1 = convolution_ntt(a1, b1);
vector<mint2> c2 = convolution_ntt(a2, b2);
vector<mint3> c3 = convolution_ntt(a3, b3);
vector<mint> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
vector<long long> Rem = {c1[i].get(), c2[i].get(), c3[i].get()};
c[i] = mint(Garner(Rem, nttfriend, mod));
}
return c;
}
template <class mint>
vector<mint> convolution(vector<mint> a, vector<mint> b) {
if (mint::ntt_info().first == -1) return convolution_garner(a, b);
return convolution_ntt(a, b);
}
template <class mint>
vector<mint> Poly_add(vector<mint> f, vector<mint> g) {
int n = max(int(f.size()), int(g.size()));
f.resize(n);
for (int i = 0; i < int(g.size()); i++) f[i] += g[i];
return f;
}
template <class mint>
vector<mint> fps_inv(vector<mint> f, int deg = -1) {
assert (f[0] != mint(0));
if (deg == -1) deg = int(f.size());
f.resize(deg);
int n = int(f.size());
// ntt prime
if (mint::ntt_info().first != -1) {
vector<mint> g(deg, mint(0));
g[0] = f[0].inverse();
int le = 1;
while (le < deg) {
vector<mint> a(2 * le, mint(0)), b(2 * le, mint(0));
for (int i = 0; i < min(n, 2 * le); i++) {
a[i] = f[i];
}
for (int i = 0; i < le; i++) {
b[i] = g[i];
}
ntt(a, 0), ntt(b, 0);
for (int i = 0; i < 2 * le; i++) {
a[i] *= b[i];
}
ntt(a, 1);
for (int i = 0; i < le; i++) {
a[i] = mint(0);
}
ntt(a, 0);
for (int i = 0; i < 2 * le; i++) {
a[i] *= b[i];
}
ntt(a, 1);
for (int i = le; i < min(deg, 2 * le); i++) {
g[i] = -a[i];
}
le *= 2;
}
return g;
}
// not ntt prime
// doubling
else {
vector<mint> g = {f[0].inverse()};
vector<mint> gg(0);
int le = 1;
while (le < deg) {
gg = convolution(g, g);
gg.resize(2 * le);
vector<mint> ff = {f.begin(), f.begin() + min(2 * le, n)};
gg = convolution(gg, f);
g.resize(2 * le);
for (int i = 0; i < 2 * le; i++) {
g[i] = g[i] + g[i] - gg[i];
}
le *= 2;
}
g.resize(deg);
return g;
}
}
template <class mint>
vector<mint> fps_exp(vector<mint> f, int deg = -1) {
if (deg == -1) deg = int(f.size());
f.resize(deg);
int n = int(f.size());
assert (n > 0);
assert (f[0] == mint(0));
// ntt prime
if (mint::ntt_info().first != -1) {
vector<mint> g = {mint(1), mint(0)};
if (f.size() > 1) g[1] = f[1];
vector<mint> h = {mint(1)};
vector<mint> p, q;
q = {mint(1), mint(1)};
int le = 2;
while (le < deg) {
vector<mint> y = g;
y.resize(2 * le);
ntt(y, 0);
p = q;
vector<mint> z(le);
for (int i = 0; i < le; i++) {
z[i] = y[i] * p[i];
}
ntt(z, 1);
for (int i = 0; i < le / 2; i++) {
z[i] = mint(0);
}
ntt(z, 0);
for (int i = 0; i < int(p.size()); i++) {
z[i] = z[i] * (-p[i]);
}
ntt(z, 1);
for (int i = le / 2; i < le; i++) {
h.push_back(z[i]);
}
q = h;
q.resize(2 * le);
ntt(q, 0);
vector<mint> x(le, mint(0));
for (int i = 0; i < le - 1; i++) {
x[i] = f[i + 1] * mint(i + 1);
}
ntt(x, 0);
for (int i = 0; i < le; i++) {
x[i] *= y[i];
}
ntt(x, 1);
for (int i = 0; i < le - 1; i++) {
x[i] -= g[i + 1] * mint(i + 1);
}
x.resize(2 * le);
for (int i = 0; i < le - 1; i++) {
x[i + le] = x[i], x[i] = mint(0);
}
ntt(x, 0);
for (int i = 0; i < 2 * le; i++) {
x[i] *= q[i];
}
ntt(x, 1);
for (int i = int(x.size()) - 2; i >= 0; i--) {
x[i + 1] = x[i] * mint(i + 1).inverse();
}
for (int i = 0; i < le; i++) {
x[i] = mint(0);
}
for (int i = le; i < 2 * le; i++) {
x[i] += f[i];
}
ntt(x, 0);
for (int i = 0; i < 2 * le; i++) {
x[i] *= y[i];
}
ntt(x, 1);
for (int i = le; i < int(x.size()); i++) {
g.push_back(x[i]);
}
le *= 2;
}
g.resize(deg);
return g;
}
// not ntt prime
// Newton's method
else {
int log = 0;
while ((1 << log) < deg) log++;
f.resize(1 << log);
vector<mint> df(1 << log, mint(0));
for (int i = 1; i < (1 << log); i++) {
df[i - 1] = f[i] * mint(i);
}
vector<mint> g = {mint(1)}, h = {mint(1)};
int le = 1;
vector<mint> p;
for (int _ = 0; _ < log; _++) {
p = convolution(g, h);
p.resize(le);
p = convolution(p, h);
p.resize(le);
h.resize(le);
for (int i = 0; i < le; i++) {
h[i] += h[i] - p[i];
}
p = {df.begin(), df.begin() + le - 1};
p = convolution(g, p);
p.resize(2 * le - 1);
for (int i = 0; i < 2 * le - 1; i++) {
p[i] = -p[i];
}
for (int i = 0; i < le - 1; i++) {
p[i] += g[i + 1] * mint(i + 1);
}
p = convolution(p, h);
p.resize(2 * le - 1);
for (int i = 0; i < le - 1; i++) {
p[i] += df[i];
}
p.push_back(mint(0));
for (int i = 2 * le - 2; i >= 0; i--) {
p[i + 1] = p[i] * mint(i + 1).inverse();
}
p[0] = mint(0);
for (int i = 0; i < 2 * le; i++) {
p[i] = f[i] - p[i];
}
p[0] = mint(1);
g = convolution(g, p);
g.resize(2 * le);
le *= 2;
}
g.resize(deg);
return g;
}
}
template <class mint>
vector<mint> fps_log(vector<mint> f, int deg = -1) {
if (deg == -1) deg = int(f.size());
f.resize(deg);
int n = int(f.size());
assert (n > 0);
assert (f[0] == mint(1));
vector<mint> df(deg, mint(0));
for (int i = 1; i < min(deg + 1, n); i++) {
df[i - 1] = f[i] * mint(i);
}
vector<mint> f_inv = fps_inv(f, deg);
vector<mint> g = convolution(df, f_inv);
g.resize(deg);
for (int i = deg - 2; i >= 0; i--) {
g[i + 1] = g[i] * mint(i + 1).inverse();
}
g[0] = mint(0);
return g;
}
template <class mint>
vector<mint> fps_pow(vector<mint> f, long long k, int deg = -1) {
if (deg == -1) deg = int(f.size());
if (k == 0) {
vector<mint> g(deg, mint(0));
g[0] = mint(1);
return g;
}
f.resize(deg);
int d = 0;
long long kk = 0; // overflow対策
while (d < deg) {
if (f[d] != mint(0)) break;
d++;
kk += k;
if (kk >= deg) {
vector<mint> g(deg, mint(0));
return g;
}
}
if (d == deg) {
vector<mint> g(deg, mint(0));
return g;
}
int dk = kk;
mint a = f[d];
mint a_inv = a.inverse();
vector<mint> g(deg - dk, mint(0));
for (int i = 0; i < deg - dk; i++) {
g[i] = f[i + d] * a_inv;
}
g = fps_log(g);
for (int i = 0; i < deg - dk; i++) {
g[i] *= mint(k);
}
g = fps_exp(g);
a = a.pow(k);
vector<mint> res(deg, mint(0));
for (int i = 0; i < deg - dk; i++) {
res[i + dk] = g[i] * a;
}
return res;
}
template <typename mint>
vector<mint> fps_sqrt(vector<mint> f, int deg = -1) {
if (deg == -1) deg = int(f.size());
f.resize(deg);
int n = int(f.size());
if (f[0] == 1) {
vector<mint> g(1);
g[0] = 1;
int le = 1;
while (le < n) {
le = min(2 * le, n);
g.resize(le);
vector<mint> h = {f.begin(), f.begin() + le};
h = convolution(fps_inv(g), h);
h.resize(le);
for (int i = 0; i < le; i++) {
g[i] += h[i];
}
mint inv_2 = mint(2).inverse();
for (int i = 0; i < le; i++) {
g[i] *= inv_2;
}
}
return g;
}
int d = 0;
while (d < n) {
if (f[d] == mint(0)) {
d++;
continue;
}
break;
}
if (d == n) return f;
if (d & 1) return {};
vector<mint> g(n - d, mint(0));
long long cc = Tonelli_Shanks(f[d].get(), mint::get_mod());
if (cc == -1) return {};
mint c = mint(cc);
mint c_inv = c.inverse() * c.inverse();
for (int i = 0; i < n - d; i++) {
g[i] = f[i + d] * c_inv;
}
g = fps_sqrt(g, n);
g.resize(n);
for (int i = n - 1; i >= 0; i--) {
if (i >= d / 2) g[i] = g[i - d / 2] * c;
else g[i] = 0;
}
return g;
}
template <class mint>
vector<mint> fps_composition(vector<mint> f, vector<mint> g) {
assert (f.size() == g.size());
int N = int(f.size());
if (N == 0) {
vector<mint> res = {};
return res;
}
int n = 1, log = 0;
while (n < N) {
n *= 2, log++;
}
f.resize(n), g.resize(n);
vector<mint> W(2 * n);
vector<int> btr(2 * n);
for (int i = 0; i < 2 * n; i++) {
btr[i] = (btr[i >> 1] >> 1) + ((i & 1) << log);
}
int t = mint::ntt_info().first;
mint r = mint(mint::ntt_info().second);
mint dw = (r.inverse()).pow((1 << t) / (4 * n)), w = mint(1);
for (auto i: btr) {
W[i] = w;
w *= dw;
}
mint inv_2 = mint(2).inverse();
auto rec = [&](auto & rec, int n, int k, vector<mint> Q) -> vector<mint> {
if (n == 1) {
// A
vector<mint> p(2 * k);
reverse(f.begin(), f.end());
for (int i = 0; i < k; i++){
p[2 * i] = f[i];
}
return p;
}
// B
Q.resize(4 * n * k);
Q[2 * n * k] = mint(1);
ntt(Q, 0);
vector<mint> nxt_Q(2 * n * k);
for (int i = 0; i < 2 * n * k; i++){
nxt_Q[i] = Q[2 * i] * Q[2 * i + 1];
}
ntt(nxt_Q, 1);
for (int j = 0; j < 2 * k; j++) {
for (int i = n / 2; i < n; i++) {
nxt_Q[n * j + i] = mint(0);
}
}
nxt_Q[0] = mint(0);
vector<mint> p = rec(rec, n / 2, 2 * k, nxt_Q);
for (int j = 0; j < 2 * k; j++) {
for (int i = n / 2; i < n; i++) {
p[n * j + i] = mint(0);
}
}
transposed_ntt(p, 1);
p.resize(4 * n * k);
for (int i = 2 * n * k - 1; i >= 0; i--) {
p[2 * i + 1] = ((-inv_2) * W[i]) * (Q[2 * i] * p[i]);
p[2 * i] = (inv_2 * W[i]) * (Q[2 * i + 1] * p[i]);
}
transposed_ntt(p, 0);
p.resize(2 * n * k);
return p;
};
vector<mint> Q(2 * n);
for (int i = 0; i < n; i++) {
Q[i] -= g[i];
}
vector<mint> p = rec(rec, n, 1, Q);
// C
p.resize(n);
reverse(p.begin(), p.end());
p.resize(N);
return p;
}
template<class mint>
vector<mint> power_projection(vector<mint> f, vector<mint> wt, int m) {
if (f.size() == 0) return vector<mint>(m, mint(0));
if (f[0] != 0) {
mint c = f[0];
f[0] = 0;
vector<mint> A = power_projection(f, wt, m);
for (int p = 1; p < m; p++) A[p] /= p;
vector<mint> B(m);
mint pow = 1;
for (int q = 0; q < m; q++){
B[q] = pow * fact_inv<mint>(q);
pow *= c;
}
A = convolution(A, B);
A.resize(m);
for (int i = 0; i < m; i++) A[i] *= fact<mint>(i);
return A;
}
int n = 1, log = 0;
while (n < int(f.size())){
n *= 2, log += 1;
}
f.resize(n), wt.resize(n);
reverse(wt.begin(), wt.end());
vector<mint> W(2 * n);
vector<int> btr(2 * n);
for (int i = 0; i < 2 * n; i++) {
btr[i] = (btr[i >> 1] >> 1) + ((i & 1) << log);
}
int t = mint::ntt_info().first;
mint r = mint(mint::ntt_info().second);
mint dw = (r.inverse()).pow((1 << t) / (4 * n)), w = mint(1);
for (auto i: btr) {
W[i] = w;
w *= dw;
}
int k = 1;
vector<mint> P(2 * n, mint(0)), Q(2 * n, mint(0));
for (int i = 0; i < n; i++) {
P[i] = wt[i], Q[i] = -f[i];
}
mint inv_2 = mint(2).inverse();
while (n > 1) {
P.resize(4 * n * k), Q.resize(4 * n * k);
Q[2 * n * k] = mint(1);
ntt(P, 0), ntt(Q, 0);
for (int i = 0; i < 2 * n * k; i++) {
P[i] = (P[2 * i] * Q[2 * i + 1] - P[2 * i + 1] * Q[2 * i]) * (inv_2 * W[i]);
Q[i] = Q[2 * i] * Q[2 * i + 1];
}
P.resize(2 * n * k), Q.resize(2 * n * k);
ntt(P, 1), ntt(Q, 1);
for (int j = 0; j < 2 * k; j++) {
for (int i = n / 2; i < n; i++) {
P[n * j + i] = mint(0), Q[n * j + i] = mint(0);
}
}
Q[0] = mint(0);
n >>= 1, k <<= 1;
}
vector<mint> p(k, mint(0));
for (int i = 0; i < k; i++) {
p[i] = P[2 * i];
}
reverse(p.begin(), p.end());
p.resize(m);
return p;
}
template <typename mint>
vector<mint> fps_compositional_inverse(vector<mint> f) {
int n = int(f.size()) - 1;
if (n == -1) return {};
assert (f[0] == 0);
if (n == 0) return f;
assert (f[1] != 0);
mint c = f[1];
mint ic = c.inverse();
for (int i = 0; i < n + 1; i++) f[i] = f[i] * ic;
vector<mint> wt(n + 1);
wt[n] = 1;
vector<mint> A = power_projection(f, wt, n);
vector<mint> g(n);
for (int i = 1; i < n + 1; i++) g[n - i] = (A[i] * n) / i;
mint k = (-mint(1)) / n;
g = fps_pow(g, k.val);
reverse(g.begin(), g.end());
g.push_back(0);
reverse(g.begin(), g.end());
mint Pow = 1;
for (int i = 0; i < int(g.size()); i++){
g[i] *= Pow, Pow *= ic;
}
return g;
}
template <class mint>
vector<mint> Product_poly_Sequence(vector<vector<mint>> F) {
int n = int(F.size());
if (n == 0) return {mint(1)};
priority_queue<pair<int, int>> G;
for (int i = 0; i < n; i++) {
vector<mint> f = F[i];
int m = int(f.size());
G.push({-m, i});
}
for (int _ = 0; _ < n - 1; _++) {
auto [m1, i] = G.top();
G.pop();
auto [m2, j] = G.top();
G.pop();
F[i] = convolution(F[i], F[j]);
G.push({m1 + m2 + 1, i});
}
return F[G.top().second];
}
template <class mint>
vector<mint> Polynomial_TaylorShift(vector<mint> f, mint c) {
int n = int(f.size()) - 1;
vector<mint> g(n + 1);
for (int i = 0; i <= n; i++) f[i] *= fact<mint>(i), g[n - i] = c.pow(i) * fact_inv<mint>(i);
g = convolution(f, g);
g = {g.begin() + n, g.end()};
for (int i = 0; i <= n; i++) g[i] *= fact_inv<mint>(i);
return g;
}
using mint = modint<998244353>;
//using mint = modint<1000000007>;
using poly = vector<mint>;
/*
検索するとき
https://www.google.com/search?udm=14&q=
-ai
*/
vector<long long> tree_dist(int s, vector<vector<pair<int, long long>>> G) {
int N = int(G.size());
vector<long long> dist(N, -1);
stack<int> st; st.push(s); dist[s] = 0;
while (st.size()) {
int u = st.top(); st.pop();
for (auto [v, w] : G[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + w;
st.push(v);
}
}
}
return dist;
}
struct UnionFind {
int group_size;
vector<int> parent;
UnionFind(int n) : group_size(n), parent(n, -1) { }
int find(int x){
if (parent[x] < 0) return x;
else return parent[x] = find(parent[x]);
}
bool same(int x, int y) { return find(x) == find(y); }
void unite(int x, int y) {
if (same(x, y)) return;
group_size--;
x = find(x), y = find(y);
if (x != y) {
if (parent[x] > parent[y]) swap(x, y);
parent[x] += parent[y];
parent[y] = x;
}
return;
}
int size(int x) { return -parent[find(x)]; }
int groups() { return group_size; }
};
void solve() {
INT(N, S, T);
S--, T--;
UnionFind uf(N);
vector<pair<int, int>> E;
vector<vector<pair<int, long long>>> G(N);
FOR(e, N - 1) {
INT(u, v);
u--, v--;
if (e != S && e != T) uf.unite(u, v);
E.push_back({u, v});
G[u].push_back({v, 1}), G[v].push_back({u, 1});
}
int s = 0, t = 0;
auto [u1, v1] = E[S];
auto [u2, v2] = E[T];
if (uf.same(u1, u2)) s = u1, t = u2;
else if (uf.same(u1, v2)) s = u1, t = v2;
else if (uf.same(v1, u2)) s = v1, t = u2;
else s = v1, t = v2;
auto dist1 = tree_dist(s, G);
auto dist2 = tree_dist(t, G);
ll D = dist1[t];
int now = s;
int C = len(G[s]) - 2;
vector<vector<mint>> F;
poly f(C + 2);
FOR(c, C + 1) {
f[c + 1] = binom<mint>(C, c) * fact<mint>(c);
}
F.push_back(f);
vector<int> seen(N);
seen[s] = 1;
while (now != t) {
for (auto [v, dd] : G[now]) {
if (seen[v]) continue;
if (dist1[v] + dist2[v] != D) continue;
C = len(G[v]) - 2;
poly g(C + 2);
FOR(c, C + 1) g[c + 1] = binom<mint>(C, c) * fact<mint>(c);
F.push_back(g);
now = v;
seen[v] = 1;
continue;
}
}
f = Product_poly_Sequence(F);
f.resize(N);
print(f);
}
int main() {
int T = 1;
//cin >> T;
FOR(T) solve();
}