QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100732 | #5139. DFS Order 2 | lgvc# | AC ✓ | 513ms | 118312kb | C++23 | 3.1kb | 2023-04-27 19:58:24 | 2023-04-27 19:58:26 |
Judging History
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