914.md (18894B)
1 Source: https://codeforces.com/blog/entry/57250 2 3 Tutorial is loading... 4 5 **Author:** [crvineeth97](/profile/crvineeth97 "Expert crvineeth97") 6 **Testers:** [deepanshugarg](/profile/deepanshugarg "Expert deepanshugarg"), [nir123](/profile/nir123 "Candidate Master nir123") 7 8 **Author's code** 9 10 ``` 11 #include <bits/stdc++.h> 12 using namespace std; 13 14 int main() 15 { 16 long long ans=LLONG_MIN, n, x; 17 cin>>n; 18 for (long long i = 0; i < n; i++) 19 { 20 cin>>x; 21 for (long long j = 0; j*j<=x; j++) 22 if (j*j == x) 23 x = LLONG_MIN; 24 ans = max(ans, x); 25 } 26 cout << ans << endl; 27 return 0; 28 } 29 ``` 30 31 Tutorial is loading... 32 33 **Author:** [RohanRTiwari](/profile/RohanRTiwari "Expert RohanRTiwari") 34 **Tester:** [Superty](/profile/Superty "Candidate Master Superty") 35 36 **Author's code** 37 38 ``` 39 #include <bits/stdc++.h> 40 using namespace std; 41 using ll = long long; 42 43 int cnt[100005]; 44 45 int main() { 46 ios::sync_with_stdio(false); 47 48 int n; 49 cin >> n; 50 while(n--) { 51 int x; 52 cin >> x; 53 cnt[x]++; 54 } 55 56 for (int i = 1; i <= 1e5; i++) { 57 if (cnt[i] % 2 == 1) { 58 cout << "Conan\n"; 59 return 0; 60 } 61 } 62 cout << "Agasa\n"; 63 return 0; 64 } 65 ``` 66 67 Tutorial is loading... 68 69 **Author:** [aman_shahi2](/profile/aman_shahi2 "Expert aman_shahi2") 70 **Tester:** [mprocks](/profile/mprocks "Expert mprocks") 71 72 **Author's code** 73 74 ``` 75 #include <bits/stdc++.h> 76 using namespace std; 77 78 #define MOD 1000000007 79 80 int dp[1004]; 81 long long ncr[1004][1004]; 82 83 int ones(int n) 84 { 85 int cnt = 0; 86 while(n) 87 { 88 if(n%2 == 1) 89 { 90 cnt++; 91 } 92 n /= 2; 93 } 94 return cnt; 95 } 96 97 void calcncr() 98 { 99 for(int i = 0; i <= 1000; i++) 100 { 101 ncr[i][0] = 1; 102 } 103 for(int i = 1; i <= 1000; i++) 104 { 105 for(int j = 1; j <= 1000; j++) 106 { 107 ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j])%MOD; 108 } 109 } 110 } 111 112 int main() 113 { 114 string n; 115 int k; 116 calcncr(); 117 118 dp[1] = 0; 119 for(int i = 2; i <= 1000; i++) 120 { 121 dp[i] = dp[ones(i)] + 1; 122 } 123 124 cin >> n >> k; 125 126 if(k == 0) 127 { 128 cout << "1\n"; 129 return 0; 130 } 131 132 long long nones = 0, ans = 0; 133 for(int i = 0; i < n.size(); i++) 134 { 135 if(n[i] == '0') 136 { 137 continue; 138 } 139 for(int j = max(nones, 1LL); j < 1000; j++) 140 { 141 if(dp[j] == k-1) 142 { 143 ans = (ans + ncr[n.size()-i-1][j-nones])%MOD; 144 if(i == 0 && k == 1) 145 { 146 ans = (ans+MOD-1)%MOD; 147 } 148 } 149 } 150 nones++; 151 } 152 153 int cnt = 0; 154 for(int i = 0; i < n.size(); i++) 155 { 156 if(n[i] == '1') 157 { 158 cnt++; 159 } 160 } 161 if(dp[cnt] == k-1) 162 { 163 ans = (ans + 1)%MOD; 164 } 165 cout << ans << endl; 166 167 return 0; 168 } 169 ``` 170 171 Tutorial is loading... 172 173 **Author:** [RohanRTiwari](/profile/RohanRTiwari "Expert RohanRTiwari") 174 **Testers:** [codelegend](/profile/codelegend "Candidate Master codelegend"), [Superty](/profile/Superty "Candidate Master Superty") 175 176 **Author's code** 177 178 ``` 179 #include <bits/stdc++.h> 180 using namespace std; 181 using ll = long long; 182 183 int tree[2000000]; 184 int trstp = 1; 185 186 int gcd(int x, int y) { 187 return y == 0 ? x : gcd(y, x % y); 188 } 189 190 void query(int root, int u, int v, int x, int s, int e, int& ans) { 191 if (e < s || v < u || e < u || v < s) { 192 return; 193 } else if (u <= s && e <= v) { 194 if (tree[root] % x == 0) { 195 return; 196 } else { 197 while (root < trstp) { 198 if (tree[2*root] % x != 0) { 199 if (tree[2*root + 1] % x != 0) { 200 ans += 2; 201 return; 202 } 203 root = 2*root; 204 } else { 205 root = 2*root + 1; 206 } 207 } 208 ans++; 209 return; 210 } 211 } 212 int mid = (s + e)/2; 213 query(2*root, u, v, x, s, mid, ans); 214 if (ans > 1) { 215 return; 216 } 217 query(2*root + 1, u, v, x, mid + 1, e, ans); 218 } 219 220 void update(int p, int x) { 221 p += trstp - 1; 222 tree[p] = x; 223 224 p /= 2; 225 while (p > 0) { 226 tree[p] = gcd(tree[2*p], tree[2*p + 1]); 227 p /= 2; 228 } 229 } 230 231 int main() { 232 ios::sync_with_stdio(false); 233 cin.tie(NULL); 234 235 int n; 236 cin >> n; 237 while (trstp < n) { 238 trstp *= 2; 239 } 240 241 for (int i = trstp; i < trstp + n; i++) { 242 cin >> tree[i]; 243 } 244 for (int i = trstp - 1; i >= 1; i--) { 245 tree[i] = gcd(tree[2*i], tree[2*i + 1]); 246 } 247 248 int q; 249 cin >> q; 250 while (q--) { 251 int t; 252 cin >> t; 253 if (t == 1) { 254 int l, r; 255 int x; 256 cin >> l >> r >> x; 257 int ans = 0; 258 query(1, l, r, x, 1, trstp, ans); 259 cout << (ans <= 1 ? "YES\n" : "NO\n"); 260 } else { 261 int i; 262 int y; 263 cin >> i >> y; 264 update(i, y); 265 } 266 } 267 268 return 0; 269 } 270 ``` 271 272 Tutorial is loading... 273 274 **Author:** [born2rule](/profile/born2rule "Candidate Master born2rule") 275 **Testers:** [devanshg27](/profile/devanshg27 "Candidate Master devanshg27"), [FundamentalEq](/profile/FundamentalEq "Candidate Master FundamentalEq") 276 277 **Author's code** 278 279 ``` 280 #include <bits/stdc++.h> 281 #include <ext/pb_ds/assoc_container.hpp> 282 #include <ext/pb_ds/tree_policy.hpp> 283 using namespace std; 284 using namespace __gnu_pbds; 285 286 #define ll long long 287 #define db long double 288 #define ii pair<int,int> 289 #define vi vector<int> 290 #define fi first 291 #define se second 292 #define sz(a) (int)(a).size() 293 #define all(a) (a).begin(),(a).end() 294 #define pb emplace_back 295 #define mp make_pair 296 #define FN(i, n) for (int i = 0; i < (int)(n); ++i) 297 #define FEN(i,n) for (int i = 1;i <= (int)(n); ++i) 298 #define rep(i,a,b) for(int i=a;i<b;i++) 299 #define repv(i,a,b) for(int i=b-1;i>=a;i--) 300 #define SET(A, val) memset(A, val, sizeof(A)) 301 typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ; 302 // order_of_key (val): returns the no. of values less than val 303 // find_by_order (k): returns the kth largest element.(0-based) 304 #define TRACE 305 #ifdef TRACE 306 #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) 307 template <typename Arg1> 308 void __f(const char* name, Arg1&& arg1){ 309 cerr << name << " : " << arg1 << std::endl; 310 } 311 template <typename Arg1, typename... Args> 312 void __f(const char* names, Arg1&& arg1, Args&&... args){ 313 const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); 314 } 315 #else 316 #define trace(...) 317 #endif 318 const int L=200005,N=(1<<20); 319 //call dfsMCT,change solve and dfs1 320 vi vpart[L],ad[L]; bool vis[L];//par:parent in cent|H:depth 321 int SZ[L],par[L],part[L],H[L],cpart;//cpart:no of parts in cent 322 ll ans[L],dp[L]; 323 string s; 324 int dfsSZ(int u,int p=-1) 325 { 326 SZ[u]=1;//vpart[i]:nodes in part i 327 for(int v:ad[u]) 328 if(!vis[v] && v!=p) 329 SZ[u]+=dfsSZ(v,u); 330 return SZ[u]; 331 } 332 int dfsFC(int u,int r,int p=-1) 333 { 334 for(int v:ad[u]) 335 if(!vis[v] && v!=p) 336 { 337 if(SZ[v]>SZ[r]/2) 338 return dfsFC(v,r,u); 339 } 340 return u; 341 } 342 int cnt[N],val[L],tmp[N]; 343 void dfs1(int u,int r,int p=-1) 344 { 345 dp[u]=0; 346 if(p==r) 347 { 348 part[u]=++cpart; 349 vpart[cpart].clear(); 350 } 351 else if(p!=-1) part[u]=part[p]; 352 if(p!=-1) vpart[cpart].pb(u); 353 for(int v1:ad[u]) 354 if(!vis[v1]&&v1!=p) 355 { 356 H[v1]=H[u]+1; 357 val[v1]=(val[u]^(1<<(s[v1-1]-'a'))); 358 dfs1(v1,r,u); 359 } 360 } 361 void dfs2(int u,int r,int par=-1) 362 { 363 dp[u]=cnt[val[u]]; 364 rep(i,0,20) 365 dp[u]+=cnt[val[u]^(1<<i)]; 366 for(int v1:ad[u]) 367 { 368 if(vis[v1] || v1==par) continue; 369 dfs2(v1,r,u); 370 dp[u]+=dp[v1]; 371 } 372 ans[u]+=dp[u]; 373 } 374 void solve(int r,int szr) 375 { 376 H[r]=cpart=0; 377 val[r]=(1<<(s[r-1]-'a')); 378 dfs1(r,r); 379 rep(i,1,cpart+1) 380 for(int v1:vpart[i]) 381 cnt[val[v1]]++; 382 cnt[val[r]]++; 383 rep(i,1,cpart+1) 384 { 385 for(int v1:vpart[i]) 386 { 387 cnt[val[v1]]--; 388 val[v1]^=(1<<(s[r-1]-'a')); 389 tmp[val[v1]]++; 390 } 391 for(int v1:vpart[i]) 392 { 393 if(tmp[val[v1]]) 394 { 395 dp[r]+=(ll)tmp[val[v1]]*cnt[val[v1]]; 396 rep(j,0,20) 397 dp[r]+=(ll)tmp[val[v1]]*cnt[val[v1]^(1<<j)]; 398 tmp[val[v1]]=0; 399 } 400 } 401 dfs2(vpart[i][0],r,r); 402 for(int v1:vpart[i]) 403 { 404 val[v1]^=(1<<(s[r-1]-'a')); 405 cnt[val[v1]]++; 406 } 407 } 408 cnt[val[r]]--; 409 dp[r]+=cnt[0]; 410 rep(i,0,20) 411 dp[r]+=cnt[(1<<i)]; 412 ans[r]+=dp[r]/2; 413 rep(i,1,cpart+1) 414 for(int v1:vpart[i]) cnt[val[v1]]--; 415 } 416 void dfsMCT(int u,int p=-1) 417 { 418 dfsSZ(u); 419 int r=dfsFC(u,u); 420 par[r]=p; solve(r,SZ[u]); vis[r]=true; 421 for(int v:ad[r]) 422 if(!vis[v]) dfsMCT(v,r); 423 } 424 int main() 425 { 426 std::ios::sync_with_stdio(false); 427 cin.tie(NULL) ; cout.tie(NULL) ; 428 int n,x,y; 429 cin>>n; 430 rep(i,1,n) 431 { 432 cin>>x>>y; 433 ad[x].pb(y); ad[y].pb(x); 434 } 435 cin>>s; 436 dfsMCT(1); 437 rep(i,1,n+1) cout<<ans[i]+1<<" "; 438 cout<<endl; 439 return 0 ; 440 } 441 ``` 442 443 Tutorial is loading... 444 445 There was an unexpected solution that involved bitset that runs in complexity *O*(*N*2 / 32). Have a look at [Syloviaely](/profile/Syloviaely "Legendary Grandmaster Syloviaely") 's code: [34364964](/contest/914/submission/34364964 "Submission 34364964 by Syloviaely") 446 447 **Author:** [RohanRTiwari](/profile/RohanRTiwari "Expert RohanRTiwari") 448 **Testers:** [born2rule](/profile/born2rule "Candidate Master born2rule"), [devanshg27](/profile/devanshg27 "Candidate Master devanshg27"), [additya1998](/profile/additya1998 "Candidate Master additya1998"), [virus_1010](/profile/virus_1010 "Expert virus_1010"), [nir123](/profile/nir123 "Candidate Master nir123") 449 450 **Author's code** 451 452 ``` 453 #include <bits/stdc++.h> 454 #define fr(x) scanf("%d", &x) 455 #define SQRN 150 456 using namespace std; 457 458 const int sa = 2 * SQRN + 10; 459 const int LEN = 100010; 460 char s[LEN], sq[LEN], zstring[2*LEN]; 461 int z[2*LEN]; 462 string temps; 463 464 struct SuffixAutomaton { 465 int edges[26][sa], link[sa], length[sa], isTerminal[sa], dp1[sa], last; 466 int sz; 467 SuffixAutomaton() { 468 last = 0; 469 sz = 0; 470 } 471 472 void set(int k) { 473 for(int i = 0; i < 26; ++i) edges[i][k] = -1; 474 } 475 476 void build(string &s) { 477 link[0] = -1; 478 length[0] = 0; 479 last = 0; 480 sz = 1; 481 set(0); 482 483 for(int i=0;i<s.size();i++) { 484 set(sz); 485 length[sz] = i+1; 486 link[sz] = 0; 487 int r = sz; 488 ++sz; 489 490 int p = last; 491 while(p >= 0 && edges[s[i]-'a'][p] == -1) { 492 edges[s[i] - 'a'][p] = r; 493 p = link[p]; 494 } 495 if(p != -1) { 496 int q = edges[s[i] - 'a'][p]; 497 if(length[p] + 1 == length[q]) { 498 link[r] = q; 499 } else { 500 for(int i = 0; i < 26; ++i) { 501 edges[i][sz] = edges[i][q]; 502 } 503 length[sz] = length[p] + 1; 504 link[sz] = link[q]; 505 int qq = sz; 506 ++sz; 507 link[q] = qq; 508 link[r] = qq; 509 while(p >= 0 && edges[s[i] - 'a'][p] == q) { 510 edges[s[i] - 'a'][p] = qq; 511 p = link[p]; 512 } 513 } 514 } 515 last = r; 516 } 517 for(int i = 0; i < sz; ++i) isTerminal[i] = 0, dp1[i] = -1; 518 int p = last; 519 while(p > 0) { 520 isTerminal[p] = 1; 521 p = link[p]; 522 } 523 } 524 525 int solve(int pos) { 526 if(dp1[pos] != -1) return dp1[pos]; 527 dp1[pos] = isTerminal[pos]; 528 for(int i=0; i<26; ++i){ 529 if(edges[i][pos] != -1) dp1[pos] += solve(edges[i][pos]); 530 } 531 return dp1[pos]; 532 } 533 534 int run() { 535 int cur = 0; 536 for(int i=1; sq[i] != '\0'; ++i) { 537 auto it = edges[sq[i] - 'a'][cur]; 538 if(it == -1) return 0; 539 else cur = it; 540 } 541 return solve(cur); 542 } 543 } SA[800]; 544 545 void computeZ() { 546 int l, r; 547 z[0] = 0; 548 l = r = -1; 549 for(int i=1; zstring[i] != '\0'; ++i) { 550 z[i]=0; 551 if(r>i) { 552 z[i]=min(z[i-l], r-i+1); 553 } 554 while(zstring[i+z[i]] == zstring[z[i]]) ++z[i]; 555 if(i+z[i]-1 > r) { 556 r = i+z[i]-1; 557 l = i; 558 } 559 } 560 } 561 562 int computeBrute(int l, int r, int sqlen) { 563 int zslen = 0, ans = 0; 564 for(int i=1; i<=sqlen; ++i) { 565 zstring[zslen++] = sq[i]; 566 } 567 zstring[zslen++] = '$'; 568 for(int i=l; i<=r; ++i) { 569 zstring[zslen++] = s[i]; 570 } 571 zstring[zslen] = '\0'; 572 computeZ(); 573 for(int i=1; i<zslen; ++i) { 574 if(z[i] >= sqlen) { 575 ++ans; 576 } 577 } 578 return ans; 579 } 580 581 int main() { 582 int q, typ, l, r, slen; 583 char ch; 584 scanf(" %s", &s[1]); 585 slen = strlen(&s[1]); 586 fr(q); 587 for(int i=0; i<=slen; i+=SQRN) { 588 temps = ""; 589 int tempr = min(i+SQRN-1, slen); 590 for(int j=max(1, i); j<=tempr; ++j) { 591 temps += s[j]; 592 } 593 SA[i/SQRN].build(temps); 594 } 595 while(q--) { 596 fr(typ); 597 if(typ == 1) { 598 scanf("%d %c", &l, &ch); 599 s[l] = ch; 600 temps = ""; 601 int bkt = l/SQRN; 602 int tempr = min(slen, (bkt+1)*SQRN-1); 603 for(int i=max(1,bkt*SQRN); i<=tempr; ++i) { 604 temps += s[i]; 605 } 606 SA[bkt].build(temps); 607 } 608 else { 609 scanf("%d %d %s", &l, &r, &sq[1]); 610 int sqlen = strlen(&sq[1]); 611 if(sqlen >= SQRN || r-l <= 2*SQRN) { 612 printf("%d\n", computeBrute(l, r, sqlen)); 613 } 614 else { 615 int lbkt = l/SQRN, rbkt = r/SQRN, ans = 0; 616 for(int i=lbkt+1; i<rbkt; ++i) { 617 ans += SA[i].run(); 618 } 619 ans += computeBrute(l, (lbkt+1)*SQRN-1, sqlen); 620 ans += computeBrute(rbkt*SQRN, r, sqlen); 621 for(int i=lbkt+1; i<=rbkt; ++i) { 622 ans += computeBrute(max(l, i*SQRN - sqlen + 1), min(r, i*SQRN + sqlen - 2), sqlen); 623 } 624 printf("%d\n", ans); 625 } 626 } 627 } 628 return 0; 629 } 630 ``` 631 632 Tutorial is loading... 633 634 **Author:** [FundamentalEq](/profile/FundamentalEq "Candidate Master FundamentalEq") 635 **Tester:** [born2rule](/profile/born2rule "Candidate Master born2rule") 636 637 **Author's code** 638 639 ``` 640 #include <bits/stdc++.h> 641 #include <ext/pb_ds/assoc_container.hpp> 642 #include <ext/pb_ds/tree_policy.hpp> 643 using namespace std; 644 using namespace __gnu_pbds; 645 646 #define ll long long 647 #define db long double 648 #define ii pair<int,int> 649 #define vi vector<int> 650 #define fi first 651 #define se second 652 #define sz(a) (int)(a).size() 653 #define all(a) (a).begin(),(a).end() 654 #define pb push_back 655 #define mp make_pair 656 #define FN(i, n) for (int i = 0; i < (int)(n); ++i) 657 #define FEN(i,n) for (int i = 1;i <= (int)(n); ++i) 658 #define rep(i,a,b) for(int i=a;i<b;i++) 659 #define repv(i,a,b) for(int i=b-1;i>=a;i--) 660 #define SET(A, val) memset(A, val, sizeof(A)) 661 typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ; 662 // order_of_key (val): returns the no. of values less than val 663 // find_by_order (k): returns the kth largest element.(0-based) 664 #define TRACE 665 #ifdef TRACE 666 #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) 667 template <typename Arg1> 668 void __f(const char* name, Arg1&& arg1){ 669 cerr << name << " : " << arg1 << std::endl; 670 } 671 template <typename Arg1, typename... Args> 672 void __f(const char* names, Arg1&& arg1, Args&&... args){ 673 const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); 674 } 675 #else 676 #define trace(...) 677 #endif 678 const int L = 17 ; 679 const int L2 = 1<<L ; 680 const int mod = 1e9+7 ; 681 int sbits[L2] ; 682 vi oddbits ; 683 inline int add(int x,int y) 684 { 685 x+=y; 686 if(x>=mod) x-=mod; 687 if(x<0) x+=mod; 688 return x; 689 } 690 inline int mult(int x,int y) 691 { 692 ll tmp=(ll)x*y; 693 if(tmp>=mod) tmp%=mod; 694 return tmp; 695 } 696 inline int pwmod(int x,int y) 697 { 698 int ans=1; 699 while(y){if(y&1)ans=mult(ans,x);y>>=1;x=mult(x,x);} 700 return ans; 701 } 702 vector<ii> nus[L] ; 703 void zeta(int A[L2]) 704 { 705 FN(i,L) 706 { 707 for(ii m:nus[i]) A[m.fi]=add(A[m.fi],A[m.se]) ; 708 } 709 } 710 711 void meu(int A[L2]) 712 { 713 for(int i:oddbits) A[i] = mod - A[i] ; 714 zeta(A) ; 715 for(int i:oddbits) A[i] = mod - A[i] ; 716 } 717 void conv(int A[L2],int B[L2]) 718 { 719 zeta(A), zeta(B);//return 720 FN(i,L2) A[i]=mult(A[i],B[i]); 721 meu(A); 722 } 723 int t[L+1][L2],t1[L2] ; 724 void subsetconv(int A[L2],int ans[L2]) 725 { 726 FN(i,L2) t[sbits[i]][i] = A[i] ; 727 FN(i,L+1) zeta(t[i]) ; 728 FN(c,L+1) FN(a,c+1) 729 { 730 int *t2 = t[a], *t3 = t[c-a] ; 731 FN(i,L2) t1[i]=mult(t2[i],t3[i]) ; 732 meu(t1) ; 733 FN(i,L2) if(sbits[i] == c) ans[i]=add(ans[i],t1[i]) ; 734 } 735 } 736 vector<ii> su[L] ; 737 738 void transform(int p[L2],bool inv=false){ int u,v; 739 for(int len=1,l=2;l<=L2;len<<=1,l<<=1)for(int 740 i=0;i<L2;i+=l) FN(j,len){ 741 u=p[i+j],v=p[i+j+len] ; 742 if(inv) {p[i+j]=add(u,v),p[i+j+len]=add(u,-v);} 743 else {p[i+j]=add(u,v),p[i+j+len]=add(u,-v);}} 744 if(inv){int d=pwmod(L2,mod-2);FN(i,L2)p[i]=mult(p[i],d);} } 745 746 int cnt[L2],fib[L2],A[L2],B[L2],C[L2],a[L2],b[L2],c[L2] ; 747 748 int main() 749 { 750 std::ios::sync_with_stdio(false); 751 cin.tie(NULL) ; cout.tie(NULL) ; 752 FN(i,L2) 753 { 754 sbits[i] = __builtin_popcount(i) ; 755 if(sbits[i] & 1) oddbits.emplace_back(i) ; 756 FN(j,L) 757 { 758 if(i&(1<<j)) nus[j].emplace_back(mp(i,i^(1<<j))) ; 759 if((i&(1<<j)) == 0) su[j].emplace_back(mp(i,i^(1<<j))) ; 760 } 761 } 762 FN(i,L) reverse(all(su[i])) ; 763 fib[1] = 1 ; rep(i,2,L2) fib[i] = add(fib[i-1],fib[i-2]) ; 764 765 int N,x ; cin>>N ; 766 FN(i,N) 767 { 768 cin>>x, ++cnt[x] ; 769 } 770 771 subsetconv(cnt,A) ; 772 FN(i,L2) A[i]=mult(A[i],fib[i]) ; 773 774 FN(i,L2) B[i]=mult(cnt[i],fib[i]); 775 FN(i,L2) C[i]=cnt[i] ; 776 transform(C) ; 777 FN(i,L2) C[i]=mult(C[i],C[i]) ; 778 transform(C,1) ; 779 FN(i,L2) C[i]=mult(C[i],fib[i]) ; 780 int ans = 0 ; 781 FN(p,L) 782 { 783 FN(i,L2) a[i]=b[i]=c[i]=0 ; 784 for(ii m:nus[p]) a[m.se]=A[m.fi],b[m.se]=B[m.fi],c[m.se]=C[m.fi] ; 785 FN(i,L) 786 { 787 for(ii m:su[i]) 788 { 789 a[m.fi]=add(a[m.fi],a[m.se]) ; 790 b[m.fi]=add(b[m.fi],b[m.se]) ; 791 c[m.fi]=add(c[m.fi],c[m.se]) ; 792 } 793 } 794 FN(i,L2) a[i]=mult(a[i],mult(b[i],c[i])) ; 795 meu(a) ; 796 ans = add(ans,a[(1<<L)-1]) ; 797 } 798 ans = ans == 0 ? 0 : mod - ans ; 799 cout << ans << "\n" ; 800 return 0 ; 801 } 802 ``` 803 804 Tutorial is loading... 805 806 **Author:** [Superty](/profile/Superty "Candidate Master Superty") 807 **Tester:** [codelegend](/profile/codelegend "Candidate Master codelegend") 808 809 **Author's code** 810 811 ``` 812 #include <bits/stdc++.h> 813 using namespace std; 814 using ll = long long; 815 816 ll mod; 817 const int maxn = 2e2 + 2; 818 ll tree[maxn][maxn][maxn]; 819 ll c[maxn][maxn]; 820 821 int main() { 822 ios::sync_with_stdio(false); 823 824 int n, d; 825 cin >> n >> d >> mod; 826 827 c[0][0] = 1; 828 for (int i = 1; i <= n; i++) { 829 c[i][0] = 1; 830 for (int j = 1; j <= i; j++) { 831 c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; 832 } 833 } 834 835 tree[1][1][0] = 1; 836 837 for (int i = 1; i < n; i++) { // adding trees of size i 838 for (int j = 1; j <= n; j++) { 839 for (int k = 0; k <= d; k++) { 840 tree[i + 1][j][k] = tree[i][j][k]; 841 } 842 } 843 ll tree_i = 0; 844 for (int j = 0; j < d; j++) { 845 tree_i = (tree_i + tree[i][i][j]) % mod; 846 } 847 848 ll ways = 1; 849 for (int j = 1; i*j <= n && j <= d; j++) { // adding j such trees 850 ways = (ways * c[i*j - 1][i - 1]) % mod; // ((ij)! tree[i]^(j-1))/(i!^j j!) 851 for (int k = 1; k + i*j <= n; k++) { // adding to trees of size k 852 ll cc = (ways * c[k + i*j - 1][k - 1]) % mod; 853 for (int deg = 0; deg + j <= d; deg++) { 854 tree[i + 1][k + i*j][deg + j] = (tree[i + 1][k + i*j][deg + j] + cc*((tree[i][k][deg]*tree_i) % mod)) % mod; 855 } 856 } 857 ways = (ways * tree_i) % mod; 858 } 859 } 860 861 ll total_trees = 0; 862 for (int i = 0; i <= n - 1; i++) { // there are i vertices lying on paths increasing from the root 863 for (int j = 0; j <= d; j++) { 864 for (int k = 0; j + k <= d; k++) { 865 if (k == 1) { 866 continue; 867 } 868 total_trees = (total_trees + ((tree[n][i + 1][j]*tree[n][n - i][k]) % mod)) % mod; 869 } 870 } 871 } 872 873 cout << (2*((n*(n-1)) % mod)*total_trees) % mod << '\n'; 874 875 return 0; 876 } 877 ```