QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#65423 | #5139. DFS Order 2 | magicduck# | WA | 3ms | 5524kb | C++14 | 2.5kb | 2022-11-30 16:11:16 | 2022-11-30 16:11:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &F) {
int R = 1; F = 0; char CH = getchar();
for(; !isdigit(CH); CH = getchar()) if(CH == '-') R = -1;
for(; isdigit(CH); CH = getchar()) F = F * 10 + CH - 48;
F *= R;
}
inline void file(string str) {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
const LL mod = 998244353;
const int N = 5e2 + 10;
int n, siz[N], t[N]; LL f[N][N], g[N], res[N][N]; vector<int> edge[N];
void dfs(int x, int fa) {
siz[x] = g[x] = 1; int s = 0; t[x] = fa;
for(int i : edge[x]) {
if(fa == i) continue;
dfs(i, x); siz[x] += siz[i];
g[x] = g[x] * g[i] % mod;
s++; g[x] = g[x] * s % mod;
}
}
LL d[N], sumx[N], sumy[N];
void dp(const vector<int> &s) {
for(int i = 1; i <= n; i++)
d[i] = sumx[i] = sumy[i] = 0;
d[1] = sumx[1] = sumy[1] = 1;
for(int i : s) {
for(int j = n; j >= 1; j--) {
if(i + j <= n) {
(sumy[i + j] += sumy[j] * sumx[j]) %= mod;
(d[i + j] += d[j] * sumx[j]) %= mod;
(sumx[i + j] += d[j] * sumx[j]) %= mod;
}
d[j] = d[j] * sumy[j] % mod;
sumx[j] = sumx[j] * sumy[j] % mod;
(sumy[j] += d[j]) %= mod;
}
}
}
void solve(int x, int fa) {
if(fa) {
LL r = 1; vector<int> s;
for(int i : edge[fa]) {
if(i != t[fa] && x != i)
s.emplace_back(siz[i]), r = r * g[i] % mod;
}
dp(s);
for(int i = 1; i <= n; i++) {
LL res = 0;
for(int j = 1; j < i; j++)
res += f[fa][j] * d[i - j] % mod;
res = res % mod * r % mod;
f[x][i] = res;
}
}
for(int i = 1; i <= n; i++)
res[x][i] = f[x][i] * g[x] % mod;
for(int i : edge[x]) {
if(i == fa) continue;
solve(i, x);
}
}
int main() {
//file("");
read(n);
for(int i = 1; i < n; i++) {
int x, y; read(x), read(y);
edge[x].emplace_back(y);
edge[y].emplace_back(x);
}
dfs(1, 0);
f[1][1] = 1; solve(1, 0);
for(int i = 1; i <= n; i++, puts(""))
for(int j = 1; j <= n; j++)
cout << res[i][j] << " ";
#ifdef _MagicDuck
fprintf(stderr, "# Time: %.3lf s", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 5524kb
input:
5 1 2 1 3 3 4 3 5
output:
4 0 0 0 0 0 2 0 0 2 0 2 2 0 0 0 0 1 2 1 0 0 1 2 1
result:
ok 25 numbers
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 5524kb
input:
10 9 2 9 6 10 5 1 5 1 6 9 3 5 8 4 3 7 9
output:
24 0 0 0 0 0 0 0 0 0 0 0 0 4 2 2 6 2 2 2 0 0 0 4 4 2 4 4 2 0 0 0 0 0 4 4 2 4 4 2 0 12 0 0 0 0 0 12 0 0 0 12 0 0 12 0 0 0 0 0 0 0 0 4 2 2 6 2 2 2 0 0 6 6 0 0 0 0 6 6 0 0 12 0 0 12 0 0 0 0 0 0 6 6 0 0 0 0 6 6
result:
wrong answer 17th numbers differ - expected: '8', found: '6'