1011.md (22549B)
1 Source: https://codeforces.com/blog/entry/60851 2 3 [1011A - Stages](/contest/1011/problem/A "Codeforces Round 499 (Div. 2)") 4 5 Author: Mike Mirzayanov ([MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")). 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() 19 { 20 int n,k; 21 cin>>n>>k; 22 string s; 23 cin>>s; 24 sort(s.begin(),s.end()); 25 char last='a'-2; 26 int ans=0; 27 int len=0; 28 for(int i=0;i<n;i++) 29 if(s[i]>=last+2) 30 { 31 last=s[i]; 32 ans+=s[i]-'a'+1; 33 len++; 34 if(len>=k) 35 cout<<ans,exit(0); 36 } 37 cout<<-1; 38 } 39 ``` 40 41 [1011B - Planning The Expedition](/contest/1011/problem/B "Codeforces Round 499 (Div. 2)") 42 43 Author: Mike Mirzayanov ([MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")). 44 45 **Tutorial** 46 47 Tutorial is loading... 48 49 **Solution** 50 51 ``` 52 #include <bits/stdc++.h> 53 54 using namespace std; 55 56 const int N = 100; 57 58 int main() { 59 int n, m; 60 cin >> n >> m; 61 vector<int> c(N + 1); 62 for (int i = 0; i < m; i++) { 63 int a; 64 cin >> a; 65 c[a]++; 66 } 67 for (int d = N; d >= 1; d--) { 68 vector<int> cc(c); 69 int k = 0; 70 for (int i = 1; i <= N; i++) 71 while (cc[i] >= d) { 72 k++; 73 cc[i] -= d; 74 } 75 if (k >= n) { 76 cout << d << endl; 77 return 0; 78 } 79 } 80 cout << 0 << endl; 81 } 82 ``` 83 84 [1011C - Fly](/contest/1011/problem/C "Codeforces Round 499 (Div. 2)") / [1010A - Fly](/contest/1010/problem/A "Codeforces Round 499 (Div. 1)") 85 86 Author: Vladislav Zavodnik ([VladProg](/profile/VladProg "Master VladProg")). 87 88 **Tutorial** 89 90 Tutorial is loading... 91 92 **Solution** 93 94 ``` 95 #include<bits/stdc++.h> 96 97 using namespace std; 98 99 int main() 100 { 101 int n,m; 102 cin>>n>>m; 103 int a[n]; 104 for(int i=0;i<n;i++) 105 { 106 cin>>a[i]; 107 if(a[i]<=1) 108 { 109 printf("-1\n"); 110 exit(0); 111 } 112 } 113 int b[n]; 114 for(int i=0;i<n;i++) 115 { 116 cin>>b[i]; 117 if(b[i]<=1) 118 { 119 printf("-1\n"); 120 exit(0); 121 } 122 } 123 double s=m; 124 s+=s/(a[0]-1); 125 for(int i=n-1;i>=1;i--) 126 { 127 s+=s/(b[i]-1); 128 s+=s/(a[i]-1); 129 } 130 s+=s/(b[0]-1); 131 printf("%.10lf\n",s-m); 132 } 133 ``` 134 135 [1011D - Rocket](/contest/1011/problem/D "Codeforces Round 499 (Div. 2)") / [1010B - Rocket](/contest/1010/problem/B "Codeforces Round 499 (Div. 1)") 136 137 Author: Vladislav Zavodnik ([VladProg](/profile/VladProg "Master VladProg")). 138 139 **Tutorial** 140 141 Tutorial is loading... 142 143 **Solution** 144 145 ``` 146 #include <bits/stdc++.h> 147 148 using namespace std; 149 150 int query(int y) 151 { 152 cout<<y<<"\n"; 153 fflush(stdout); 154 int t; 155 cin>>t; 156 if(t==0||t==-2) 157 exit(0); 158 return t; 159 } 160 161 int main() 162 { 163 int m,n; 164 cin>>m>>n; 165 int p[n]; 166 for(int i=0;i<n;i++) 167 { 168 int t=query(1); 169 p[i]=t==1; 170 } 171 int l=2,r=m; 172 for(int q=0;;q++) 173 { 174 int y=(l+r)/2; 175 int t=query(y); 176 if(!p[q%n]) 177 t*=-1; 178 if(t==1) 179 l=y+1; 180 else 181 r=y-1; 182 } 183 } 184 ``` 185 186 [1011E - Border](/contest/1011/problem/E "Codeforces Round 499 (Div. 2)") / [1010C - Border](/contest/1010/problem/C "Codeforces Round 499 (Div. 1)") 187 188 Author: Vladislav Zavodnik ([VladProg](/profile/VladProg "Master VladProg")). 189 190 **Tutorial** 191 192 Tutorial is loading... 193 194 **Solution** 195 196 ``` 197 #include<bits/stdc++.h> 198 199 using namespace std; 200 201 int gcd(int a,int b) 202 { 203 if(a<b) 204 swap(a,b); 205 return (b==0)?a:gcd(b,a%b); 206 } 207 208 int main() 209 { 210 int n,k; 211 scanf("%d%d",&n,&k); 212 int g=0; 213 for(int i=0;i<n;i++) 214 { 215 int t; 216 scanf("%d",&t); 217 g=gcd(g,t); 218 } 219 set<int> ans; 220 for(long long i=0,s=0;i<k;i++,s+=g) 221 ans.insert(s%k); 222 printf("%d\n",ans.size()); 223 for(set<int>::iterator i=ans.begin();i!=ans.end();i++) 224 printf("%d ",*i); 225 } 226 ``` 227 228 [1011F - Mars rover](/contest/1011/problem/F "Codeforces Round 499 (Div. 2)") / [1010D - Mars rover](/contest/1010/problem/D "Codeforces Round 499 (Div. 1)") 229 230 Author: Vladislav Zavodnik ([VladProg](/profile/VladProg "Master VladProg")). 231 232 **Tutorial** 233 234 Tutorial is loading... 235 236 **Solution** 237 238 ``` 239 #pragma GCC optimize("O3") 240 #include<bits/stdc++.h> 241 242 using namespace std; 243 244 struct vertex 245 { 246 char type; 247 vector<int>in; 248 bool val; 249 bool change; 250 }; 251 252 int n; 253 vector<vertex> g; 254 255 int dfs1(int v) 256 { 257 switch(g[v].type) 258 { 259 case 'A': 260 g[v].val = dfs1(g[v].in[0]) & dfs1(g[v].in[1]); 261 break; 262 case 'O': 263 g[v].val = dfs1(g[v].in[0]) | dfs1(g[v].in[1]); 264 break; 265 case 'X': 266 g[v].val = dfs1(g[v].in[0]) ^ dfs1(g[v].in[1]); 267 break; 268 case 'N': 269 g[v].val = ! dfs1(g[v].in[0]); 270 break; 271 } 272 return g[v].val; 273 } 274 275 void dfs2(int v) 276 { 277 if(g[v].change==false) 278 for(int i=0;i<g[v].in.size();i++) 279 g[g[v].in[i]].change=false; 280 else 281 switch(g[v].type) 282 { 283 case 'A': 284 if(g[v].val==(!g[g[v].in[0]].val&g[g[v].in[1]].val)) /// equal to if(g[g[v].in[1]].val==false) 285 g[g[v].in[0]].change=false; 286 else 287 g[g[v].in[0]].change=true; 288 if(g[v].val==(g[g[v].in[0]].val&!g[g[v].in[1]].val)) /// equal to if(g[g[v].in[0]].val==false) 289 g[g[v].in[1]].change=false; 290 else 291 g[g[v].in[1]].change=true; 292 break; 293 case 'O': 294 if(g[v].val==(!g[g[v].in[0]].val|g[g[v].in[1]].val)) /// equal to if(g[g[v].in[1]].val==true) 295 g[g[v].in[0]].change=false; 296 else 297 g[g[v].in[0]].change=true; 298 if(g[v].val==(g[g[v].in[0]].val|!g[g[v].in[1]].val)) /// equal to if(g[g[v].in[0]].val==true) 299 g[g[v].in[1]].change=false; 300 else 301 g[g[v].in[1]].change=true; 302 break; 303 case 'X': 304 if(g[v].val==(!g[g[v].in[0]].val^g[g[v].in[1]].val)) /// equal to if(false) 305 g[g[v].in[0]].change=false; 306 else 307 g[g[v].in[0]].change=true; 308 if(g[v].val==(g[g[v].in[0]].val^!g[g[v].in[1]].val)) /// equal to if(false) 309 g[g[v].in[1]].change=false; 310 else 311 g[g[v].in[1]].change=true; 312 break; 313 case 'N': 314 if(g[v].val==(!!g[g[v].in[0]].val)) /// equal to if(false) 315 g[g[v].in[0]].change=false; 316 else 317 g[g[v].in[0]].change=true; 318 break; 319 } 320 for(int i=0;i<g[v].in.size();i++) 321 dfs2(g[v].in[i]); 322 } 323 324 int main() 325 { 326 scanf("%d",&n); 327 g.resize(n); 328 for(int i=0;i<n;i++) 329 { 330 char c[4]; 331 scanf("%s",c); 332 g[i].type=c[0]; 333 int x; 334 switch(g[i].type) 335 { 336 case 'I': 337 scanf("%d",&x); 338 g[i].val=x; 339 break; 340 case 'N': 341 scanf("%d",&x); 342 g[i].in.push_back(x-1); 343 break; 344 default: 345 scanf("%d",&x); 346 g[i].in.push_back(x-1); 347 scanf("%d",&x); 348 g[i].in.push_back(x-1); 349 break; 350 } 351 } 352 dfs1(0); 353 g[0].change=true; 354 dfs2(0); 355 for(int i=0;i<n;i++) 356 if(g[i].type=='I') 357 printf("%d",g[0].val^g[i].change); 358 } 359 ``` 360 361 [1010E - Store](/contest/1010/problem/E "Codeforces Round 499 (Div. 1)") 362 363 Author: Vladislav Zavodnik ([VladProg](/profile/VladProg "Master VladProg")). 364 365 **Tutorial** 366 367 Tutorial is loading... 368 369 **Solution** 370 371 ``` 372 #include<bits/stdc++.h> 373 374 using namespace std; 375 376 int xmax,ymax,zmax,n,m,k; 377 378 map< int , map< int , pair< int ,int > > > pmap; 379 vector< pair< int , map< int , pair< int ,int > > > > pvector; 380 vector< pair< vector< pair< int , pair< int , int > > > , vector< pair< int , int > > > > tree; 381 int oxl,oxr,oyl,oyr,ozl,ozr; 382 383 pair<int,int> comb(pair<int,int> p1,pair<int,int> p2) 384 { 385 return make_pair(max(p1.first,p2.first), 386 min(p1.second,p2.second)); 387 } 388 389 void build_y(int vx,int lxt, int rxt,int vy,int lyt, int ryt) 390 { 391 if(lyt==ryt) 392 { 393 if(lxt==rxt) 394 tree[vx].second[vy]=tree[vx].first[lyt].second; 395 else 396 { 397 int sl,sr; 398 sl=0,sr=tree[vx*2+1].first.size()-1; 399 while(sr>sl) 400 { 401 int sm=(sl+sr)/2; 402 if(tree[vx*2+1].first[sm].first>=tree[vx].first[lyt].first) 403 sr=sm; 404 else 405 sl=sm+1; 406 } 407 pair<int,int> res1=(tree[vx*2+1].first[sl].first==tree[vx].first[lyt].first)? 408 (tree[vx*2+1].first[sl].second): 409 make_pair(0,(int)zmax+1); 410 sl=0,sr=tree[vx*2+2].first.size()-1; 411 while(sr>sl) 412 { 413 int sm=(sl+sr)/2; 414 if(tree[vx*2+2].first[sm].first>=tree[vx].first[lyt].first) 415 sr=sm; 416 else 417 sl=sm+1; 418 } 419 pair<int,int> res2=(tree[vx*2+2].first[sl].first==tree[vx].first[lyt].first)? 420 (tree[vx*2+2].first[sl].second): 421 make_pair(0,(int)zmax+1); 422 tree[vx].second[vy]=comb(res1,res2); 423 } 424 } 425 else 426 { 427 int myt=(lyt+ryt)/2; 428 build_y(vx,lxt,rxt,vy*2+1,lyt,myt); 429 build_y(vx,lxt,rxt,vy*2+2,myt+1,ryt); 430 tree[vx].second[vy]=comb(tree[vx].second[vy*2+1],tree[vx].second[vy*2+2]); 431 } 432 } 433 434 void build_x(int vx,int lxt, int rxt) 435 { 436 if(lxt==rxt) 437 tree[vx].first=vector< pair< int , pair< int , int > > >(pvector[lxt].second.begin(),pvector[lxt].second.end()); 438 else 439 { 440 int mxt=(lxt+rxt)/2; 441 build_x(2*vx+1,lxt,mxt); 442 build_x(2*vx+2,mxt+1,rxt); 443 for(vector< pair< int , pair< int , int > > >::iterator i=tree[2*vx+1].first.begin(),j=tree[2*vx+2].first.begin();;) 444 { 445 if(i==tree[2*vx+1].first.end()) 446 { 447 for(;j!=tree[2*vx+2].first.end();j++) 448 tree[vx].first.push_back(*j); 449 break; 450 } 451 if(j==tree[2*vx+2].first.end()) 452 { 453 for(;i!=tree[2*vx+1].first.end();i++) 454 tree[vx].first.push_back(*i); 455 break; 456 } 457 if(i->first<j->first) 458 { 459 tree[vx].first.push_back(*i); 460 i++; 461 } 462 else if(j->first<i->first) 463 { 464 tree[vx].first.push_back(*j); 465 j++; 466 } 467 else 468 { 469 tree[vx].first.push_back(make_pair(i->first,comb(i->second,j->second))); 470 i++; 471 j++; 472 } 473 } 474 } 475 tree[vx].second.resize(tree[vx].first.size()*4); 476 build_y(vx,lxt,rxt,0,0,tree[vx].first.size()-1); 477 } 478 479 pair<int,int> get_y(int vx, int vy, int lyt, int ryt, int lyc, int ryc) 480 { 481 if(lyc>ryc) 482 return make_pair(0,zmax+1); 483 if(lyc==lyt&&ryt==ryc) 484 return tree[vx].second[vy]; 485 int myt=(lyt+ryt)/2; 486 return comb(get_y(vx,vy*2+1,lyt,myt,lyc,min(ryc,myt)), 487 get_y(vx,vy*2+2,myt+1,ryt,max(lyc,myt+1),ryc)); 488 } 489 490 pair<int,int> get_x(int vx, int lxt, int rxt, int lxc, int rxc, int ly, int ry) 491 { 492 if(lxc>rxc) 493 return make_pair(0,zmax+1); 494 if(lxc==lxt&&rxt==rxc) 495 { 496 int sl,sr; 497 sl=0,sr=tree[vx].first.size()-1; 498 while(sr>sl) 499 { 500 int sm=(sl+sr)/2; 501 if(tree[vx].first[sm].first>=ly) 502 sr=sm; 503 else 504 sl=sm+1; 505 } 506 int lyc=sl; 507 sl=0,sr=tree[vx].first.size()-1; 508 while(sr>sl) 509 { 510 int sm=(sl+sr+1)/2; 511 if(tree[vx].first[sm].first<=ry) 512 sl=sm; 513 else 514 sr=sm-1; 515 } 516 int ryc=sr; 517 return (tree[vx].first[lyc].first>=ly&&tree[vx].first[ryc].first<=ry)? 518 get_y(vx,0,0,tree[vx].first.size()-1,lyc,ryc): 519 make_pair(0,(int)zmax+1); 520 } 521 int mxt=(lxt+rxt)/2; 522 return comb(get_x(vx*2+1,lxt,mxt,lxc,min(rxc,mxt),ly,ry), 523 get_x(vx*2+2,mxt+1,rxt,max(lxc,mxt+1),rxc,ly,ry)); 524 } 525 526 int main() 527 { 528 scanf("%d%d%d%d%d%d",&xmax,&ymax,&zmax,&n,&m,&k); 529 oxl=xmax; 530 oxr=1; 531 oyl=ymax; 532 oyr=1; 533 ozl=zmax; 534 ozr=1; 535 for(int i=0;i<n;i++) 536 { 537 int x,y,z; 538 scanf("%d%d%d",&x,&y,&z); 539 oxl=min(oxl,x); 540 oxr=max(oxr,x); 541 oyl=min(oyl,y); 542 oyr=max(oyr,y); 543 ozl=min(ozl,z); 544 ozr=max(ozr,z); 545 } 546 for(int i=0;i<m;i++) 547 { 548 int x,y,z; 549 scanf("%d%d%d",&x,&y,&z); 550 if(oxl<=x&&x<=oxr&&oyl<=y&&y<=oyr&&ozl<=z&&z<=ozr) 551 { 552 printf("INCORRECT\n"); 553 exit(0); 554 } 555 map< int , pair< int ,int > >::iterator it=pmap[x].insert(make_pair(y,make_pair(0,zmax+1))).first; 556 if(z<=ozr) 557 it->second.first=max(it->second.first,z); 558 if(z>=ozl) 559 it->second.second=min(it->second.second,z); 560 } 561 printf("CORRECT\n"); 562 if(m>0) 563 { 564 pvector=vector< pair< int , map< int , pair< int ,int > > > >(pmap.begin(),pmap.end()); 565 tree.resize(pvector.size()*4); 566 build_x(0,0,pvector.size()-1); 567 } 568 for(int i=0;i<k;i++) 569 { 570 int x,y,z; 571 scanf("%d%d%d",&x,&y,&z); 572 if(oxl<=x&&x<=oxr&&oyl<=y&&y<=oyr&&ozl<=z&&z<=ozr) 573 { 574 printf("OPEN\n"); 575 continue; 576 } 577 if(m==0) 578 { 579 printf("UNKNOWN\n"); 580 continue; 581 } 582 bool closed=false; 583 for(int ii=0;ii<=1;ii++) 584 for(int jj=0;jj<=1;jj++) 585 { 586 if(closed) 587 break; 588 int i=oxl+ii*(oxr-oxl); 589 int j=oyl+jj*(oyr-oyl); 590 int lx=min(x,i),rx=max(x,i); 591 int sl,sr; 592 sl=0,sr=pvector.size()-1; 593 while(sr>sl) 594 { 595 int sm=(sl+sr)/2; 596 if(pvector[sm].first>=lx) 597 sr=sm; 598 else 599 sl=sm+1; 600 } 601 int lxc=sl; 602 sl=0,sr=pvector.size()-1; 603 while(sr>sl) 604 { 605 int sm=(sl+sr+1)/2; 606 if(pvector[sm].first<=rx) 607 sl=sm; 608 else 609 sr=sm-1; 610 } 611 int rxc=sr; 612 if(pvector[lxc].first>=lx&&pvector[rxc].first<=rx) 613 { 614 pair<int,int> p=get_x(0,0,pvector.size()-1,lxc,rxc,min(y,j),max(y,j)); 615 if(min({z,ozl,ozr})<=p.first||max({z,ozl,ozr})>=p.second) 616 closed=true; 617 } 618 } 619 if(closed) 620 printf("CLOSED\n"); 621 else 622 printf("UNKNOWN\n"); 623 } 624 } 625 ``` 626 627 [1010F - Tree](/contest/1010/problem/F "Codeforces Round 499 (Div. 1)") 628 629 Authors: Ildar Gainullin ([300iq](/profile/300iq "Grandmaster 300iq")) and Dmitry Sayutin ([cdkrot](/profile/cdkrot "International Master cdkrot")). 630 631 **Tutorial** 632 633 Tutorial is loading... 634 635 **Solution** 636 637 ``` 638 #include <cmath> 639 #include <iostream> 640 #include <vector> 641 #include <algorithm> 642 #include <string> 643 #include <set> 644 #include <map> 645 #include <list> 646 #include <time.h> 647 #include <math.h> 648 #include <random> 649 #include <deque> 650 #include <queue> 651 #include <cassert> 652 #include <unordered_map> 653 #include <unordered_set> 654 #include <iomanip> 655 #include <bitset> 656 #include <sstream> 657 658 using namespace std; 659 660 typedef long long ll; 661 662 mt19937 rnd(228); 663 664 const int md = 998244353; 665 666 inline void add(int &a, int b) { 667 a += b; 668 if (a >= md) a -= md; 669 } 670 671 inline void sub(int &a, int b) { 672 a -= b; 673 if (a < 0) a += md; 674 } 675 676 inline int mul(int a, int b) { 677 #if !defined(_WIN32) || defined(_WIN64) 678 return (int) ((long long) a * b % md); 679 #endif 680 unsigned long long x = (long long) a * b; 681 unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m; 682 asm( 683 "divl %4; \n\t" 684 : "=a" (d), "=d" (m) 685 : "d" (xh), "a" (xl), "r" (md) 686 ); 687 return m; 688 } 689 690 inline int power(int a, long long b) { 691 int res = 1; 692 while (b > 0) { 693 if (b & 1) { 694 res = mul(res, a); 695 } 696 a = mul(a, a); 697 b >>= 1; 698 } 699 return res; 700 } 701 702 inline int inv(int a) { 703 a %= md; 704 if (a < 0) a += md; 705 int b = md, u = 0, v = 1; 706 while (a) { 707 int t = b / a; 708 b -= t * a; swap(a, b); 709 u -= t * v; swap(u, v); 710 } 711 assert(b == 1); 712 if (u < 0) u += md; 713 return u; 714 } 715 716 namespace ntt { 717 int base = 1; 718 vector<int> roots = {0, 1}; 719 vector<int> rev = {0, 1}; 720 int max_base = -1; 721 int root = -1; 722 723 void init() { 724 int tmp = md - 1; 725 max_base = 0; 726 while (tmp % 2 == 0) { 727 tmp /= 2; 728 max_base++; 729 } 730 root = 2; 731 while (true) { 732 if (power(root, 1 << max_base) == 1) { 733 if (power(root, 1 << (max_base - 1)) != 1) { 734 break; 735 } 736 } 737 root++; 738 } 739 } 740 741 void ensure_base(int nbase) { 742 if (max_base == -1) { 743 init(); 744 } 745 if (nbase <= base) { 746 return; 747 } 748 assert(nbase <= max_base); 749 rev.resize(1 << nbase); 750 for (int i = 0; i < (1 << nbase); i++) { 751 rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1)); 752 } 753 roots.resize(1 << nbase); 754 while (base < nbase) { 755 int z = power(root, 1 << (max_base - 1 - base)); 756 for (int i = 1 << (base - 1); i < (1 << base); i++) { 757 roots[i << 1] = roots[i]; 758 roots[(i << 1) + 1] = mul(roots[i], z); 759 } 760 base++; 761 } 762 } 763 764 void fft(vector<int> &a) { 765 int n = (int) a.size(); 766 assert((n & (n - 1)) == 0); 767 int zeros = __builtin_ctz(n); 768 ensure_base(zeros); 769 int shift = base - zeros; 770 for (int i = 0; i < n; i++) { 771 if (i < (rev[i] >> shift)) { 772 swap(a[i], a[rev[i] >> shift]); 773 } 774 } 775 for (int k = 1; k < n; k <<= 1) { 776 for (int i = 0; i < n; i += 2 * k) { 777 for (int j = 0; j < k; j++) { 778 int x = a[i + j]; 779 int y = mul(a[i + j + k], roots[j + k]); 780 a[i + j] = x + y - md; 781 if (a[i + j] < 0) a[i + j] += md; 782 a[i + j + k] = x - y + md; 783 if (a[i + j + k] >= md) a[i + j + k] -= md; 784 } 785 } 786 } 787 } 788 789 vector<int> multiply(vector<int> a, vector<int> b, int eq = 0) { 790 int need = (int) (a.size() + b.size() - 1); 791 int nbase = 0; 792 while ((1 << nbase) < need) nbase++; 793 ensure_base(nbase); 794 int sz = 1 << nbase; 795 a.resize(sz); 796 b.resize(sz); 797 fft(a); 798 if (eq) b = a; else fft(b); 799 int inv_sz = inv(sz); 800 for (int i = 0; i < sz; i++) { 801 a[i] = mul(mul(a[i], b[i]), inv_sz); 802 } 803 reverse(a.begin() + 1, a.end()); 804 fft(a); 805 a.resize(need); 806 while (!a.empty() && a.back() == 0) { 807 a.pop_back(); 808 } 809 return a; 810 } 811 812 vector<int> square(vector<int> a) { 813 return multiply(a, a, 1); 814 } 815 }; 816 817 const int N = 1e5 + 1; 818 819 vector <vector <int> > polys[N]; 820 int l[N], r[N]; 821 int who[N]; 822 int sz[N]; 823 824 vector <int> slozh(const vector <int> &a, const vector <int> &b) 825 { 826 int n = (int) a.size(), m = (int) b.size(); 827 vector <int> c(max(n, m)); 828 for (int i = 0; i < n; i++) add(c[i], a[i]); 829 for (int i = 0; i < m; i++) add(c[i], b[i]); 830 return c; 831 } 832 833 pair <vector <int>, vector <int> > eval(const vector <vector <int> > &a) 834 { 835 if (a.size() == 1) 836 { 837 auto ret = a[0]; 838 ret[0]++; 839 return {ret, a[0]}; 840 } 841 else 842 { 843 int m = (int) a.size() / 2; 844 vector <vector <int> > l, r; 845 for (int i = 0; i < m; i++) 846 { 847 l.push_back(a[i]); 848 } 849 for (int i = m; i < (int) a.size(); i++) 850 { 851 r.push_back(a[i]); 852 } 853 auto lf = eval(l), rf = eval(r); 854 add(lf.first[0], -1); 855 auto P = slozh(ntt::multiply(lf.first, rf.second), rf.first); 856 auto Q = ntt::multiply(lf.second, rf.second); 857 return {P, Q}; 858 } 859 } 860 861 vector <int> g[N]; 862 863 void dfs(int v, int pr) 864 { 865 vector <int> go; 866 int deg = 0; 867 for (int to : g[v]) 868 { 869 if (to != pr) 870 { 871 go.push_back(to); 872 deg++; 873 } 874 } 875 if (deg == 0) 876 { 877 polys[v].push_back({0, 1}); 878 sz[v] = 1; 879 who[v] = v; 880 } 881 else 882 { 883 if (deg == 2) 884 { 885 l[v] = go[0]; 886 r[v] = go[1]; 887 dfs(l[v], v); 888 dfs(r[v], v); 889 sz[v] = sz[l[v]] + sz[r[v]] + 1; 890 if (sz[l[v]] < sz[r[v]]) 891 { 892 swap(l[v], r[v]); 893 } 894 auto go = eval(polys[who[r[v]]]).first; 895 go.insert(go.begin(), 0); 896 polys[who[l[v]]].push_back(go); 897 who[v] = who[l[v]]; 898 } 899 else 900 { 901 int son = go[0]; 902 dfs(son, v); 903 sz[v] = sz[son] + 1; 904 who[v] = who[son]; 905 polys[who[v]].push_back({0, 1}); 906 } 907 } 908 } 909 910 vector <int> binom(ll n, int k) 911 { 912 if (n == 0) 913 { 914 vector <int> ret(k + 1); 915 ret[0] = 1; 916 return ret; 917 } 918 else if (n % 2 == 0) 919 { 920 auto a = binom(n / 2, k); 921 a = ntt::square(a); 922 a.resize(k + 1); 923 return a; 924 } 925 else 926 { 927 auto a = binom(n - 1, k); 928 for (int i = k; i >= 0; i--) 929 { 930 if (i != 0) 931 { 932 add(a[i], a[i - 1]); 933 } 934 } 935 return a; 936 } 937 } 938 939 int main() 940 { 941 #ifdef ONPC 942 freopen("a.in", "r", stdin); 943 #endif 944 ios::sync_with_stdio(0); 945 cin.tie(0); 946 int n; 947 cin >> n; 948 ll x; 949 cin >> x; 950 vector <int> fact(n + 1), rev_fact(n + 1); 951 fact[0] = 1; 952 for (int i = 1; i <= n; i++) 953 { 954 fact[i] = mul(fact[i - 1], i); 955 } 956 for (int i = 0; i <= n; i++) 957 { 958 rev_fact[i] = inv(fact[i]); 959 } 960 for (int i = 1; i < n; i++) 961 { 962 int a, b; 963 cin >> a >> b; 964 a--, b--; 965 g[a].push_back(b); 966 g[b].push_back(a); 967 } 968 dfs(0, -1); 969 auto solve = eval(polys[who[0]]).first; 970 auto big_binoms = binom(x, n); 971 for (int i = 0; i <= n; i++) 972 { 973 big_binoms[i] = mul(big_binoms[i], rev_fact[i]); 974 } 975 rev_fact.insert(rev_fact.begin(), 0); 976 big_binoms = ntt::multiply(big_binoms, rev_fact); 977 int ans = 0; 978 for (int i = 1; i <= n; i++) 979 { 980 add(ans, mul(mul(solve[i], big_binoms[i]), fact[i - 1])); 981 } 982 cout << ans << '\n'; 983 } 984 ```