QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#658720 | #5139. DFS Order 2 | juan_123 | RE | 0ms | 0kb | C++14 | 2.1kb | 2024-10-19 17:28:13 | 2024-10-19 17:28:13 |
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 = i+1;j>=1;j--){
for(int k = s[i];j<=sz[now];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<=sz[now];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<=sz[now];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 = s[l];k<=sz[now];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
1 3
3 4
3 5
*/
詳細信息
Test #1:
score: 0
Runtime Error
input:
5 1 2 1 3 3 4 3 5