QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#617937 | #5139. DFS Order 2 | MENDAX | WA | 0ms | 3872kb | C++14 | 2.0kb | 2024-10-06 17:47:41 | 2024-10-06 17:47:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define x first
#define y second
const int N=510,mod=998244353;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef pair<int,int> PII;
vector<int> e[N];
int qmi(int a,int k){
int res=1;
while(k){
if(k&1) res=res*a%mod;
a=a*a%mod;
k>>=1;
}
return res;
}
int p[N][N],siz[N];
int ge(int u,int fa){
int num=0;
int res=1;
siz[u]=1;
for(auto v:e[u]){
if(v==fa) continue;
num++;
res*=ge(v,u);
siz[u]+=siz[v];
res%=mod;
}
for(int i=1;i<=num;i++)res*=i,res%=mod;
return res;
}
int pos[N];
int n;
void dfs(int u,int fa){
vector<int> w;
w.push_back(0);
int cnt=0;
for(auto v:e[u]){
if(v==fa) continue;
cnt++;
pos[v]=cnt;
w.push_back(siz[v]);
}
int len=w.size();
for(auto v:e[u]){//这个就是枚举要处理的子儿子
vector<vector<int>> dp(len+1,vector<int>(siz[u]+10,0));
dp[0][1]=1;
if(v==fa) continue;
for(int i=1;i<len;i++){
for(int j=0;j<=siz[u];j++) dp[i][j]=dp[i-1][j];
if(i==pos[v]) continue;//求得v
for(int j=0;j<=siz[u];j++)if(j>=w[i]) dp[i][j]+=dp[i-1][j-w[i]],dp[i][j]%=mod;//这里面dp[i][4]
}
int sum=0;
for(int j=0;j<=siz[u];j++) sum+=dp[len-1][j];
sum=qmi(sum,mod-2);
for(int i=1;i<=n;i++){//枚举u走的步数
for(int j=1;j<=n;j++){//枚举兄弟走的步数
p[v][i+j]+=dp[len-1][j]%mod*sum%mod*p[u][i]%mod;//兄弟的方案数
p[v][i+j]%=mod;
}
}
}
for(auto v:e[u]){
if(v==fa) continue;
dfs(v,u);
}
}
void slove(){
cin>>n;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
e[u].push_back(v),e[v].push_back(u);
}
int total=ge(1,0);
// cout<<total<<endl;
p[1][1]=1;
dfs(1,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<p[i][j]*total%mod<<" ";
}
cout<<endl;
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T=1;
while(T--) slove();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
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: 0ms
memory: 3872kb
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 3 3 3 6 3 3 3 0 0 0 3 6 3 3 6 3 0 0 0 0 0 3 6 3 3 6 3 0 12 0 0 0 0 0 12 0 0 0 12 0 0 12 0 0 0 0 0 0 0 0 3 3 3 6 3 3 3 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 14th numbers differ - expected: '4', found: '3'