QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#658668 | #5139. DFS Order 2 | juan_123 | WA | 1ms | 5888kb | C++14 | 2.1kb | 2024-10-19 17:18:02 | 2024-10-19 17:18:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int qp(int p,int q){
int ans = 1,pro = p;
while(q){
if(q&1)ans = ans*pro%mod;
pro = pro*pro%mod;q>>=1;
}
return ans;
}
int dp[505][505],sz[505];
vector<int>p[505];
int jie[505];
int f[505][505],g[505];
int n;
void dfs1(int now,int fa){
g[now] = 1;
sz[now]=1;
int tt =0 ;
for(auto x:p[now])if(x!=fa){
dfs1(x,now);
sz[now]+=sz[x];
++tt;
g[now] = g[now]*g[x]%mod;
}
g[now] = g[now]*jie[tt]%mod;
}
void dfs(int now,int fa){
vector<int>s;//s.push_back(0);
int pro = 1;
for(auto x:p[now]){
if(x!=fa)s.push_back(sz[x]),pro = pro*g[x]%mod;
}
for(int i =0;i<s.size();i++)for(int j =0;j<=sz[now];j++)f[i][j]=0;
f[0][0] = 1;
for(int i =0;i<s.size();i++){
for(int j = s.size();j>=1;j--){
for(int k = n;k>=s[i];k--){
f[j][k] = (f[j][k]+f[j-1][k-s[i]])%mod;
}
}
}
int l =0;
for(auto x:p[now]){
if(x==fa)continue;
for(int j = 1;j<=s.size();j++){
for(int k = s[l];k<=n;k++){
f[j][k] = (f[j][k]-f[j-1][k-s[l]]+mod)%mod;
}
}
int p = pro*qp(g[x],mod-2)%mod;
for(int i = 1;i<=n;i++){
for(int j = 0;j<s.size();j++){
for(int k = 0;k<=n;k++){
// cout <<" " << i+k+1 << " " << f[j][k] <<" " << dp[now][i] << " " << jie[j]*jie[s.size()-j-1]*p%mod << endl;
dp[x][i+k+1] = (dp[x][i+k+1]+f[j][k]*dp[now][i]%mod*jie[j]%mod*jie[s.size()-j-1]*p%mod)%mod;
}
}
}
for(int j = s.size();j>=1;j--){
for(int k = n;k>=s[l];k--){
f[j][k] = (f[j][k]+f[j-1][k-s[l]])%mod;
}
}
++l;
}
for(auto x:p[now])if(x!=fa)dfs(x,now);
}
signed main(){
cin >> n;
jie[0]=1;for(int i = 1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
for(int i = 1;i<n;i++){
int a,b;cin >>a >> b;
p[a].push_back(b),p[b].push_back(a);
}
dp[1][1] = 1;
dfs1(1,1);
// for(int i = 1;i<=n;i++)cout << " " << g[i];cout << endl;
dfs(1,1);
for(int i =1;i<=n;i++){
for(int j = 1;j<=n;j++)dp[i][j]=dp[i][j]*g[i]%mod;
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++)cout << dp[i][j] << " ";
cout << endl;
}
return 0;
}/*
5
1 2
2 3
3 4
4 5
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5888kb
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: 1ms
memory: 5660kb
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 8 2 2 6 0 0 0 4 4 4 4 4 4 2 0 0 0 0 4 4 4 4 4 4 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 8 2 2 6 0 0 6 6 0 0 0 0 12 6 0 0 12 0 0 12 0 0 0 0 0 0 6 6 0 0 0 0 12 6
result:
wrong answer 20th numbers differ - expected: '4', found: '6'