QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#261318 | #7792. Tree Topological Order Counting | Froranzen | 0 | 2ms | 9680kb | C++23 | 3.5kb | 2023-11-22 20:16:41 | 2023-11-22 20:16:44 |
answer
#include <bits/stdc++.h>
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
#define per(i, t, f) for(int i(t); i >= f; --i)
#define pe(i, t) for(int i(t); i >= 1; --i)
#define nx(i, u) for(int i(head[u]); i; i = e[i].nxt)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
// #define int long long
using namespace std;
typedef pair <int, int> pii;
#define pb push_back
#define fi first
#define se second
#define ix(l, r) ((l + r) | (l != r))
#define ls (ix(l, mid))
#define rs (ix(mid + 1, r))
#define mp(i, j) (make_pair(i, j))
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define eps 1e-10
#define look_memory cerr<<abs(&sT-&eD)/1024.0/1024<<'\n'
bool sT;
namespace IO {
char buf[1 << 21], *p1 = buf, *p2 = buf, buf1[1 << 21];
inline char gc() {
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#endif
// #define gc getchar
template<class I>
inline void read(I &x) {
x = 0;
I f = 1;
char c = gc();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = gc();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = gc();
}
x *= f;
}
template<class I>
inline void write(I x) {
if (x == 0) {
putchar('0');
return;
}
I tmp = x > 0 ? x : -x;
if (x < 0)
putchar('-');
int cnt = 0;
while (tmp > 0) {
buf1[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0)
putchar(buf1[--cnt]);
}
#define in(x) read(x)
#define outn(x) write(x), putchar('\n')
#define out(x) write(x), putchar(' ')
} using namespace IO;
const int mod = 998244353;
const int N = 5e3 + 5;
int n, fath[N], b[N];
int fac[N], inv[N];
vector<int>G[N];
inline int ksm (int a, int b) {
ll ans = 1, base = a;
while(b) {
if(b & 1) ans = ans * base % mod;
base= base * base % mod;
b >>= 1;
}
return ans;
}
inline int C (int n, int m) {
if(n < 0 || m < 0 || n < m) return 0;
return 1ll * fac[n] * inv[m] % mod * inv[n-m] % mod;
}
int rt;
int f[N][N], siz[N], g[N];
int dfs (int u) {
f[u][0] = 1;
re(i, n) f[u][i] = 0;
f[u][1] = 1;
siz[u] = 1;
int flg = 0;
for(int v : G[u]) {
int w = dfs(v);
flg |= w;
f[u][0] = 1ll * f[u][0] * f[v][0] % mod * inv[siz[v]] % mod;
re(i, siz[u]) g[i] = f[u][i], f[u][i] = 0;
re(i, siz[u]) {
rep(j, 0, siz[v]) {
f[u][i+j] = (f[u][i+j] + 1ll * g[i] * f[v][j] % mod * inv[j] % mod * inv[siz[v]-j-w] % mod) % mod;
}
}
siz[u] += siz[v];
}
f[u][0] = 1ll * f[u][0] * fac[siz[u]-1] % mod;
re(i, siz[u]) f[u][i] = 1ll * f[u][i] * fac[i-1] % mod * fac[siz[u]-i-flg] % mod;
if(u == rt) {
re(i, siz[u]) f[u][i] = 0;
return 1;
}
if(flg) {
f[u][0] = 0;
}
return flg;
}
int main () {
read(n);
rep(i, 2, n) {
read(fath[i]);
G[fath[i]].pb(i);
}
re(i, n) read(b[i]);
fac[0] = inv[0] = 1;
re(i, n) fac[i] = 1ll * fac[i-1] * i % mod, inv[i] = ksm(fac[i], mod-2);
for(rt=1; rt<=n; ++rt) {
dfs(1);
int ans = 0;
rep(i, 0, n-1) {
ans = (ans + 1ll * f[1][i] * b[i+1] % mod) % mod;
}
out(ans);
}
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 9680kb
input:
10 1 2 2 4 2 5 3 2 3 421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543
output:
791644175 293112286 383600722 383600722 556722198 47472573 200339152 378530675 47472573 378530675
result:
wrong answer 1st numbers differ - expected: '132551152', found: '791644175'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Time Limit Exceeded
Test #22:
score: 0
Time Limit Exceeded
input:
3000 1 1 3 1 3 6 1 5 3 2 4 9 6 7 2 7 1 1 8 1 4 17 23 2 5 24 15 12 14 28 16 32 33 16 6 1 3 12 17 31 33 19 43 3 33 7 35 42 23 15 30 12 8 21 16 38 53 8 49 56 21 25 30 54 30 14 20 10 35 28 35 55 12 50 10 1 75 76 19 22 8 82 4 68 42 9 57 68 3 67 56 8 11 23 72 68 9 62 32 20 73 39 74 56 88 61 83 78 69 29 29...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%