QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277741#5139. DFS Order 2zzuqy#WA 0ms9596kbC++112.5kb2023-12-06 22:11:412023-12-06 22:11:42

Judging History

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

  • [2023-12-06 22:11:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9596kb
  • [2023-12-06 22:11:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
    int x;cin>>x;
    return x;
}
int mod=998244353;
ll quick(ll a,ll b)
{
	ll t=1;
	while(b)
	{
		if(b&1)
			t=t*a%mod;
		b=b/2;
		a=a*a%mod;
	}
	return t;
}
int n,f[510],siz[510],g[510][510][510],jie[510],ans[510][510];
int sum[510],cnt[510];
vector<int>e[510];
void dfs(int x,int fa)
{
    f[x]=1;
    siz[x]=1;
    
	for(int i=0;i<e[x].size();i++)
	{
		if(e[x][i]==fa)
		{
			swap(e[x][i],e[x][e[x].size()-1]);
			e[x].resize(e[x].size()-1);
		}
	}
    for(auto y:e[x])
    {
        if(y==fa)
            continue;
        dfs(y,x);
        siz[x]+=siz[y];
        f[x]=1ll*f[x]*f[y]%mod;
        cnt[x]++;
    }
    f[x]=1ll*f[x]*jie[cnt[x]]%mod;
}
queue<pair<int,int>>q;
int vis[510][510];
int main()
{
//    freopen("1.in","r",stdin);
//    freopen("1.out","w",stdout);
    n=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    jie[0]=1;
    for(int i=1;i<=n+1;i++)
        jie[i]=1ll*jie[i-1]*i%mod;
    dfs(1,0);
    for(int x=n;x>=1;x--)
    {
    	g[x][0][0]=1;
        cnt[x]=0;
        for(auto y:e[x])
        {
            sum[x]+=siz[y];
            cnt[x]++;
            for(int i=sum[x];i>=siz[y];i--)
                for(int j=cnt[x];j>=1;j--)
                   g[x][j][i]=(g[x][j][i]+g[x][j-1][i-siz[y]])%mod;
        }
    }
    q.push({1,1});
    vis[1][1]=1;
    ans[1][1]=1;
    while(q.size())
    {
    	int x=q.front().first,k=q.front().second;
    	q.pop();
    	int res=ans[x][k];
	    for(auto y:e[x])
	    {
	        for(int i=siz[y];i<=sum[x];i++)
	            for(int j=1;j<=cnt[x];j++)
	               g[x][j][i]=(g[x][j][i]-g[x][j-1][i-siz[y]])%mod;
	        sum[x]-=siz[y];
	        cnt[x]--;
	        for(int i=0;i<=sum[x];i++)
	        {
	            for(int j=0;j<=cnt[x];j++)
	            {
	                if(g[x][j][i]==0)
	                    continue;
					ans[y][k+i+1]+=1ll*res*jie[j]%mod*jie[cnt[x]-j]%mod*g[x][j][i]%mod*f[x]%mod*quick(f[y],mod-2)%mod*quick(jie[cnt[x]+1],mod-2)%mod;
					ans[y][k+i+1]%=mod;
		        }
	        }
	        sum[x]+=siz[y];
	        cnt[x]++;
	        for(int j=cnt[x];j>=1;j--)
	            for(int i=1;i<=sum[x];i++)
	               g[x][j][i]=(g[x][j][i]+g[x][j-1][i-siz[y]])%mod;
	    }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<(ans[i][j]*f[i]%mod+mod)%mod<<' ';
        cout<<'\n';
    }
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 9596kb

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 0 0 0 
0 0 0 0 0 

result:

wrong answer 18th numbers differ - expected: '1', found: '0'