QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#289005#7864. Random Tree Parkingucup-team180#AC ✓238ms16800kbC++2329.6kb2023-12-23 14:42:502024-11-20 09:59:29

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 09:59:29]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果：AC
  • 用时：238ms
  • 内存：16800kb
查看
  • [2024-11-20 07:58:09]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果：97
  • 用时：250ms
  • 内存：16924kb
查看
  • [2024-11-20 07:55:31]
  • hack成功，自动添加数据
  • (/hack/1204)
  • [2023-12-23 14:42:50]
  • 评测
  • 测评结果：100
  • 用时：216ms
  • 内存：16756kb
查看
  • [2023-12-23 14:42:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using ull = unsigned long long;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
template<class T> using pqmin = priority_queue<T, vector<T>, greater<T>>;
template<class T> using pqmax = priority_queue<T>;
const ll inf=LLONG_MAX/3;
const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define si(x) ll(x.size())
#define rep(i,n) for(ll i=0;i<n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define rng(i,l,r) for(ll i=l;i<r;i++)
#define gnr(i,l,r) for(ll i=r-1;i>=l;i--)
#define fore(i, a) for(auto &&i : a)
#define fore2(a, b, v) for(auto &&[a, b] : v)
#define fore3(a, b, c, v) for(auto &&[a, b, c] : v)
template<class T> bool chmin(T& a, const T& b){ if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, const T& b){ if(a >= b) return 0; a = b; return 1; }
template<class T, class U> bool chmin(T& a, const U& b){ return chmin(a, (T)b); }
template<class T, class U> bool chmax(T& a, const U& b){ return chmax(a, (T)b); }
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type>name(__VA_ARGS__)
#define VEC(type,name,size) vector<type>name(size);in(name)
#define VLL(name,size) vector<ll>name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>> name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>> name(h,vector<type>(w));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>> name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
#define SUM(...) accumulate(all(__VA_ARGS__),0LL)
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }
template<class T, class F = less<>> void sor(T& a, F b = F{}){ sort(all(a), b); }
template<class T> void uniq(T& a){ sor(a); a.erase(unique(all(a)), end(a)); }
void outb(bool x){cout<<(x?"Yes":"No")<<"\n";}
ll max(int x, ll y) { return max((ll)x, y); }
ll max(ll x, int y) { return max(x, (ll)y); }
int min(int x, ll y) { return min((ll)x, y); }
int min(ll x, int y) { return min(x, (ll)y); }
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))
ll gcd(ll a,ll b){return (b?gcd(b,a%b):a);}
vector<pll> factor(ull x){ vector<pll> ans; for(ull i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }
vector<ll> divisor(ull x){ vector<ll> ans; for(ull i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); per(i,ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
vll prime_table(ll n){vec(ll,isp,n+1,1);vll res;rng(i,2,n+1)if(isp[i]){res.pb(i);for(ll j=i*i;j<=n;j+=i)isp[j]=0;}return res;}

template <class T, class S> pair<T, S> operator-(const pair<T, S> &x) { return pair<T, S>(-x.first, -x.second); }
template <class T, class S> pair<T, S> operator-(const pair<T, S> &x, const pair<T, S> &y) { return pair<T, S>(x.fi - y.fi, x.se - y.se); }
template <class T, class S> pair<T, S> operator+(const pair<T, S> &x, const pair<T, S> &y) { return pair<T, S>(x.fi + y.fi, x.se + y.se); }
template <class T> pair<T, T> operator&(const pair<T, T> &l, const pair<T, T> &r) { return pair<T, T>(max(l.fi, r.fi), min(l.se, r.se)); }
template <class T, class S> pair<T, S> operator+=(pair<T, S> &l, const pair<T, S> &r) { return l = l + r; }
template <class T, class S> pair<T, S> operator-=(pair<T, S> &l, const pair<T, S> &r) { return l = l - r; }
template <class T> bool intersect(const pair<T, T> &l, const pair<T, T> &r) { return (l.se < r.se ? r.fi < l.se : l.fi < r.se); }

template <class T> vector<T> &operator++(vector<T> &v) {
		fore(e, v) e++;
		return v;
}
template <class T> vector<T> operator++(vector<T> &v, int) {
		auto res = v;
		fore(e, v) e++;
		return res;
}
template <class T> vector<T> &operator--(vector<T> &v) {
		fore(e, v) e--;
		return v;
}
template <class T> vector<T> operator--(vector<T> &v, int) {
		auto res = v;
		fore(e, v) e--;
		return res;
}
template <class T> vector<T> &operator+=(vector<T> &l, const vector<T> &r) {
		fore(e, r) l.eb(e);
		return l;
}

template<class... Ts> void in(Ts&... t);
[[maybe_unused]] void print(){}
template<class T, class... Ts> void print(const T& t, const Ts&... ts);
template<class... Ts> void out(const Ts&... ts){ print(ts...); cout << '\n'; }
namespace IO{
#define VOID(a) decltype(void(a))
struct S{ S(){ cin.tie(nullptr)->sync_with_stdio(0); fixed(cout).precision(12); } }S;
template<int I> struct P : P<I-1>{};
template<> struct P<0>{};
template<class T> void i(T& t){ i(t, P<3>{}); }
void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }
template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }
template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }
template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){ in(get<idx>(t)...); }
template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){ ituple(t, make_index_sequence<tuple_size<T>::value>{}); }
template<class T> void o(const T& t){ o(t, P<4>{}); }
template<size_t N> void o(const char (&t)[N], P<4>){ cout << t; }
template<class T, size_t N> void o(const T (&t)[N], P<3>){ o(t[0]); for(size_t i = 1; i < N; i++){ o(' '); o(t[i]); } }
template<class T> auto o(const T& t, P<2>) -> VOID(cout << t){ cout << t; }
template<class T> auto o(const T& t, P<1>) -> VOID(begin(t)){ bool first = 1; for(auto&& x : t) { if(first) first = 0; else o(' '); o(x); } }
template<class T, size_t... idx> void otuple(const T& t, index_sequence<idx...>){ print(get<idx>(t)...); }
template<class T> auto o(T& t, P<0>) -> VOID(tuple_size<T>{}){ otuple(t, make_index_sequence<tuple_size<T>::value>{}); }
#undef VOID
}
#define unpack(a) (void)initializer_list<int>{(a, 0)...}
template<class... Ts> void in(Ts&... t){ unpack(IO::i(t)); }
template<class T, class... Ts> void print(const T& t, const Ts&... ts){ IO::o(t); unpack(IO::o((cout << ' ', ts))); }
#undef unpack
#ifdef _MSC_VER
#include <intrin.h>
#endif
 
namespace atcoder {
 
namespace internal {
 
int ceil_pow2(int n) {
	int x = 0;
	while ((1U << x) < (unsigned int)(n)) x++;
	return x;
}
 
constexpr int bsf_constexpr(unsigned int n) {
	int x = 0;
	while (!(n & (1 << x))) x++;
	return x;
}
 
int bsf(unsigned int n) {
#ifdef _MSC_VER
	unsigned long index;
	_BitScanForward(&index, n);
	return index;
#else
	return __builtin_ctz(n);
#endif
}
 
}  // namespace internal
 
}  // namespace atcoder
 
 
#include <cassert>
#include <numeric>
#include <type_traits>
 
#ifdef _MSC_VER
#include <intrin.h>
#endif
 
 
#include <utility>
 
#ifdef _MSC_VER
#include <intrin.h>
#endif
 
namespace atcoder {
 
namespace internal {
 
constexpr long long safe_mod(long long x, long long m) {
	x %= m;
	if (x < 0) x += m;
	return x;
}
 
struct barrett {
	unsigned int _m;
	unsigned long long im;
 
	explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
 
	unsigned int umod() const { return _m; }
 
	unsigned int mul(unsigned int a, unsigned int b) const {
 
		unsigned long long z = a;
		z *= b;
#ifdef _MSC_VER
		unsigned long long x;
		_umul128(z, im, &x);
#else
		unsigned long long x =
			(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
		unsigned int v = (unsigned int)(z - x * _m);
		if (_m <= v) v += _m;
		return v;
	}
};
 
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
	if (m == 1) return 0;
	unsigned int _m = (unsigned int)(m);
	unsigned long long r = 1;
	unsigned long long y = safe_mod(x, m);
	while (n) {
		if (n & 1) r = (r * y) % _m;
		y = (y * y) % _m;
		n >>= 1;
	}
	return r;
}
 
constexpr bool is_prime_constexpr(int n) {
	if (n <= 1) return false;
	if (n == 2 || n == 7 || n == 61) return true;
	if (n % 2 == 0) return false;
	long long d = n - 1;
	while (d % 2 == 0) d /= 2;
	constexpr long long bases[3] = {2, 7, 61};
	for (long long a : bases) {
		long long t = d;
		long long y = pow_mod_constexpr(a, t, n);
		while (t != n - 1 && y != 1 && y != n - 1) {
			y = y * y % n;
			t <<= 1;
		}
		if (y != n - 1 && t % 2 == 0) {
			return false;
		}
	}
	return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
 
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
	a = safe_mod(a, b);
	if (a == 0) return {b, 0};
 
	long long s = b, t = a;
	long long m0 = 0, m1 = 1;
 
	while (t) {
		long long u = s / t;
		s -= t * u;
		m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b
 
 
		auto tmp = s;
		s = t;
		t = tmp;
		tmp = m0;
		m0 = m1;
		m1 = tmp;
	}
	if (m0 < 0) m0 += b / s;
	return {s, m0};
}
 
constexpr int primitive_root_constexpr(int m) {
	if (m == 2) return 1;
	if (m == 167772161) return 3;
	if (m == 469762049) return 3;
	if (m == 754974721) return 11;
	if (m == 998244353) return 3;
	int divs[20] = {};
	divs[0] = 2;
	int cnt = 1;
	int x = (m - 1) / 2;
	while (x % 2 == 0) x /= 2;
	for (int i = 3; (long long)(i)*i <= x; i += 2) {
		if (x % i == 0) {
			divs[cnt++] = i;
			while (x % i == 0) {
				x /= i;
			}
		}
	}
	if (x > 1) {
		divs[cnt++] = x;
	}
	for (int g = 2;; g++) {
		bool ok = true;
		for (int i = 0; i < cnt; i++) {
			if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
				ok = false;
				break;
			}
		}
		if (ok) return g;
	}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
 
unsigned long long floor_sum_unsigned(unsigned long long n,
										unsigned long long m,
										unsigned long long a,
										unsigned long long b) {
	unsigned long long ans = 0;
	while (true) {
		if (a >= m) {
			ans += n * (n - 1) / 2 * (a / m);
			a %= m;
		}
		if (b >= m) {
			ans += n * (b / m);
			b %= m;
		}
 
		unsigned long long y_max = a * n + b;
		if (y_max < m) break;
		n = (unsigned long long)(y_max / m);
		b = (unsigned long long)(y_max % m);
		std::swap(m, a);
	}
	return ans;
}
 
}  // namespace internal
 
}  // namespace atcoder
 
 
#include <cassert>
#include <numeric>
#include <type_traits>
 
namespace atcoder {
 
namespace internal {
 
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
	typename std::conditional<std::is_same<T, __int128_t>::value ||
									std::is_same<T, __int128>::value,
								std::true_type,
								std::false_type>::type;
 
template <class T>
using is_unsigned_int128 =
	typename std::conditional<std::is_same<T, __uint128_t>::value ||
									std::is_same<T, unsigned __int128>::value,
								std::true_type,
								std::false_type>::type;
 
template <class T>
using make_unsigned_int128 =
	typename std::conditional<std::is_same<T, __int128_t>::value,
								__uint128_t,
								unsigned __int128>;
 
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
													is_signed_int128<T>::value ||
													is_unsigned_int128<T>::value,
												std::true_type,
												std::false_type>::type;
 
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
												 std::is_signed<T>::value) ||
													is_signed_int128<T>::value,
												std::true_type,
												std::false_type>::type;
 
template <class T>
using is_unsigned_int =
	typename std::conditional<(is_integral<T>::value &&
								 std::is_unsigned<T>::value) ||
									is_unsigned_int128<T>::value,
								std::true_type,
								std::false_type>::type;
 
template <class T>
using to_unsigned = typename std::conditional<
	is_signed_int128<T>::value,
	make_unsigned_int128<T>,
	typename std::conditional<std::is_signed<T>::value,
								std::make_unsigned<T>,
								std::common_type<T>>::type>::type;
 
#else
 
template <class T> using is_integral = typename std::is_integral<T>;
 
template <class T>
using is_signed_int =
	typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
								std::true_type,
								std::false_type>::type;
 
template <class T>
using is_unsigned_int =
	typename std::conditional<is_integral<T>::value &&
									std::is_unsigned<T>::value,
								std::true_type,
								std::false_type>::type;
 
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
												std::make_unsigned<T>,
												std::common_type<T>>::type;
 
#endif
 
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
 
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
 
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
 
}  // namespace internal
 
}  // namespace atcoder
 
 
namespace atcoder {
 
namespace internal {
 
struct modint_base {};
struct static_modint_base : modint_base {};
 
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
 
}  // namespace internal
 
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
	using mint = static_modint;
 
	public:
	static constexpr int mod() { return m; }
	static mint raw(int v) {
		mint x;
		x._v = v;
		return x;
	}
 
	static_modint() : _v(0) {}
	template <class T, internal::is_signed_int_t<T>* = nullptr>
	static_modint(T v) {
		long long x = (long long)(v % (long long)(umod()));
		if (x < 0) x += umod();
		_v = (unsigned int)(x);
	}
	template <class T, internal::is_unsigned_int_t<T>* = nullptr>
	static_modint(T v) {
		_v = (unsigned int)(v % umod());
	}
 
	unsigned int val() const { return _v; }
 
	mint& operator++() {
		_v++;
		if (_v == umod()) _v = 0;
		return *this;
	}
	mint& operator--() {
		if (_v == 0) _v = umod();
		_v--;
		return *this;
	}
	mint operator++(int) {
		mint result = *this;
		++*this;
		return result;
	}
	mint operator--(int) {
		mint result = *this;
		--*this;
		return result;
	}
 
	mint& operator+=(const mint& rhs) {
		_v += rhs._v;
		if (_v >= umod()) _v -= umod();
		return *this;
	}
	mint& operator-=(const mint& rhs) {
		_v -= rhs._v;
		if (_v >= umod()) _v += umod();
		return *this;
	}
	mint& operator*=(const mint& rhs) {
		unsigned long long z = _v;
		z *= rhs._v;
		_v = (unsigned int)(z % umod());
		return *this;
	}
	mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
 
	mint operator+() const { return *this; }
	mint operator-() const { return mint() - *this; }
 
	mint pow(long long n) const {
		assert(0 <= n);
		mint x = *this, r = 1;
		while (n) {
			if (n & 1) r *= x;
			x *= x;
			n >>= 1;
		}
		return r;
	}
	mint inv() const {
		if (prime) {
			assert(_v);
			return pow(umod() - 2);
		} else {
			auto eg = internal::inv_gcd(_v, m);
			assert(eg.first == 1);
			return eg.second;
		}
	}
 
	friend mint operator+(const mint& lhs, const mint& rhs) {
		return mint(lhs) += rhs;
	}
	friend mint operator-(const mint& lhs, const mint& rhs) {
		return mint(lhs) -= rhs;
	}
	friend mint operator*(const mint& lhs, const mint& rhs) {
		return mint(lhs) *= rhs;
	}
	friend mint operator/(const mint& lhs, const mint& rhs) {
		return mint(lhs) /= rhs;
	}
	friend bool operator==(const mint& lhs, const mint& rhs) {
		return lhs._v == rhs._v;
	}
	friend bool operator!=(const mint& lhs, const mint& rhs) {
		return lhs._v != rhs._v;
	}
 
	private:
	unsigned int _v;
	static constexpr unsigned int umod() { return m; }
	static constexpr bool prime = internal::is_prime<m>;
};
 
template <int id> struct dynamic_modint : internal::modint_base {
	using mint = dynamic_modint;
 
	public:
	static int mod() { return (int)(bt.umod()); }
	static void set_mod(int m) {
		assert(1 <= m);
		bt = internal::barrett(m);
	}
	static mint raw(int v) {
		mint x;
		x._v = v;
		return x;
	}
 
	dynamic_modint() : _v(0) {}
	template <class T, internal::is_signed_int_t<T>* = nullptr>
	dynamic_modint(T v) {
		long long x = (long long)(v % (long long)(mod()));
		if (x < 0) x += mod();
		_v = (unsigned int)(x);
	}
	template <class T, internal::is_unsigned_int_t<T>* = nullptr>
	dynamic_modint(T v) {
		_v = (unsigned int)(v % mod());
	}
 
	unsigned int val() const { return _v; }
 
	mint& operator++() {
		_v++;
		if (_v == umod()) _v = 0;
		return *this;
	}
	mint& operator--() {
		if (_v == 0) _v = umod();
		_v--;
		return *this;
	}
	mint operator++(int) {
		mint result = *this;
		++*this;
		return result;
	}
	mint operator--(int) {
		mint result = *this;
		--*this;
		return result;
	}
 
	mint& operator+=(const mint& rhs) {
		_v += rhs._v;
		if (_v >= umod()) _v -= umod();
		return *this;
	}
	mint& operator-=(const mint& rhs) {
		_v += mod() - rhs._v;
		if (_v >= umod()) _v -= umod();
		return *this;
	}
	mint& operator*=(const mint& rhs) {
		_v = bt.mul(_v, rhs._v);
		return *this;
	}
	mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
 
	mint operator+() const { return *this; }
	mint operator-() const { return mint() - *this; }
 
	mint pow(long long n) const {
		assert(0 <= n);
		mint x = *this, r = 1;
		while (n) {
			if (n & 1) r *= x;
			x *= x;
			n >>= 1;
		}
		return r;
	}
	mint inv() const {
		auto eg = internal::inv_gcd(_v, mod());
		assert(eg.first == 1);
		return eg.second;
	}
 
	friend mint operator+(const mint& lhs, const mint& rhs) {
		return mint(lhs) += rhs;
	}
	friend mint operator-(const mint& lhs, const mint& rhs) {
		return mint(lhs) -= rhs;
	}
	friend mint operator*(const mint& lhs, const mint& rhs) {
		return mint(lhs) *= rhs;
	}
	friend mint operator/(const mint& lhs, const mint& rhs) {
		return mint(lhs) /= rhs;
	}
	friend bool operator==(const mint& lhs, const mint& rhs) {
		return lhs._v == rhs._v;
	}
	friend bool operator!=(const mint& lhs, const mint& rhs) {
		return lhs._v != rhs._v;
	}
 
	private:
	unsigned int _v;
	static internal::barrett bt;
	static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
 
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
 
namespace internal {
 
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
 
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
 
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
 
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
 
}  // namespace internal
 
}  // namespace atcoder
 
 
namespace atcoder {
 
namespace internal {
 
template <class mint,
			int g = internal::primitive_root<mint::mod()>,
			internal::is_static_modint_t<mint>* = nullptr>
struct fft_info {
	static constexpr int rank2 = bsf_constexpr(mint::mod() - 1);
	std::array<mint, rank2 + 1> root;   // root[i]^(2^i) == 1
	std::array<mint, rank2 + 1> iroot;  // root[i] * iroot[i] == 1
 
	std::array<mint, std::max(0, rank2 - 2 + 1)> rate2;
	std::array<mint, std::max(0, rank2 - 2 + 1)> irate2;
 
	std::array<mint, std::max(0, rank2 - 3 + 1)> rate3;
	std::array<mint, std::max(0, rank2 - 3 + 1)> irate3;
 
	fft_info() {
		root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
		iroot[rank2] = root[rank2].inv();
		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 - 2; i++) {
				rate2[i] = root[i + 2] * prod;
				irate2[i] = iroot[i + 2] * iprod;
				prod *= iroot[i + 2];
				iprod *= root[i + 2];
			}
		}
		{
			mint prod = 1, iprod = 1;
			for (int i = 0; i <= rank2 - 3; i++) {
				rate3[i] = root[i + 3] * prod;
				irate3[i] = iroot[i + 3] * iprod;
				prod *= iroot[i + 3];
				iprod *= root[i + 3];
			}
		}
	}
};
 
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly(std::vector<mint>& a) {
	int n = int(a.size());
	int h = internal::ceil_pow2(n);
 
	static const fft_info<mint> info;
 
	int len = 0;  // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
	while (len < h) {
		if (h - len == 1) {
			int p = 1 << (h - len - 1);
			mint rot = 1;
			for (int s = 0; s < (1 << len); s++) {
				int offset = s << (h - len);
				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;
				}
				if (s + 1 != (1 << len))
					rot *= info.rate2[bsf(~(unsigned int)(s))];
			}
			len++;
		} else {
			int p = 1 << (h - len - 2);
			mint rot = 1, imag = info.root[2];
			for (int s = 0; s < (1 << len); s++) {
				mint rot2 = rot * rot;
				mint rot3 = rot2 * rot;
				int offset = s << (h - len);
				for (int i = 0; i < p; i++) {
					auto mod2 = 1ULL * mint::mod() * mint::mod();
					auto a0 = 1ULL * a[i + offset].val();
					auto a1 = 1ULL * a[i + offset + p].val() * rot.val();
					auto a2 = 1ULL * a[i + offset + 2 * p].val() * rot2.val();
					auto a3 = 1ULL * a[i + offset + 3 * p].val() * rot3.val();
					auto a1na3imag =
						1ULL * mint(a1 + mod2 - a3).val() * imag.val();
					auto na2 = mod2 - a2;
					a[i + offset] = a0 + a2 + a1 + a3;
					a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
					a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
					a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
				}
				if (s + 1 != (1 << len))
					rot *= info.rate3[bsf(~(unsigned int)(s))];
			}
			len += 2;
		}
	}
}
 
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(std::vector<mint>& a) {
	int n = int(a.size());
	int h = internal::ceil_pow2(n);
 
	static const fft_info<mint> info;
 
	int len = h;  // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
	while (len) {
		if (len == 1) {
			int p = 1 << (h - len);
			mint irot = 1;
			for (int s = 0; s < (1 << (len - 1)); s++) {
				int offset = s << (h - len + 1);
				for (int i = 0; i < p; i++) {
					auto l = a[i + offset];
					auto r = a[i + offset + p];
					a[i + offset] = l + r;
					a[i + offset + p] =
						(unsigned long long)(mint::mod() + l.val() - r.val()) *
						irot.val();
					;
				}
				if (s + 1 != (1 << (len - 1)))
					irot *= info.irate2[bsf(~(unsigned int)(s))];
			}
			len--;
		} else {
			int p = 1 << (h - len);
			mint irot = 1, iimag = info.iroot[2];
			for (int s = 0; s < (1 << (len - 2)); s++) {
				mint irot2 = irot * irot;
				mint irot3 = irot2 * irot;
				int offset = s << (h - len + 2);
				for (int i = 0; i < p; i++) {
					auto a0 = 1ULL * a[i + offset + 0 * p].val();
					auto a1 = 1ULL * a[i + offset + 1 * p].val();
					auto a2 = 1ULL * a[i + offset + 2 * p].val();
					auto a3 = 1ULL * a[i + offset + 3 * p].val();
 
					auto a2na3iimag =
						1ULL *
						mint((mint::mod() + a2 - a3) * iimag.val()).val();
 
					a[i + offset] = a0 + a1 + a2 + a3;
					a[i + offset + 1 * p] =
						(a0 + (mint::mod() - a1) + a2na3iimag) * irot.val();
					a[i + offset + 2 * p] =
						(a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) *
						irot2.val();
					a[i + offset + 3 * p] =
						(a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) *
						irot3.val();
				}
				if (s + 1 != (1 << (len - 2)))
					irot *= info.irate3[bsf(~(unsigned int)(s))];
			}
			len -= 2;
		}
	}
}
 
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution_naive(const std::vector<mint>& a,
									const std::vector<mint>& b) {
	int n = int(a.size()), m = int(b.size());
	std::vector<mint> ans(n + m - 1);
	if (n < m) {
		for (int j = 0; j < m; j++) {
			for (int i = 0; i < n; i++) {
				ans[i + j] += a[i] * b[j];
			}
		}
	} else {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				ans[i + j] += a[i] * b[j];
			}
		}
	}
	return ans;
}
 
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution_fft(std::vector<mint> a, std::vector<mint> b) {
	int n = int(a.size()), m = int(b.size());
	int z = 1 << internal::ceil_pow2(n + m - 1);
	a.resize(z);
	internal::butterfly(a);
	b.resize(z);
	internal::butterfly(b);
	for (int i = 0; i < z; i++) {
		a[i] *= b[i];
	}
	internal::butterfly_inv(a);
	a.resize(n + m - 1);
	mint iz = mint(z).inv();
	for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
	return a;
}
 
}  // namespace internal
 
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(std::vector<mint>&& a, std::vector<mint>&& b) {
	int n = int(a.size()), m = int(b.size());
	if (!n || !m) return {};
	if (std::min(n, m) <= 60) return convolution_naive(a, b);
	return internal::convolution_fft(a, b);
}
 
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(const std::vector<mint>& a,
								const std::vector<mint>& b) {
	int n = int(a.size()), m = int(b.size());
	if (!n || !m) return {};
	if (std::min(n, m) <= 60) return convolution_naive(a, b);
	return internal::convolution_fft(a, b);
}
 
template <unsigned int mod = 998244353,
			class T,
			std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {
	int n = int(a.size()), m = int(b.size());
	if (!n || !m) return {};
 
	using mint = static_modint<mod>;
	std::vector<mint> a2(n), b2(m);
	for (int i = 0; i < n; i++) {
		a2[i] = mint(a[i]);
	}
	for (int i = 0; i < m; i++) {
		b2[i] = mint(b[i]);
	}
	auto c2 = convolution(move(a2), move(b2));
	std::vector<T> c(n + m - 1);
	for (int i = 0; i < n + m - 1; i++) {
		c[i] = c2[i].val();
	}
	return c;
}
 
std::vector<long long> convolution_ll(const std::vector<long long>& a,
										const std::vector<long long>& b) {
	int n = int(a.size()), m = int(b.size());
	if (!n || !m) return {};
 
	static constexpr unsigned long long MOD1 = 754974721;  // 2^24
	static constexpr unsigned long long MOD2 = 167772161;  // 2^25
	static constexpr unsigned long long MOD3 = 469762049;  // 2^26
	static constexpr unsigned long long M2M3 = MOD2 * MOD3;
	static constexpr unsigned long long M1M3 = MOD1 * MOD3;
	static constexpr unsigned long long M1M2 = MOD1 * MOD2;
	static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
 
	static constexpr unsigned long long i1 =
		internal::inv_gcd(MOD2 * MOD3, MOD1).second;
	static constexpr unsigned long long i2 =
		internal::inv_gcd(MOD1 * MOD3, MOD2).second;
	static constexpr unsigned long long i3 =
		internal::inv_gcd(MOD1 * MOD2, MOD3).second;
 
	auto c1 = convolution<MOD1>(a, b);
	auto c2 = convolution<MOD2>(a, b);
	auto c3 = convolution<MOD3>(a, b);
 
	std::vector<long long> c(n + m - 1);
	for (int i = 0; i < n + m - 1; i++) {
		unsigned long long x = 0;
		x += (c1[i] * i1) % MOD1 * M2M3;
		x += (c2[i] * i2) % MOD2 * M1M3;
		x += (c3[i] * i3) % MOD3 * M1M2;
		long long diff =
			c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
		if (diff < 0) diff += MOD1;
		static constexpr unsigned long long offset[5] = {
			0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
		x -= offset[diff % 5];
		c[i] = x;
	}
 
	return c;
}
 
}  // namespace atcoder
 

using namespace atcoder;
using mint=modint998244353;
using vmint=vector<mint>;

// combination mod prime
// https://youtu.be/8uowVvQ_-Mo?t=6002
// https://youtu.be/Tgd_zLfRZOQ?t=9928
struct modinv {
	int n; vector<mint> d;
	modinv(): n(2), d({0,1}) {}
	mint operator()(int i) {
	while (n <= i) d.push_back(-d[mint::mod()%n]*(mint::mod()/n)), ++n;
	return d[i];
	}
	mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
	int n; vector<mint> d;
	modfact(): n(2), d({1,1}) {}
	mint operator()(int i) {
	while (n <= i) d.push_back(d.back()*n), ++n;
	return d[i];
	}
	mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {
	int n; vector<mint> d;
	modfactinv(): n(2), d({1,1}) {}
	mint operator()(int i) {
	while (n <= i) d.push_back(d.back()*invs(n)), ++n;
	return d[i];
	}
	mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {
	if (n < k || k < 0) return 0;
	return facts(n)*ifacts(k)*ifacts(n-k);
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	LL(n);
	vec(ll,p,n);
	rng(i,1,n)cin>>p[i];
	p--;
	vec(ll,d,n,0);
	vec(ll,s,n,0);
	d[0]=0;
	rng(i,1,n){
		d[i]=d[p[i]]+1;
	}
	vv(mint,dp,n);
	per(i,n){
		dp[i].resize(d[i]+2);
		rep(j,d[i]+2)dp[i][j]=0;
		dp[i][0]=1;
	}
	per(i,n){
		{
			vec(mint,cop,d[i]+2,0);
			rep(j,d[i]+2)rng(k,j,d[i]+2){
				cop[k]+=dp[i][j]*comb(s[i]+k,k-j);
			}
			swap(dp[i],cop);
		}
		rep(j,d[i]+1)dp[i][j]=dp[i][j+1];
		dp[i][d[i]+1]=0;
		s[i]++;
		if(i==0)break;

		{
			vec(mint,cop,d[p[i]]+2,0);
			rep(j,d[i]+1)rep(k,d[p[i]]+2-j){
				cop[k+j]+=dp[i][j]*dp[p[i]][k]*comb(s[i]+j+s[p[i]]+k,j+s[i]);
			}
			swap(dp[p[i]],cop);
		}
		s[p[i]]+=s[i];
	}
	out(dp[0][0].val());
	// rep(i,n){
	// 	cout<<i<<":";
	// 	rep(j,si(dp[i])){
	// 		cout<<dp[i][j].val()<<" ";
	// 	}
	// 	cout<<endl;
	// }
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3640kb

input:

3
1 1

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

3
1 2

output:

16

result:

ok 1 number(s): "16"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

4
1 2 3

output:

125

result:

ok 1 number(s): "125"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

8
1 2 3 1 3 4 3

output:

1198736

result:

ok 1 number(s): "1198736"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

15
1 2 2 2 2 3 3 2 7 7 3 10 3 13

output:

938578089

result:

ok 1 number(s): "938578089"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

100
1 1 1 3 5 5 5 5 9 9 3 2 11 14 9 8 16 8 18 18 20 10 12 2 22 21 27 28 29 6 2 21 2 20 21 11 16 19 9 25 39 8 14 19 6 38 22 19 25 13 3 27 19 51 23 18 45 30 30 22 24 16 12 61 42 24 3 3 53 40 59 72 6 23 1 64 41 13 71 75 30 64 11 55 70 60 32 84 25 4 69 49 15 42 72 31 71 23 58

output:

426063005

result:

ok 1 number(s): "426063005"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

500
1 1 3 3 3 4 3 5 2 5 8 4 12 11 8 14 1 12 7 16 7 7 17 10 8 26 7 4 13 21 6 7 20 34 35 24 25 23 25 39 20 30 13 43 43 35 45 34 7 4 11 23 11 43 35 27 6 2 3 11 37 42 27 37 62 42 41 43 63 4 57 17 18 8 11 23 72 74 41 49 76 44 50 81 46 18 45 5 8 88 77 27 35 11 52 18 32 85 57 25 32 22 39 35 43 26 63 7 62 2...

output:

105022837

result:

ok 1 number(s): "105022837"

Test #8:

score: 0
Accepted
time: 3ms
memory: 4116kb

input:

2000
1 1 2 4 4 4 1 5 9 4 5 9 9 4 15 1 11 18 11 2 4 22 10 23 18 15 6 25 25 19 15 28 32 17 29 24 35 11 32 20 25 8 7 12 27 29 40 21 23 47 24 8 6 24 53 43 9 10 48 18 16 16 10 45 42 33 20 27 33 47 41 22 37 4 38 23 8 29 14 54 49 74 60 56 45 32 11 4 58 16 71 29 49 32 31 95 38 2 89 73 91 65 26 12 94 35 1 73...

output:

510693456

result:

ok 1 number(s): "510693456"

Test #9:

score: 0
Accepted
time: 13ms
memory: 4876kb

input:

10000
1 2 1 1 2 1 4 3 5 6 1 8 8 3 2 15 4 14 10 9 9 15 17 5 21 9 11 24 17 20 17 16 4 13 10 10 36 2 8 29 34 40 8 13 27 5 1 18 16 4 40 47 4 8 9 1 54 40 38 41 46 52 31 21 21 14 49 49 46 22 14 59 71 37 30 18 37 30 36 56 24 56 48 17 75 68 68 6 65 87 48 52 8 26 94 89 29 32 40 77 51 6 9 78 1 48 100 69 85 89...

output:

158503783

result:

ok 1 number(s): "158503783"

Test #10:

score: 0
Accepted
time: 238ms
memory: 16800kb

input:

100000
1 1 1 2 4 4 7 8 6 9 7 8 12 10 15 15 9 12 9 16 9 13 11 18 11 8 6 23 22 28 8 29 12 24 14 9 33 5 17 4 33 29 41 19 37 34 19 41 15 21 20 13 36 25 34 38 2 56 33 53 40 36 26 28 34 7 19 66 35 43 52 47 53 32 61 11 55 10 78 75 43 80 71 16 20 68 27 41 80 33 69 50 71 7 5 26 24 78 62 17 76 15 10 11 56 64 ...

output:

937583571

result:

ok 1 number(s): "937583571"

Test #11:

score: 0
Accepted
time: 190ms
memory: 15976kb

input:

100000
1 2 1 2 5 3 5 4 6 8 2 1 6 2 5 5 1 6 12 12 15 11 23 3 4 13 3 22 8 5 13 12 10 9 6 27 37 22 14 24 12 26 15 30 2 27 43 4 47 9 42 5 33 26 13 54 17 32 23 15 34 36 14 49 41 25 14 35 22 35 51 50 17 22 38 54 71 41 69 44 61 18 77 3 78 53 74 70 67 8 18 10 88 2 1 74 36 15 76 62 7 70 89 24 72 77 15 44 49 ...

output:

264669337

result:

ok 1 number(s): "264669337"

Test #12:

score: 0
Accepted
time: 204ms
memory: 16164kb

input:

100000
1 1 3 2 2 6 7 6 3 4 10 1 2 14 12 16 3 2 19 20 3 2 12 17 6 17 16 9 27 18 23 21 2 31 18 13 6 17 39 13 25 18 29 11 42 17 10 34 22 9 33 31 52 45 5 54 43 52 56 4 5 47 63 51 41 54 28 65 31 70 2 63 59 53 53 40 39 5 46 71 13 6 41 31 57 4 82 62 78 59 87 72 92 9 5 69 90 92 19 15 78 41 39 23 12 1 47 49 ...

output:

399299126

result:

ok 1 number(s): "399299126"

Test #13:

score: 0
Accepted
time: 209ms
memory: 16344kb

input:

100000
1 1 1 4 5 5 3 7 6 1 7 8 8 11 11 13 7 7 1 1 13 20 21 22 22 19 8 2 29 28 4 27 8 16 30 4 5 14 21 35 29 32 35 22 14 23 41 24 33 12 31 39 4 40 24 5 38 46 20 23 37 5 27 39 32 41 26 50 33 15 50 40 40 23 52 58 31 16 25 60 36 72 29 33 48 1 82 1 25 57 15 69 5 78 29 81 36 46 97 38 15 7 39 51 19 80 29 77...

output:

58289876

result:

ok 1 number(s): "58289876"

Test #14:

score: 0
Accepted
time: 184ms
memory: 15948kb

input:

100000
1 1 1 1 4 1 7 2 4 8 6 3 2 9 15 15 5 5 7 1 12 15 4 19 7 8 15 21 26 28 13 20 14 21 30 27 21 2 3 14 1 33 33 8 41 25 11 38 35 35 35 5 16 29 16 9 24 39 13 12 3 58 20 44 3 43 53 57 13 23 44 43 14 4 23 69 27 73 22 55 25 64 52 40 71 48 56 56 8 68 27 30 92 46 18 7 58 30 65 69 61 55 38 92 33 102 80 2 2...

output:

861492056

result:

ok 1 number(s): "861492056"

Test #15:

score: 0
Accepted
time: 197ms
memory: 16180kb

input:

100000
1 1 2 3 2 2 5 8 7 4 1 3 5 11 15 2 9 8 19 5 19 11 15 19 19 11 26 3 13 15 30 1 18 28 16 33 9 23 15 2 3 36 7 11 44 31 40 15 46 7 8 5 23 36 22 12 2 28 23 14 11 40 21 18 60 24 32 42 50 57 21 27 60 54 9 63 76 56 22 59 40 41 31 58 27 68 10 45 70 54 46 29 68 6 4 61 11 7 60 56 69 92 69 5 88 71 46 21 7...

output:

528382031

result:

ok 1 number(s): "528382031"

Test #16:

score: 0
Accepted
time: 193ms
memory: 16012kb

input:

100000
1 1 3 1 1 5 4 5 3 3 6 4 1 8 10 15 5 14 5 16 9 13 14 13 8 15 26 17 1 21 11 31 18 16 21 27 14 32 9 27 30 30 3 41 33 26 47 25 26 6 24 15 11 15 6 49 48 25 23 56 3 38 31 28 54 14 17 45 60 64 24 21 14 30 20 30 38 8 13 43 37 11 83 78 75 12 30 66 37 85 24 77 72 71 49 78 88 73 25 68 19 51 79 43 93 21 ...

output:

316789948

result:

ok 1 number(s): "316789948"

Test #17:

score: 0
Accepted
time: 209ms
memory: 16348kb

input:

100000
1 2 1 2 5 4 3 8 5 8 7 6 3 10 15 12 10 4 17 15 16 13 11 1 15 10 4 16 21 11 25 11 15 4 9 21 18 16 17 29 39 3 39 1 34 5 1 14 44 5 15 16 12 15 42 28 45 32 8 33 7 32 61 9 8 34 54 66 59 61 51 51 37 40 30 61 36 36 45 18 75 27 27 45 45 53 50 77 26 89 72 41 15 18 56 53 64 6 34 33 9 90 41 50 8 4 58 101...

output:

846732448

result:

ok 1 number(s): "846732448"

Test #18:

score: 0
Accepted
time: 178ms
memory: 15980kb

input:

100000
1 1 1 3 3 6 5 7 1 3 11 6 3 2 4 4 12 1 6 10 15 8 8 20 24 10 3 5 25 4 10 13 18 30 19 11 9 6 8 24 16 5 17 2 42 33 35 3 26 42 7 42 30 17 6 41 57 53 8 19 41 50 4 16 13 45 28 50 53 22 20 2 9 30 62 25 43 76 2 41 67 74 16 2 43 64 17 28 61 15 35 33 12 60 29 64 51 33 16 18 16 15 45 18 77 40 10 87 70 72...

output:

994347719

result:

ok 1 number(s): "994347719"

Test #19:

score: 0
Accepted
time: 200ms
memory: 16144kb

input:

100000
1 1 1 4 3 3 5 8 8 1 4 9 9 14 6 12 5 3 2 9 14 4 15 11 14 14 12 18 3 22 25 1 23 1 15 8 21 35 31 34 15 23 30 13 32 18 22 33 32 18 36 46 36 27 45 16 4 35 48 12 29 1 59 64 33 12 4 1 53 8 29 16 18 67 75 7 54 18 74 21 55 69 47 54 42 56 2 85 3 90 81 42 15 90 9 41 72 68 43 58 28 87 38 22 39 29 26 44 2...

output:

946042832

result:

ok 1 number(s): "946042832"

Test #20:

score: 0
Accepted
time: 73ms
memory: 8332kb

input:

40000
1 2 2 4 1 6 5 3 3 6 3 3 4 6 10 12 1 18 18 4 11 3 9 14 25 13 14 18 4 3 1 6 13 16 9 17 37 13 38 7 10 36 13 8 22 3 17 1 20 12 33 37 8 10 25 35 41 52 10 35 36 59 20 25 32 62 18 5 3 22 66 13 2 52 38 30 62 18 35 77 51 58 32 34 44 2 70 85 46 2 80 84 67 91 91 80 19 13 42 99 75 36 38 51 62 93 96 37 96 ...

output:

599775439

result:

ok 1 number(s): "599775439"

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-01 20:11:56 | OpenSource Project