QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277901#5139. DFS Order 2zzuqyWA 2ms10300kbC++113.0kb2023-12-07 08:49:122023-12-07 08:49:12

Judging History

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

  • [2023-12-07 08:49:12]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10300kb
  • [2023-12-07 08:49:12]
  • 提交

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],F[510],JIE[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<int>q;
int vis[510][510];
queue<int>use[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;
    JIE[0]=1;
    for(int i=1;i<=n+1;i++){
        jie[i]=1ll*jie[i-1]*i%mod;
        JIE[i]=quick(jie[i],mod-2);
    }
    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;
        }
    }
    ans[1][1]=1;
    for(int i=1;i<=n;i++)
    	F[i]=quick(f[i],mod-2);

    q.push(1);
    use[1].push(1);
    while(q.size())
    {
        int x=q.front();
    	q.pop();
	    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]--;
            while(use[x].size())
            {
                int k=use[x].front();
                use[x].pop();
                int res=ans[x][k];
    	        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*F[y]%mod*JIE[cnt[x]+1]%mod;
    					ans[y][k+i+1]%=mod;
    		        }
    	        }
            }

            q.push(y);
            for(int i=0;i<=n;i++)
                if(ans[y][i])
                    use[y].push(i);
	        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;
	    }
    }
    // cout<<clock();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<(1ll*ans[i][j]*f[i]%mod+mod)%mod<<' ';
        cout<<'\n';
    }
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 10300kb

input:

5
1 2
1 3
3 4
3 5

output:

4 0 0 0 0 
0 2 0 0 2 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 

result:

wrong answer 12th numbers differ - expected: '2', found: '0'