QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#589527#5139. DFS Order 2SoestxWA 315ms513548kbC++173.1kb2024-09-25 18:16:462024-09-25 18:16:48

Judging History

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

  • [2024-09-25 18:16:48]
  • 评测
  • 测评结果:WA
  • 用时:315ms
  • 内存:513548kb
  • [2024-09-25 18:16:46]
  • 提交

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]=1ll*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]=(1ll*dp[id][to][p+1]+dp[id][o][p]*(p+1)%mod)%mod;
			}
		}
		cnt++;
		siz[id]+=siz[j];
		dap[id]=1ll*dap[id]*dap[j]%mod;
    }
    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=0;o<=siz[id];o++)
		{
			for(int p=0;p<=son[id];p++)
			{
				if(!dp[id][o][p]) continue;
				int t=dp[id][o][p];;
				if(o>=siz[j]&&p)
				t=(1ll*dp[id][o][p]-1ll*p*tmp[o-siz[j]][p-1]%mod);
				//cout<<o<<" "<<p<<" "<<dp[id][o][p]<<" "<<dp[id][o-siz[j]][p-1]<<" "<<t<<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()
{
    cin>>n;
    ini();
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>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++)
        {
        	//cout<<i<<" "<<j<<" "<<tp[i][j]<<endl;
        	//cout<<tp[i][j]<<" "<<dap[i]<<endl;
			ll t=1ll*tp[i][j]*dap[i]%mod;
			t=(t%mod+mod)%mod;
        	cout<<t<<" ";
			//printf("%d ",1ll*tp[i][j]*dap[i]%mod);
		}
		cout<<endl;
    }
}

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

*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 11884kb

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: 0
Accepted
time: 3ms
memory: 16024kb

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

ok 100 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 104520kb

input:

100
18 100
91 87
28 83
11 98
51 52
24 91
72 53
18 19
89 16
77 35
26 25
73 16
96 70
56 44
69 10
63 30
54 95
39 66
58 98
8 71
58 65
74 73
2 64
12 19
32 81
31 54
43 41
84 59
55 75
72 81
59 37
10 94
93 2
64 47
13 32
36 84
28 22
30 28
25 77
47 6
80 52
54 17
23 40
47 88
49 53
65 27
99 59
25 70
91 9
74 1
7...

output:

8388559 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 62914557 0 62914557 62914557 0 62914557 0 0 0 62914557 0 62914557...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 76ms
memory: 509576kb

input:

500
382 156
418 376
91 15
142 274
449 174
375 82
118 175
421 458
361 222
14 474
11 324
368 341
227 424
231 249
81 435
250 271
118 38
147 61
124 408
135 1
244 316
301 80
39 313
90 118
290 465
465 250
277 341
8 105
319 373
305 379
309 200
180 398
47 489
463 259
173 492
494 343
251 193
111 32
401 270
4...

output:

219078761 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 250000 numbers

Test #5:

score: 0
Accepted
time: 24ms
memory: 511952kb

input:

500
164 415
76 333
437 167
184 28
281 491
40 64
184 6
407 459
141 469
370 186
226 142
165 243
26 175
442 345
496 451
351 277
467 136
42 10
14 435
109 202
22 267
354 312
232 273
141 158
219 356
329 405
212 65
345 166
378 79
114 224
213 79
371 23
454 276
150 9
82 291
24 111
157 396
22 475
268 163
57 8...

output:

744716203 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 250000 numbers

Test #6:

score: 0
Accepted
time: 27ms
memory: 513548kb

input:

500
177 65
367 41
19 51
1 131
95 135
410 397
30 109
357 209
172 357
195 199
167 297
437 232
63 12
194 387
309 12
235 112
32 359
143 66
267 397
467 224
199 383
226 310
435 3
300 206
151 189
198 398
226 287
322 467
244 280
273 9
44 305
273 32
398 15
14 117
199 290
313 76
85 80
34 348
146 458
261 233
2...

output:

171992689 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 250000 numbers

Test #7:

score: -100
Wrong Answer
time: 315ms
memory: 512136kb

input:

500
381 446
399 209
190 247
83 319
1 278
101 82
1 224
1 75
391 382
303 231
220 92
446 494
112 342
73 218
1 148
210 334
1 57
212 44
450 495
17 473
173 122
424 1
196 465
47 305
321 143
458 88
10 439
1 243
391 144
300 397
332 1
232 1
1 152
366 1
100 483
111 25
416 63
242 280
110 1
119 1
234 365
1 475
5...

output:

566360865 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

wrong answer 507th numbers differ - expected: '230860221', found: '830887086'