QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#229276 | #5139. DFS Order 2 | whsyhyyh# | AC ✓ | 685ms | 10020kb | C++14 | 2.0kb | 2023-10-28 15:38:17 | 2023-10-28 15:38:17 |
Judging History
answer
#include<bits/stdc++.h>
#define N 510
#define LL long long
#define mod 998244353
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int rd() {
int res=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
return res*f;
}
LL poww(LL x,LL y) {
LL res=1;
while(y) {
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int n,sz[N];
vector<int>G[N];
LL g[N],dp[N][N],tmp[N][N],f[N][N];
void dfs1(int x,int fat) {
g[x]=sz[x]=1;
int son=0;
for(auto v:G[x]) if(v!=fat) {
son++;
dfs1(v,x);
sz[x]+=sz[v];
g[x]=g[x]*son%mod*g[v]%mod;
}
}
void dfs2(int x,int fat) {
memset(dp,0,sizeof(dp));
dp[0][0]=1;
int son=0,all=0;
for(auto v:G[x]) if(v!=fat) {
memcpy(tmp,dp,sizeof(tmp)),memset(dp,0,sizeof(dp));
rep(i,0,son) rep(j,0,all) if(tmp[i][j]) dp[i][j]=(dp[i][j]+tmp[i][j]*g[v]%mod*(son+1-i))%mod,dp[i+1][j+sz[v]]=(dp[i+1][j+sz[v]]+tmp[i][j]*g[v]%mod*(i+1))%mod;
all+=sz[v];
son++;
}
for(auto v:G[x]) if(v!=fat) {
rep(i,0,son) {
LL tmp=poww(g[v]*(son-i)%mod,mod-2);
rep(j,0,all) {
dp[i][j]=dp[i][j]*tmp%mod;
dp[i+1][j+sz[v]]=(dp[i+1][j+sz[v]]-dp[i][j]*g[v]%mod*(i+1)%mod+mod)%mod;
}
}
rep(j,0,all) rep(i,1,son) dp[0][j]=(dp[0][j]+dp[i][j])%mod;
rep(i,0,n) if(f[x][i]) rep(j,0,all) f[v][i+j+1]=(f[v][i+j+1]+f[x][i]*dp[0][j])%mod;
rep(j,0,all) rep(i,1,son) dp[0][j]=(dp[0][j]-dp[i][j]+mod)%mod;
memcpy(tmp,dp,sizeof(tmp)),memset(dp,0,sizeof(dp));
rep(i,0,son) rep(j,0,all) if(tmp[i][j]) dp[i][j]=(dp[i][j]+tmp[i][j]*g[v]%mod*(son-i))%mod,dp[i+1][j+sz[v]]=(dp[i+1][j+sz[v]]+tmp[i][j]*g[v]%mod*(i+1))%mod;
}
for(auto v:G[x]) if(v!=fat) dfs2(v,x);
}
int main() {
// freopen("C.in","r",stdin);
// freopen("C.out","w",stdout);
n=rd();
for(int i=1,u,v;i<n;i++) {
u=rd(),v=rd();
G[u].push_back(v),G[v].push_back(u);
}
dfs1(1,0),f[1][1]=1,dfs2(1,0);
rep(i,1,n) {
rep(j,1,n) printf("%lld ",f[i][j]*g[i]%mod);puts("");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 8952kb
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: 2ms
memory: 9028kb
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: 44ms
memory: 9916kb
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: 248ms
memory: 9892kb
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: 242ms
memory: 9928kb
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: 240ms
memory: 9948kb
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: 625ms
memory: 10020kb
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: 422ms
memory: 9860kb
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: 337ms
memory: 9864kb
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: 265ms
memory: 9900kb
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: 260ms
memory: 9884kb
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: 685ms
memory: 9964kb
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: 413ms
memory: 9868kb
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: 319ms
memory: 9932kb
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: 257ms
memory: 9932kb
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