QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100732#5139. DFS Order 2lgvc#AC ✓513ms118312kbC++233.1kb2023-04-27 19:58:242023-04-27 19:58:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-27 19:58:26]
  • 评测
  • 测评结果:AC
  • 用时:513ms
  • 内存:118312kb
  • [2023-04-27 19:58:24]
  • 提交

answer

//这回只花了114514min就打完了。
//真好。记得多手造几组。
#include <bits/stdc++.h>
//#define int long long
#define pai 3.141592653589793238462643383279502884197169399375105820
#define MOD 998244353
#define eps 0.00000001
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
#define ULL unsigned long long
#define LL long long
#define INF 0x3f3f3f3f
#define INF_LL 0x3f3f3f3f3f3f3f3f
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
	if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
	*pp++=ch;
}
inline void pcc(){
	fwrite(buf2,1,pp-buf2,stdout);
	pp=buf2;
}
inline int read(void) {
	int w=1;
	register int x(0);register char c(getchar());
	while(c<'0'||c>'9') {if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w*x;
}
void write(int x) {
	if(x<0) pc('-'),x=-x;
	static int sta[20];
	int top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while(x);
	while(top) pc(sta[--top]+48);
}
void we(int x) {
	write(x);
	pc('\n');
}
inline bool cmp_xi(int a,int b) {return a<b;}
inline bool cmp_da(int a,int b) {return a>b;}
bool vi[509][509];
int N,hd[509],dd[509][509],to[1009],nxt[1009],siz[509],p[509],px[509],k,dp[509][509][509];
inline void l(int u,int v) {nxt[++k]=hd[u],to[k]=v,hd[u]=k;}
inline int md(int a) {
	return a>=MOD?a-MOD:a;
}
void dfs(int n,int f) {
	siz[n]=1;p[n]=1;
	int dg=0;
	vi[n][n]=1;
	for(int i=hd[n];i;i=nxt[i]) {
		if(to[i]==f) continue;
		dfs(to[i],n);
		for(int j=1;j<=N;j++) vi[n][j]|=vi[to[i]][j];
		dg++;
		siz[n]+=siz[to[i]];
		p[n]=1ll*p[n]*p[to[i]]%MOD;
	}
	p[n]=1ll*p[n]*px[dg]%MOD;
	dp[n][n][1]=p[n];
	for(int i=hd[n];i;i=nxt[i]) {
		if(to[i]==f) continue;
		for(int j=0;j<=dg;j++) {
			for(int k=0;k<=siz[n];k++) {
				dd[j][k]=0;
			}
		}
		dd[0][0]=1;
		int aq=1,ss=0,dq=0;
		for(int j=hd[n];j;j=nxt[j]) {
			if(to[j]==f||to[j]==to[i]) continue;
			aq=1ll*aq*p[to[j]]%MOD;
			ss+=siz[to[j]];dq++;
			for(int k=dq;k>=1;k--) {
				for(int l=siz[to[j]];l<=ss;l++) {
					dd[k][l]=md(dd[k][l]+dd[k-1][l-siz[to[j]]]);
				}
			}
		}
		for(int k=0;k<=siz[n];k++) {
			int as=0;
			for(int j=0;j<=dg;j++) {
				if(!dd[j][k]) continue;
				int va=1ll*dd[j][k]*px[j]%MOD*px[dg-j-1]%MOD;
				as=md(as+va);
			}
			as=1ll*as*aq%MOD;
			if(as==0) continue;
			for(int l=1;l<=N;l++) {
				if(!vi[to[i]][l]) continue;
				for(int x=1;x<=siz[to[i]]&&x+k+1<=siz[n];x++) {
					if(dp[to[i]][l][x]) dp[n][l][x+k+1]=md(dp[n][l][x+k+1]+1ll*dp[to[i]][l][x]*as%MOD);
				}
			}
		}
	}
} 
signed main(void) {
//    freopen("m.in","r",stdin);
//    freopen("m.out","w",stdout);
	N=read();
	px[0]=1;
	for(int i=1;i<=N;i++) px[i]=1ll*px[i-1]*i%MOD;	
	for(int i=1;i<N;i++) {
		int u=read(),v=read();
		l(u,v),l(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=N;i++) {
		for(int j=1;j<=N;j++) {
			write(dp[1][i][j]);
			pc(' ');
		}
		pc('\n');
	}
	pcc();
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3292kb

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

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: 4ms
memory: 8732kb

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: 47ms
memory: 118312kb

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: 30ms
memory: 28296kb

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: 20ms
memory: 15648kb

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: 0
Accepted
time: 392ms
memory: 10392kb

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:

ok 250000 numbers

Test #8:

score: 0
Accepted
time: 171ms
memory: 12404kb

input:

500
93 1
1 431
401 267
455 366
32 390
403 198
1 211
374 279
351 1
240 1
437 311
207 197
45 1
197 424
77 262
298 1
153 1
18 281
54 448
314 6
363 141
372 8
407 331
331 21
337 1
409 398
301 1
187 189
55 437
1 272
16 1
411 206
462 255
193 389
450 4
1 137
140 118
221 196
489 1
486 242
60 370
129 79
469 1...

output:

227529272 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 #9:

score: 0
Accepted
time: 82ms
memory: 15248kb

input:

500
183 389
280 391
263 341
39 40
480 336
1 92
444 314
64 173
258 120
129 243
174 1
403 160
499 362
407 1
294 1
212 459
268 115
438 416
351 1
141 1
297 150
149 402
223 38
104 396
300 169
1 437
73 242
116 483
271 229
407 499
281 78
110 50
166 472
250 1
232 400
319 1
302 308
1 330
297 329
471 171
25 1...

output:

448670309 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 #10:

score: 0
Accepted
time: 47ms
memory: 37628kb

input:

500
133 394
381 56
247 487
122 256
430 1
1 330
50 41
20 38
491 493
290 280
414 390
360 169
402 80
183 126
142 257
381 123
265 1
373 174
145 316
422 319
474 75
79 425
165 118
453 131
328 128
405 225
69 196
223 88
429 156
92 137
18 252
1 232
291 295
382 309
125 1
301 333
420 484
497 63
347 32
334 227
...

output:

131504462 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 #11:

score: 0
Accepted
time: 50ms
memory: 31920kb

input:

500
288 98
40 352
234 132
49 289
103 29
10 418
7 197
136 396
181 468
429 270
196 43
453 389
254 185
15 405
453 405
458 323
477 209
149 97
498 20
168 95
80 492
455 83
299 346
202 337
181 481
104 139
415 153
269 14
315 443
155 224
365 456
1 281
195 500
228 222
125 187
142 194
292 141
363 1
70 203
405 ...

output:

628243246 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 #12:

score: 0
Accepted
time: 513ms
memory: 11084kb

input:

500
233 2
115 66
66 353
66 332
141 66
213 390
101 207
66 41
293 484
362 411
224 294
124 44
329 331
261 66
66 8
495 176
72 102
341 318
169 343
485 227
66 154
344 436
66 354
304 66
364 57
130 66
66 294
66 447
312 66
180 361
66 310
76 183
13 96
66 244
66 420
66 471
89 66
66 117
19 334
46 254
147 484
14...

output:

639412989 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 #13:

score: 0
Accepted
time: 156ms
memory: 13576kb

input:

500
87 366
173 87
460 471
191 439
87 4
351 427
201 205
128 401
161 362
109 367
324 296
125 422
367 233
112 87
13 245
51 346
4 412
478 331
47 338
87 464
221 440
416 420
191 355
126 322
477 87
400 363
99 101
429 144
87 249
303 65
120 87
157 87
419 87
45 161
334 56
159 87
361 232
278 376
87 448
384 353...

output:

46803215 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 #14:

score: 0
Accepted
time: 74ms
memory: 18144kb

input:

500
153 363
86 463
23 27
360 402
284 465
206 360
380 224
313 252
18 128
139 369
433 467
429 451
233 22
360 317
25 201
59 388
360 231
143 360
275 260
360 487
295 495
474 44
459 240
217 62
421 349
476 267
360 219
473 221
474 179
356 196
360 241
344 354
278 230
63 360
468 152
158 177
112 326
360 441
44...

output:

76613732 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 #15:

score: 0
Accepted
time: 43ms
memory: 25788kb

input:

500
474 52
218 265
468 285
379 183
373 383
340 367
339 92
46 221
451 195
276 10
389 487
216 121
119 159
111 371
150 40
17 454
344 298
41 183
207 309
27 472
161 133
337 215
336 384
288 130
212 6
445 485
92 497
266 187
240 151
71 22
184 102
100 169
454 215
160 130
183 447
259 436
415 225
167 58
183 35...

output:

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