QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#589435 | #5139. DFS Order 2 | Soestx | WA | 0ms | 16204kb | C++17 | 3.1kb | 2024-09-25 17:53:13 | 2024-09-25 17:53:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define lowbit(x) (x&(-x))
typedef long long ll;
//typedef unsigned long long ull;
const int N = 1e6 + 10, M = 1e5,mod=998244353;
int n, m, k;
int res;
int dp[510][510][510],dap[510],tp[510][510];
int siz[510],son[510];
int h[510],e[1010],ne[1010],idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int fac[510];
void ini()
{
idx=0;
fac[0]=1;
for(int i=1;i<=n;i++)
{
h[i]=-1;
fac[i]=fac[i-1]*i%mod;
}
}
ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int tap[510];
void dfs(int id,int f)
{
siz[id]=1;
dap[id]=1;
int cnt=0;
dp[id][0][0]=1;
for(int i=h[id];i!=-1;i=ne[i])
{
int j=e[i];
if(j==f) continue;
dfs(j,id);
for(int o=siz[id];o>=0;o--)
{
for(int p=cnt;p>=0;p--)
{
int to=o+siz[j];
dp[id][to][p+1]=(dp[id][to][p+1]+1ll*dp[id][o][p]*(p+1)%mod)%mod;
}
}
cnt++;
siz[id]+=siz[j];
dap[id]=1ll*dap[id]*dap[j]%mod;
}
//cout<<"ID "<<id<<"--------------"<<endl;
// for(int o=siz[id];o>=0;o--)
// {
// for(int p=cnt;p>=0;p--)
// {
// cout<<o<<" "<<p<<" "<<dp[id][o][p]<<endl;
// }
// }
son[id]=cnt;
tap[id]=dap[id];
dap[id]=1ll*dap[id]*fac[cnt]%mod;
}
int tmp[510][510],arr[510];
void DFS(int id,int f)
{
for(int i=h[id];i!=-1;i=ne[i])
{
int j=e[i];
if(j==f) continue;
//cout<<j<<"-----------------------"<<endl;
for(int a=0;a<=siz[id];a++) for(int b=0;b<=son[id];b++) tmp[a][b]=0,arr[a]=0;
for(int o=siz[id];o>=0;o--)
{
for(int p=son[id];p>=0;p--)
{
if(!dp[id][o][p]) continue;
int t=dp[id][o][p];;
if(o>=siz[j])
t=(1ll*dp[id][o][p]-p*dp[id][o-siz[j]][p-1]%mod);
//cout<<o<<" "<<p<<" "<<dp[id][o][p]<<" "<<dp[id][o-siz[j]][p-1]<<endl;
t=(t%mod+mod)%mod;
tmp[o][p]=(tmp[o][p]+t)%mod;
}
}
int ty=1ll*tap[id]*qpow(dap[j],mod-2)%mod;
for(int o=0;o<=siz[id];o++)
{
int sum=0;
for(int p=0;p<=son[id];p++)
{
//cout<<o<<" "<<p<<" "<<tmp[o][p]<<endl;
sum=(1ll*sum+tmp[o][p]*fac[son[id]-1-p]%mod)%mod;
}
arr[o]=1ll*sum*ty%mod;
}
for(int o=0;o<=n;o++)
{
for(int p=0;p<=siz[id];p++)
{
int to=o+p+1;
tp[j][to]=(tp[j][to]+1ll*tp[id][o]*arr[p]%mod)%mod;
}
}
}
for(int i=h[id];i!=-1;i=ne[i])
{
int j=e[i];
if(j==f) continue;
DFS(j,id);
}
}
void solve()
{
scanf("%d",&n);
ini();
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d %d",&a,&b);
add(a,b);
add(b,a);
}
tp[1][1]=1;
dfs(1,0);
DFS(1,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) printf("%d ",1ll*tp[i][j]*dap[i]%mod);
puts("");
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
T = 1;
//cin>>T;
while (T--) solve();
return 0;
}
/*
1
2 0
10 15
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 10108kb
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: 16204kb
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 998244351 8 2 998244351 4 0 0 0 4 4 4 4 4 4 0 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 998244351 8 2 998244351 4 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 16th numbers differ - expected: '2', found: '998244351'