QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373391#5139. DFS Order 2SiilhouetteWA 1ms5792kbC++143.8kb2024-04-01 15:59:572024-04-01 15:59:59

Judging History

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

  • [2024-04-01 15:59:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5792kb
  • [2024-04-01 15:59:57]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define debug(x) cerr << #x << " == " << x << endl
#define el '\n'
#define fir first
#define sec second
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int N=510;
int n,m,soncnt[N];
ll fac[N],g[N],ans[N][N],h[N][N],siz[N],f[N];

inline ll fpow(ll x,ll y)
{
    ll res=1;
    for(;y;y>>=1)
    {
        if(y&1)res=res*x%mod;
        x=x*x%mod;
    }
    return res;
}

struct Graph{
    int tot,head[N],suiv[N<<1],ver[N<<1],fa[N];

    inline void lnk(int x,int y)
    {
        ver[++tot]=y;
        suiv[tot]=head[x];
        head[x]=tot;
    }

    inline void dfs1(int x)
    {
        g[x]=1;siz[x]=1;
        for(int i=head[x];i;i=suiv[i])
        {
            int y=ver[i];
            if(y==fa[x])continue;
            fa[y]=x;
            dfs1(y);
            siz[x]+=siz[y];
            soncnt[x]++;
            g[x]=g[x]*g[y]%mod;
        }
        g[x]=g[x]*fac[soncnt[x]]%mod;
    }

    inline void dfs2(int x)
    {
        //cout<<" x "<<x<<endl;
        h[0][0]=1;
        for(int i=head[x];i;i=suiv[i])
        {
            int y=ver[i];
            if(y==fa[x])continue;
            for(int k=soncnt[x];k;k--)
                for(int l=siz[x];l-siz[y]>=0;l--)
                    h[k][l]=(h[k][l]+h[k-1][l-siz[y]])%mod;
        }
        /*
        for(int k=soncnt[x];k>=0;k--)
        {
            cout<<"h[][] "<<endl;
            for(int l=siz[x];l>=0;l--)
                cout<<"k L "<<k<<" "<<l<<" "<<h[k][l]<<endl;
        }
        */
        for(int i=head[x];i;i=suiv[i])
        {
            int y=ver[i];
            if(y==fa[x])continue;
            for(int k=1;k<=soncnt[x];k++)
                for(int l=siz[x];l-siz[y]>=0;l--)
                    h[k][l]=((h[k][l]-h[k-1][l-siz[y]])%mod+mod)%mod;
            for(int k=0;k<=siz[x]+1;k++)
                f[k]=0;
            for(int k=0;k<=soncnt[x]-1;k++) 
                for(int l=0;l<=siz[x];l++) 
                    f[l+1]=(f[l+1]+fac[k]*fac[soncnt[x]-1-k]%mod*h[k][l]%mod)%mod;
            for(int k=1;k<=n;k++) 
                for(int l=1;l+k<=n;l++)
                    ans[y][l+k]=(ans[y][l+k]+ans[x][k]*f[l]%mod)%mod;
            for(int k=soncnt[x];k;k--)
                for(int l=siz[x];l-siz[y]>=0;l--)
                    h[k][l]=(h[k][l]+h[k-1][l-siz[y]])%mod;
            /*
            for(int k=0;k<=soncnt[z]-1;k++)
                for(int j=0;j<=n;j++)
                    for(int l=n;l-j>=0;l--)
                        f[z][l]=(f[z][l]+f[fa[z]][l-j]*h[k][j]%mod*fac[k]%mod*fac[soncnt[z]-k-1]%mod)%mod;
            
            cout<<"f[][]"<<endl;
            for(int j=0;j<=siz[x];j++)
                cout<<"z j "<<z<<" "<<f[j]<<endl;*/
        }
        
        for(int i=0;i<=soncnt[x];i++)
            for(int j=0;j<=siz[x];j++)
                h[i][j]=0;
        for(int i=head[x];i;i=suiv[i])
        {
            int y=ver[i];
            if(y==fa[x])continue;
            dfs2(y);
        }
    }

}e;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    fac[0]=1;
    for(int i=1;i<=500;i++)
        fac[i]=fac[i-1]*i%mod;
    cin>>n;
    for(int i=1,x,y;i<n;i++)
        cin>>x>>y,e.lnk(x,y),e.lnk(y,x);
    e.dfs1(1);
    ans[1][1]=g[1];
    e.dfs2(1);
    for(int i=1;i<=n;i++)
    {
        ll sum=0;
        for(int j=1;j<=n;j++)
            sum=(sum+ans[i][j])%mod;
        ll inv=fpow(sum,mod-2);
        for(int j=1;j<=n;j++)
            cout<<(g[1]*ans[i][j]%mod*inv%mod)<<" ";
        cout<<endl;
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5656kb

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: 1ms
memory: 5792kb

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 2 8 2 2 4 
0 0 0 4 4 4 4 4 4 0 
0 0 0 0 2 2 2 6 6 6 
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 2 8 2 2 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 35th numbers differ - expected: '4', found: '2'