QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288970 | #7864. Random Tree Parking | ucup-team896# | AC ✓ | 62ms | 18712kb | C++23 | 10.4kb | 2023-12-23 14:33:13 | 2023-12-23 14:33:13 |
Judging History
answer
/*
* @Author: cmk666
* @Created time: 2023-12-23 14:15:26
* @Last Modified time: 2023-12-23 14:32:54
*/
#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
#ifdef LOCAL
#include"debug.h"
#else
#define D(...) ((void)0)
#endif
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
namespace FastIO
{
// ------------------------------
// #define IN_HAS_NEG
// #define OUT_HAS_NEG
// #define CHK_EOF
// #define DISABLE_MMAP
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if ( defined(LOCAL) || defined(_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include<sys/mman.h>
#endif
#ifdef LOCAL
inline char gc() { return getchar(); }
inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
INLINE_V constexpr int _READ_SIZE = 1 << 18;
INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc()
{
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) )
{
_read_ptr = _read_buffer;
_read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
#ifdef CHK_EOF
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
#endif
}
return *_read_ptr++;
}
#else
INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
inline char gc() { return *_read_ptr++; }
#endif
INLINE_V constexpr int _WRITE_SIZE = 1 << 18;
INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
inline void pc(char c)
{
*_write_ptr++ = c;
if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) )
{
fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
_write_ptr = _write_buffer;
}
}
INLINE_V struct _auto_flush
{
inline ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
} _auto_flush;
#endif
#ifdef CHK_EOF
inline constexpr bool _isdigit(char c) { return ( c & 16 ) && c != EOF; }
inline constexpr bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
inline constexpr bool _isdigit(char c) { return c & 16; }
inline constexpr bool _isgraph(char c) { return c > 32; }
#endif
template < class T >
INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer;
template < class T >
INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed;
template < class T >
INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >;
template <> INLINE_V constexpr bool _is_integer < __int128 > = true;
template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true;
template <> INLINE_V constexpr bool _is_signed < __int128 > = true;
template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true;
#undef INLINE_V
inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); }
inline void read_cstr(char *s)
{
char c = gc(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) *s++ = c, c = gc();
*s = 0;
}
inline void read(string &s)
{
char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) s.push_back(c), c = gc();
}
#ifdef IN_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void read(T &x)
{
char c = gc(); bool f = true; x = 0;
while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); }
if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
else while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc();
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void read(T &x)
{
char c = gc(); while ( !_isdigit(c) ) c = gc();
x = 0; while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
}
inline void write(char c) { pc(c); }
inline void write_cstr(const char *s) { while ( *s ) pc(*s++); }
inline void write(const string &s) { for ( char c : s ) pc(c); }
#ifdef OUT_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
if ( x >= 0 ) do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); }
while ( digits ) pc(buffer[--digits]);
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
while ( digits ) pc(buffer[--digits]);
}
template < int N > struct _tuple_io_helper
{
template < class ...T >
static inline void _read(tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); }
};
template <> struct _tuple_io_helper < 1 >
{
template < class ...T >
static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); }
};
template < class ...T >
inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); }
template < class ...T >
inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); }
template < class T1, class T2 >
inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
template < class T1, class T2 >
inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); }
template < class T1, class ...T2 >
inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
template < class ...T >
inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template < class T1, class ...T2 >
inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
template < class ...T >
inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template < class T >
inline void print(const T &x) { write(x); }
inline void print_cstr(const char *x) { write_cstr(x); }
template < class T1, class ...T2 >
inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template < class ...T >
inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); }
inline void println() { pc(10); }
inline void println_cstr() { pc(10); }
template < class ...T >
inline void println(const T &...x) { print(x...), pc(10); }
template < class ...T >
inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); }
}
using namespace FastIO;
template < int P > class Modint
{
using MI = Modint;
inline Modint(int x, int) : v(x) {}
inline static int add(int x) { return x < P ? x : x - P; }
inline static int sub(int x) { return x >= 0 ? x : x + P; }
public:
int v;
inline Modint() : v(0) {}
inline Modint(const MI &x) : v(x.v) {}
template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 >
inline Modint(T x) : v(sub(x % P)) {}
template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 >
explicit inline operator T()const { return v; }
inline friend bool operator==(const MI &x, const MI &y) { return x.v == y.v; }
inline friend bool operator!=(const MI &x, const MI &y) { return x.v != y.v; }
inline MI &operator=(const MI &x) { v = x.v; return *this; }
inline MI &operator++() { v < P - 1 ? v++ : v = 0; return *this; }
inline MI operator++(int) { MI x = *this; v < P - 1 ? v++ : v = 0; return x; }
inline MI &operator--() { v ? v-- : v = P - 1; return *this; }
inline MI operator--(int) { MI x = *this; v ? v-- : v = P - 1; return x; }
inline MI operator-()const { return MI(v ? P - v : 0, 0); }
inline friend MI operator+(const MI &x, const MI &y) { return MI(add(x.v + y.v), 0); }
inline friend MI operator-(const MI &x, const MI &y) { return MI(sub(x.v - y.v), 0); }
inline friend MI operator*(const MI &x, const MI &y) { return MI(1ll * x.v * y.v % P, 0); }
inline friend MI operator/(const MI &x, const MI &y) { return x * y.inv(); }
inline MI &operator+=(const MI &x) { v = add(v + x.v); return *this; }
inline MI &operator-=(const MI &x) { v = sub(v - x.v); return *this; }
inline MI &operator*=(const MI &x) { v = 1ll * v * x.v % P; return *this; }
inline MI &operator/=(const MI &x) { return *this *= x.inv(); }
template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 >
inline MI qpow(T y)const
{ MI x = *this, z = 1; for ( ; y ; y >>= 1, x *= x ) if ( y & 1 ) z *= x; return z; }
template < class T, enable_if_t < numeric_limits < T >::is_integer, int > = 0 >
inline friend MI qpow(const MI &x, T y) { return x.qpow(y); }
inline MI inv()const { assert(v); return qpow(P - 2); }
inline friend MI inv(const MI &x) { return x.inv(); }
inline friend istream &operator>>(istream &is, MI &x) { return is >> x.v; }
inline friend ostream &operator<<(ostream &os, const MI &x) { return os << x.v; }
};
using MI = Modint < 998244353 >;
struct binom
{
MI fac[100009], ifac[100009];
inline binom()
{
constexpr int n = sizeof(fac) / sizeof(*fac) - 1;
fac[0] = 1; For(i, 1, n) fac[i] = i * fac[i - 1];
ifac[n] = inv(fac[n]); Fol(i, n, 1) ifac[i - 1] = i * ifac[i];
}
} binom;
inline MI fac(int x) { return binom.fac[x]; }
inline MI ifac(int x) { return binom.ifac[x]; }
inline MI c(int x, int y) { return x >= y && y >= 0 ? fac(x) * ifac(y) * ifac(x - y) : 0; }
int n, f, d[100009]; vector < int > g[100009]; vector < MI > dp[100009], dq;
int main()
{
read(n), d[1] = 1;
For(i, 2, n) read(f), d[i] = d[f] + 1, g[f].push_back(i);
Fol(u, n, 1)
{
dp[u].resize(d[u] + 1);
For(i, 0, d[u]) dp[u][i] = ifac(i);
for ( int v : g[u] )
{
dq = dp[u], fill(dp[u].begin(), dp[u].end(), 0);
For(i, 1, d[v]) For(j, 0, d[u] + 1 - i) dp[u][i + j - 1] += dp[v][i] * dq[j];
}
}
return println(( dp[1][1] * fac(n) ).v), 0;
}
// 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏
// 伊娜可爱捏 伊娜贴贴捏
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9264kb
input:
3 1 1
output:
12
result:
ok 1 number(s): "12"
Test #2:
score: 0
Accepted
time: 3ms
memory: 9560kb
input:
3 1 2
output:
16
result:
ok 1 number(s): "16"
Test #3:
score: 0
Accepted
time: 0ms
memory: 9536kb
input:
4 1 2 3
output:
125
result:
ok 1 number(s): "125"
Test #4:
score: 0
Accepted
time: 3ms
memory: 9084kb
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: 9156kb
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: 3ms
memory: 9340kb
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: 3ms
memory: 9496kb
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: 9636kb
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: 3ms
memory: 10236kb
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: 61ms
memory: 18712kb
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: 54ms
memory: 18000kb
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: 58ms
memory: 18068kb
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: 56ms
memory: 18252kb
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: 53ms
memory: 17884kb
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: 59ms
memory: 18052kb
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: 50ms
memory: 17960kb
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: 62ms
memory: 18296kb
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: 51ms
memory: 17788kb
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: 62ms
memory: 18212kb
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: 14ms
memory: 12492kb
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