QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729173 | #9566. Topology | ucup-team045# | WA | 12ms | 199596kb | C++20 | 4.6kb | 2024-11-09 16:37:50 | 2024-11-09 16:37:51 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<cassert>
#include<stdint.h>
using namespace std;
using LL = long long;
template<const int T>
struct ModInt {
const static int mod = T;
int x;
ModInt(int x = 0) : x(x % mod) {}
ModInt(long long x) : x(int(x % mod)) {}
int val() { return x; }
ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
bool operator == (const ModInt &a) const { return x == a.x; };
bool operator != (const ModInt &a) const { return x != a.x; };
void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
void operator /= (const ModInt &a) { *this = *this / a; }
friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}
friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}
friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}
ModInt pow(int64_t n) const {
ModInt res(1), mul(x);
while(n){
if (n & 1) res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
ModInt inv() const {
int a = x, b = mod, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
if (u < 0) u += mod;
return u;
}
};
using mint = ModInt<998244353>;
const int maxn = 5005;
vector<int> g[maxn];
int sz[maxn], dep[maxn];
mint f[maxn], mul[maxn], fact[maxn];
int n;
void dfs1(int u){
mul[u] = 1;
sz[u] = 1;
for(auto j : g[u]){
dfs1(j);
sz[u] += sz[j];
mul[u] *= mul[j];
}
mul[u] *= sz[u];
f[u] = fact[sz[u]] / mul[u];
}
// dp[u][i] : u正好在排第i的方案数(不包括u当前子树内点)
mint dp[maxn][maxn], C[maxn][maxn];
mint ans[maxn];
mint get(int x, int y){
if (y == 0){
return (x == 0 ? 1 : 0);
}
// cout << x + y - 1 << ' ' << y - 1 << '\n';
// assert(x + y - 1 <= n and x + y - 1 >= 0);
if (y - 1 < 0) return 0;
return C[x + y - 1][y - 1];
}
void dfs2(int u){
// cout << u << ":\n";
// for(int i = 1; i <= n; i++) cout << dp[u][i] << " \n"[i == n];
const int s = g[u].size();
vector<mint> pre(s), suf(s);
for(int i = 0; i < s; i++){
pre[i] = suf[i] = f[g[u][i]];
}
for(int i = 1; i < s; i++) pre[i] *= pre[i - 1];
for(int i = s - 2; i >= 0; i--) suf[i] *= suf[i + 1];
for(int x = 0; x < s; x++){
int j = g[u][x];
mint t = (x - 1 >= 0 ? pre[x - 1] : 1) * (x + 1 < s ? suf[x + 1] : 1);
mint sum = 0;
for(int i = 1; i <= n; i++){
dp[j][i] = sum;
// [i, n - sz[u] + 1]
if (dp[u][i].val() != 0) sum += dp[u][i] * t * get(sz[u] - sz[j] - 1, n - sz[u] + 1 - i + 1);
}
// 当前点数是 n - sz[j] + 1(包括j本身)
// 后面的点只能在i后面
// [j, n - sz[j] + 1]
if (dp[j][j].val() != 0) ans[j] = dp[j][j] * f[j] * get(sz[j] - 1, n - sz[j] + 1 - j + 1);
dfs2(j);
}
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n;
for(int i = 2; i <= n; i++){
int x;
cin >> x;
g[x].push_back(i);
}
for(int i = 0; i <= n; i++){
for(int j = 0; j <= i; j++){
if (!j) C[i][j] = 1;
else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
fact[0] = 1;
for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
dep[1] = 1;
dfs1(1);
ans[1] = f[1];
dp[1][1] = 1;
dfs2(1);
for(int i = 1; i <= n; i++){
cout << ans[i] << " \n"[i == n];
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 199372kb
input:
4 1 1 2
output:
3 2 1 2
result:
ok 4 number(s): "3 2 1 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 199596kb
input:
9 1 1 2 2 3 3 4 5
output:
672 420 180 160 152 108 120 170 210
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 199336kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: 0
Accepted
time: 12ms
memory: 199424kb
input:
500 1 2 3 4 5 6 7 7 8 10 8 10 11 4 11 12 12 17 15 13 21 21 22 5 16 9 24 28 28 19 29 27 17 33 23 3 33 27 30 9 25 34 16 26 30 34 46 45 41 14 43 49 43 35 39 37 26 48 52 58 51 56 51 55 19 48 63 36 67 69 54 60 71 61 29 40 32 77 73 55 66 42 77 72 71 69 62 83 46 64 88 39 83 36 89 94 47 98 57 61 38 80 78 88...
output:
331058271 331058271 107893248 201481008 579367731 934007150 548415590 60830816 948776140 565765713 126668425 603509050 491206892 433369091 271511598 706737964 70425819 69672788 713120782 734952162 267434947 720007515 670449595 828144080 372921049 434477621 877300187 307269573 636190001 793011806 327...
result:
ok 500 numbers
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 199464kb
input:
500 1 2 3 4 5 2 6 8 9 10 11 12 13 14 15 16 7 18 19 17 21 20 22 24 25 26 23 27 29 30 2 28 31 34 35 36 37 38 39 33 40 42 41 43 45 46 17 47 49 35 50 52 44 53 9 55 54 57 58 59 61 60 62 64 65 66 67 68 69 70 63 71 27 73 25 70 75 78 79 80 75 80 81 84 72 86 87 85 89 90 91 88 92 16 71 93 53 94 99 10 100 12 9...
output:
199957339 199957339 713415395 633706456 352131089 624197058 360461813 532766543 643300762 951160691 515628617 162173363 188718163 899871076 591019765 913659763 516547362 997687530 555134171 277981670 434565875 428443692 950912211 201268221 799265651 31491534 581175237 513698743 795109450 730574236 6...
result:
wrong answer 3rd numbers differ - expected: '748333395', found: '713415395'