QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#589435#5139. DFS Order 2SoestxWA 0ms16204kbC++173.1kb2024-09-25 17:53:132024-09-25 17:53:13

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 17:53:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:16204kb
  • [2024-09-25 17:53:13]
  • 提交

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

*/

Details

Tip: Click on the bar to expand more detailed information

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'