QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#610826#5139. DFS Order 2yanshanjiahongWA 1ms5892kbC++142.8kb2024-10-04 17:36:422024-10-04 17:36:42

Judging History

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

  • [2024-10-04 17:36:42]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5892kb
  • [2024-10-04 17:36:42]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define int long long
#define double long double
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=505,M=6,S=(1<<15)+5,inf=1e9+7,mo=998244353;
const double eps=1e-8;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int n;
vector<int>e[N];
int f[N],g[N][N];
int quick_power(int base,int x){
    int res=1;
    while(x){
        if(x&1)res*=base,res%=mo;
        base*=base,base%=mo;
        x>>=1;
    }
    return res;
}
int jc[N],qj[N],sz[N],cnts[N],pros[N];
int h[N][N];
void addv(int upp,int maxs,int x){
    repp(i,upp,1){
        rep(j,sz[x],maxs)
            h[i][j]+=h[i-1][j-sz[x]],h[i][j]%=mo;
    }
}
void delv(int upp,int maxs,int x){
    rep(i,1,upp){
        rep(j,sz[x],maxs)
            h[i][j]-=h[i-1][j-sz[x]],h[i][j]=(h[i][j]+mo)%mo;
    }
}
void dfs1(int x,int p){
    sz[x]=1,f[x]=pros[x]=1;
    for(auto j:e[x]){
        if(j==p)continue;
        cnts[x]++,dfs1(j,x);
        sz[x]+=sz[j];
        f[x]*=f[j],f[x]%=mo;
        pros[x]*=f[j],pros[x]%=mo;
    }
    f[x]*=jc[cnts[x]],f[x]%=mo;
}
int hs[N];
void dfs2(int x,int p){
    if(x==1)g[x][1]=1;
    rep(i,0,cnts[x]){
        rep(j,0,sz[x])
            h[i][j]=0;
    }
    h[0][0]=1;
    for(auto j:e[x]){//count h.
        if(j==p)continue;
        addv(cnts[x],sz[x],j);
    }
    for(auto j:e[x]){//count g
        if(j==p)continue;
        delv(cnts[x],sz[x],j);
        int npro=pros[x]*quick_power(f[j],mo-2)%mo;
        rep(k,0,sz[x])
            hs[k]=0;
        rep(i,0,cnts[x]-1){
            rep(k,0,sz[x])
                hs[k]+=h[i][k]*jc[cnts[x]-i-1]%mo*jc[i]%mo,hs[k]%=mo;
        }
        rep(i,2,n-sz[j]+1){
            rep(k,1,i-1)
                g[j][i]+=g[x][k]*npro%mo*hs[i-k-1]%mo,g[j][i]%=mo;
        }
        addv(cnts[x],sz[x],j);
    }
    for(auto j:e[x])
        if(j!=p)dfs2(j,x);
}
signed main(){
    read(n);
    jc[0]=qj[0]=1;
    rep(i,1,n)
        jc[i]=jc[i-1]*i%mo,qj[i]=quick_power(jc[i],mo-2);
    rep(i,1,n-1){
        int x,y;
        read(x),read(y);
        e[x].push_back(y),e[y].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,0);
    /*rep(i,1,n){
        printf("%lld %lld:\n",i,f[i]);
        rep(j,1,n)
            printf("%lld %lld:%lld\n",i,j,g[i][j]);
    }*/
    rep(i,1,n){
        rep(j,1,n)
            printf("%lld ",g[i][j]*f[i]%mo);
        puts("");
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 5892kb

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 4 4 4 12 12 12 
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 38th numbers differ - expected: '4', found: '12'