1605.md (27579B)
1 Source: https://codeforces.com/blog/entry/96866 2 3 Thank you for participating! We hope you enjoyed the contest. 4 5 [1605A - A.M. Deviation](/contest/1605/problem/A "Codeforces Round 754 (Div. 2)") 6 7 Authored and prepared by [JeevanJyot](/profile/JeevanJyot "Master JeevanJyot") 8 9 **Hint 1** 10 11 What happens to the value of $d(a_1, a_2, a_3)$ if you perform an operation on $a_1$ and $a_3$? 12 13 **Hint 2** 14 15 What happens if you perform an operation on $a_1$ and $a_2$? 16 17 **Hint 3** 18 19 Can we use negative values to improve the worst answer? 20 21 **Solution** 22 23 Tutorial is loading... 24 25 **Solution [c++] (JeevanJyot)** 26 27 ``` 28 #include <bits/stdc++.h> 29 using namespace std; 30 31 int32_t main() 32 { 33 ios_base::sync_with_stdio(0); 34 cin.tie(0); cout.tie(0); 35 int T; cin >> T; 36 while(T--) 37 { 38 int a, b, c; cin >> a >> b >> c; 39 cout << ((a + c - 2 * b) % 3 == 0 ? 0 : 1) << "\n"; 40 } 41 return 0; 42 } 43 ``` 44 45 **Solution [Kotlin] (ExplodingFreeze)** 46 47 ``` 48 fun main(args: Array<String>) { 49 repeat(readLine()!!.toInt()) { 50 println(Math.min(readLine()!!.split(" ").map { it.toInt() }.sum() % 3, 1)) 51 } 52 } 53 ``` 54 55 **Solution [Python] (AshishGup)** 56 57 ``` 58 t=int(input()) 59 for i in range(t): 60 a,b,c=[int(x) for x in input().split()] 61 print(0 if ((a+b+c)%3 == 0) else 1) 62 ``` 63 64 [1605B - Reverse Sort](/contest/1605/problem/B "Codeforces Round 754 (Div. 2)") 65 66 Authored by [Ashishgup](/profile/Ashishgup "Grandmaster Ashishgup") and prepared by [JeevanJyot](/profile/JeevanJyot "Master JeevanJyot"). 67 68 **Hint 1** 69 70 What can you say about the number of $0$s and $1$s that are in positions where they should not be in the final string? 71 72 **Hint 2** 73 74 What is the minimum number of operations required to sort the string given this relationship between the number of such $0$s and $1$s? 75 76 **Solution** 77 78 Tutorial is loading... 79 80 **Solution [c++] (JeevanJyot)** 81 82 ``` 83 #include <bits/stdc++.h> 84 using namespace std; 85 86 int32_t main() 87 { 88 ios_base::sync_with_stdio(0); 89 cin.tie(0); cout.tie(0); 90 int T; cin >> T; 91 while(T--) 92 { 93 int n; cin >> n; 94 string s; cin >> s; 95 if(is_sorted(s.begin(), s.end())) 96 { 97 cout << 0 << "\n"; 98 continue; 99 } 100 101 string t = s; 102 sort(t.begin(), t.end()); 103 cout << 1 << "\n"; 104 vector<int> ans; 105 for(int i = 0; i < n; i++) 106 { 107 if(s[i] != t[i]) 108 ans.push_back(i+1); 109 } 110 cout << ans.size() << " "; 111 for(int i = 0; i < ans.size(); i++) 112 cout << ans[i] << " \n"[i+1 == ans.size()]; 113 } 114 return 0; 115 } 116 ``` 117 118 **Solution [Kotlin] (ExplodingFreeze)** 119 120 ``` 121 fun main(args: Array<String>) { 122 repeat(readLine()!!.toInt()) { 123 val n = readLine()!!.toInt() 124 val s = readLine()!! 125 if("10" in s) { 126 println(1); 127 val res = s.toCharArray().sorted().withIndex().filter { it.value != s[it.index] }.map { it.index + 1 } 128 println("${res.size} ${res.joinToString(" ")}"); 129 } else { 130 println(0); 131 } 132 133 } 134 } 135 ``` 136 137 **Solution [Python] (AshishGup)** 138 139 ``` 140 q = int(input()) 141 for tc in range(q): 142 n = int(input()) 143 s = input() 144 t = ''.join(sorted(s)) 145 ans = [] 146 for i in range(len(s)): 147 if s[i] != t[i]: 148 ans.append(i) 149 val = 1 if len(ans) > 0 else 0 150 print(val) 151 if val > 0: 152 print(len(ans), end = " ") 153 for elem in range(len(ans)): 154 print(ans[elem] + 1, end = " ") 155 print() 156 ``` 157 158 [1605C - Dominant Character](/contest/1605/problem/C "Codeforces Round 754 (Div. 2)") 159 160 Authored by [Ashishgup](/profile/Ashishgup "Grandmaster Ashishgup") and prepared by [JeevanJyot](/profile/JeevanJyot "Master JeevanJyot"). 161 162 **Hint 1** 163 164 Think about small substrings. 165 166 **Hint 2** 167 168 What are the strings that satisfy the given conditions? 169 170 **Hint 3** 171 172 If you got WA on pretest $2$, then you're probably not checking $7$ length strings. 173 174 **Solution** 175 176 Tutorial is loading... 177 178 **Solution [c++] (AshishGup)** 179 180 ``` 181 #include <bits/stdc++.h> 182 using namespace std; 183 184 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 185 #define endl "\n" 186 #define int long long 187 188 const int N = 1e6 + 5; 189 190 int n; 191 string s; 192 193 int32_t main() 194 { 195 IOS; 196 int t; 197 cin >> t; 198 while(t--) 199 { 200 cin >> n >> s; 201 int ans = 1e9; 202 for(int i = 0; i < n; i++) 203 { 204 vector<int> f(3, 0); 205 f[s[i] - 'a']++; 206 for(int j = i + 1; j < min(n, i + 7); j++) 207 { 208 f[s[j] - 'a']++; 209 if(f[0] > f[1] && f[0] > f[2]) 210 ans = min(ans, j - i + 1); 211 } 212 } 213 if(ans == 1e9) 214 ans = -1; 215 cout << ans << endl; 216 } 217 return 0; 218 } 219 ``` 220 221 **Solution [Kotlin] (ExplodingFreeze)** 222 223 ``` 224 fun main(args: Array<String>) { 225 repeat(readLine()!!.toInt()) { 226 val n = readLine()!!.toInt() 227 val s = readLine()!! 228 var ans = 8; 229 for(i in 0..n-1) { 230 val cnt = IntArray(3) {0} 231 for(j in i..Math.min(i + 6, n - 1)) { 232 cnt[s[j] - 'a']++; 233 if(j > i && cnt[0] > Math.max(cnt[1], cnt[2])) 234 ans = Math.min(ans, j - i + 1); 235 } 236 } 237 if(ans > 7) 238 ans = -1; 239 println(ans) 240 } 241 } 242 ``` 243 244 [1605D - Treelabeling](/contest/1605/problem/D "Codeforces Round 754 (Div. 2)") 245 246 Authored and prepared by [the_hyp0cr1t3](/profile/the_hyp0cr1t3 "Master the_hyp0cr1t3"). 247 248 **Hint 1** 249 250 When is $u \oplus v \nleq min(u, v)$? 251 252 **Hint 2** 253 254 If $u \oplus v \nleq min(u, v)$ for any $u$ that is adjacent to $v$, the player cannot make move and will lose. 255 256 **Hint 3** 257 258 Can you relabel the nodes in such a way that $u \oplus v \nleq min(u, v)$ for any $u$ and $v$ which share an edge? Think bipartite. 259 260 **Hint 4** 261 262 The number of occurrences of (almost) every 'class' of nodes of the same kind is a unique power of $2$. 263 264 **Hint 5** 265 266 Thinking about the binary representation of a number is often useful in competitive programming. 267 268 **Solution** 269 270 Tutorial is loading... 271 272 **Solution [c++] (the_hyp0cr1t3)** 273 274 ``` 275 /** 276 * the_hyp0cr1t3 277 * 24.09.2021 01:19:28 278 **/ 279 #ifdef W 280 #include <k_II.h> 281 #else 282 #include <bits/stdc++.h> 283 using namespace std; 284 #endif 285 286 template<class T> class Y { 287 T f; 288 public: 289 template<class U> explicit Y(U&& f): f(forward<U>(f)) {} 290 template<class... Args> decltype(auto) operator()(Args&&... args) { 291 return f(ref(*this), forward<Args>(args)...); 292 } 293 }; template<class T> Y(T) -> Y<T>; 294 295 int main() { 296 ios_base::sync_with_stdio(false), cin.tie(nullptr); 297 int Q; cin >> Q; 298 299 while(Q--) []() { 300 int i, j, k, n; 301 cin >> n; 302 vector<vector<int>> g(n); 303 for(i = 0; i < n - 1; i++) { 304 int u, v; cin >> u >> v; 305 g[--u].push_back(--v); g[v].push_back(u); 306 } 307 308 int lg = 32 - __builtin_clz(n); 309 vector<vector<int>> vals(lg); 310 for(i = 1; i <= n; i++) 311 vals[31 - __builtin_clz(i)].push_back(i); 312 313 vector<int> col(n); 314 Y([&](auto dfs, int v, int p) -> void { 315 for(auto& x: g[v]) if(x ^ p) { 316 col[x] = col[v] ^ 1; 317 dfs(x, v); 318 } 319 })(0, -1); 320 321 int w = accumulate(col.begin(), col.end(), 0); 322 if(w > n - w) { 323 w = n - w; 324 for(auto& x: col) x ^= 1; 325 } 326 327 vector<int> ans(n); 328 for(i = j = k = 0; k < lg; k++) { 329 for(auto x: vals[k]) { 330 if(w >> k & 1) { 331 while(!col[i]) i++; 332 ans[i++] = x; 333 } else { 334 while(col[j]) j++; 335 ans[j++] = x; 336 } 337 } 338 } 339 340 for(i = 0; i < n; i++) 341 cout << ans[i] << " \n"[i + 1 == n]; 342 }(); 343 344 } // ~W 345 ``` 346 347 **Solution [c++] (AshishGup)** 348 349 ``` 350 #include <bits/stdc++.h> 351 using namespace std; 352 353 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 354 #define endl "\n" 355 356 const int N = 2e5 + 5; 357 358 int n; 359 int msb[N], ans[N]; 360 vector<int> nodes[2]; 361 vector<int> g[N]; 362 363 void precompute() 364 { 365 int bit = 1, cnt = 1, nxt = 2; 366 for(int i = 1; i < N; i++) 367 { 368 msb[i] = bit; 369 cnt--; 370 if(cnt == 0) 371 cnt = nxt, bit++, nxt *= 2; 372 } 373 } 374 375 void dfs(int u, int par, int col) 376 { 377 nodes[col].push_back(u); 378 for(auto &v: g[u]) 379 { 380 if(v == par) 381 continue; 382 dfs(v, u, col ^ 1); 383 } 384 } 385 386 387 int32_t main() 388 { 389 IOS; 390 precompute(); 391 int t; 392 cin >> t; 393 while(t--) 394 { 395 cin >> n; 396 for(int i = 1; i <= n; i++) 397 g[i].clear(); 398 for(int i = 1; i <= n - 1; i++) 399 { 400 int u, v; 401 cin >> u >> v; 402 g[u].push_back(v); 403 g[v].push_back(u); 404 } 405 dfs(1, 0, 0); 406 vector<vector<int> > v(20); 407 for(int i = 1; i <= n; i++) 408 v[msb[i]].push_back(i); 409 for(int i = 19; i >= 0; i--) 410 { 411 int cur = 0; 412 if(nodes[cur ^ 1].size() > nodes[cur].size()) 413 cur ^= 1; 414 for(auto &it:v[i]) 415 { 416 int node = nodes[cur].back(); 417 nodes[cur].pop_back(); 418 ans[node] = it; 419 } 420 } 421 for(int i = 1; i <= n; i++) 422 cout << ans[i] << " "; 423 cout << endl; 424 } 425 return 0; 426 } 427 ``` 428 429 **Solution [Kotlin] (ExplodingFreeze)** 430 431 ``` 432 fun dfs(x: Int, p: Int, curcol: Int, adj: Array<MutableList<Int>>, col: Array<Int>) { 433 col[x] = curcol 434 adj[x] 435 .filter { it != p } 436 .forEach { dfs(it, x, curcol xor 1, adj, col) } 437 } 438 439 fun main(args: Array<String>) { 440 val t = readLine()!!.toInt() 441 repeat(t) { 442 val n = readLine()!!.toInt() 443 val adj = Array(n) { mutableListOf<Int>() } 444 repeat(n - 1) { 445 val (u, v) = readLine()!!.split(" ").map { it.toInt() } 446 adj[u - 1].add(v - 1); 447 adj[v - 1].add(u - 1); 448 } 449 val col = Array<Int>(n) {0} 450 dfs(0, -1, 0, adj, col) 451 var s = Array(2) { mutableListOf<Int>() } 452 (0..n-1).forEach { s[col[it]].add(it) } 453 if(s[0].size < s[1].size) 454 s[0] = s[1].also { s[1] = s[0] } 455 val highestBit = Array(20) { mutableListOf<Int>() } 456 (1..n).forEach { highestBit[it.takeHighestOneBit().countTrailingZeroBits()].add(it - 1) } 457 val ans = Array<Int>(n) {-1} 458 (19 downTo 0).forEach { currentBit -> 459 val largerSet = if(s[0].size >= s[1].size) 0 else 1 460 highestBit[currentBit].forEach { it -> 461 ans[it] = s[largerSet].last() 462 s[largerSet].removeLast() 463 } 464 } 465 val pos = Array<Int>(n) {-1} 466 (0..n-1).forEach { pos[ans[it]] = it }; 467 (0..n-1).forEach { print ("${pos[it] + 1} ") } 468 println() 469 } 470 } 471 ``` 472 473 [1605E - Array Equalizer](/contest/1605/problem/E "Codeforces Round 754 (Div. 2)") 474 475 Authored and prepared by [JeevanJyot](/profile/JeevanJyot "Master JeevanJyot"). 476 477 **Hint 1** 478 479 How would you solve the problem for one query? 480 481 **Hint 2** 482 483 Assume the value of $b_1$ to be some variable, say $x$. 484 485 **Hint 3** 486 487 Try finding the number of operations applied at each index in terms of $x$. 488 489 **Solution** 490 491 Tutorial is loading... 492 493 **Solution [c++] (JeevanJyot)** 494 495 ``` 496 #include <bits/stdc++.h> 497 using namespace std; 498 499 #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) 500 #define int long long 501 #define endl "\n" 502 #define sz(w) (int)(w.size()) 503 using pii = pair<int, int>; 504 505 const double EPS = 1e-9; 506 const long long INF = 1e18; 507 508 const int N = 2e5+5; 509 510 int n, m, a[N], b[N], c[N], add[N], mob[N]; 511 512 void mobius() 513 { 514 mob[1] = 1; 515 for(int i = 2; i < N; i++) 516 { 517 mob[i]--; 518 for(int j = i + i; j < N; j += i) 519 { 520 mob[j] -= mob[i]; 521 } 522 } 523 } 524 525 int32_t main() 526 { 527 IOS; 528 mobius(); 529 cin >> n; 530 for(int i = 1; i <= n; i++) 531 cin >> a[i]; 532 for(int i = 1; i <= n; i++) 533 cin >> b[i]; 534 for(int i = 1; i <= n; i++) 535 c[i] = b[i] - a[i]; 536 c[1] = 0; 537 vector<int> z; 538 for(int i = 1; i <= n; i++) 539 { 540 int d = c[i]; 541 for(int j = i; j <= n; j += i) 542 { 543 c[j] -= d; 544 } 545 add[i] = d; 546 } 547 int ans = 0; 548 for(int i = 1; i <= n; i++) 549 { 550 if(mob[i] == 0) 551 ans += abs(add[i]); 552 else if(mob[i] == -1) 553 z.push_back(-add[i]); 554 else 555 z.push_back(add[i]); 556 } 557 sort(z.begin(), z.end()); 558 vector<int> pref = z; 559 for(int i = 1; i < sz(z); i++) 560 pref[i] = pref[i-1] + z[i]; 561 auto sum = [&pref](int l, int r) 562 { 563 if(r < 0) return 0LL; 564 int res = pref[r]; 565 if(l-1 >= 0) 566 res -= pref[l-1]; 567 return res; 568 }; 569 int q; cin >> q; 570 while(q--) 571 { 572 int x; cin >> x; 573 x -= a[1]; 574 int lo = 0, hi = sz(z)-1; 575 while(lo <= hi) 576 { 577 int mid = (lo+hi)/2; 578 if(z[mid] <= -x) 579 lo = mid+1; 580 else 581 hi = mid-1; 582 } 583 swap(lo, hi); 584 int res = sum(hi, sz(z)-1) + (sz(z)-hi) * x; 585 res -= (sum(0, lo) + (lo+1)*x); 586 cout << ans+res << endl; 587 } 588 return 0; 589 } 590 ``` 591 592 [1605F - PalindORme](/contest/1605/problem/F "Codeforces Round 754 (Div. 2)") 593 594 Authored by [ExplodingFreeze](/profile/ExplodingFreeze "Master ExplodingFreeze") and [antontrygubO_o](/profile/antontrygubO_o "Legendary Grandmaster antontrygubO_o") and prepared by [ExplodingFreeze](/profile/ExplodingFreeze "Master ExplodingFreeze"). 595 596 **Hint 1** 597 598 How can you check if an array is good? 599 600 **Hint 2** 601 602 Is there any relation between a bad array and a good array? 603 604 **Hint 3** 605 606 How can we define a unique good subsequence of a bad array? 607 608 **Hint 4** 609 610 Can we somehow count the number of bad arrays using this? 611 612 **Hint 5** 613 614 Can we modify our choice of subsequence such that we can easily count the number of ways of choosing the remaining elements? 615 616 **Solution** 617 618 Tutorial is loading... 619 620 **Solution [c++] (ExplodingFreeze)** 621 622 ``` 623 #include <bits/stdc++.h> 624 #define int long long 625 using pii=std::pair<int,int>; 626 using namespace std; 627 628 const int maxn = 105; 629 630 int t, n, k, MOD, modinv[maxn], fact[maxn], invfact[maxn], cnt_distinct_positive[maxn][maxn], cnt_total[maxn][maxn], cnt_bad[maxn][maxn], pow2[maxn * maxn]; 631 // cnt_distinct_positive[i][j] = ways of choosing i distinct positive values with a combined of exactly j bits on. 632 // cnt_total[i][j] = total number of arrays of length i with exactly j bits on in total 633 // cnt_bad[i][j] = number of bad arrays of length i with exactly j bits on in total 634 635 int mod_expo(int x, int p) 636 { 637 if(!p) 638 return 1; 639 int res = mod_expo(x, p / 2); 640 res *= res; 641 res %= MOD; 642 if(p & 1) 643 res *= x; 644 return res % MOD; 645 } 646 647 int mod_inv(int x) 648 { 649 return mod_expo(x, MOD - 2); 650 } 651 652 // O(1) with O(n) precalc needed 653 int fast_nCr(int x, int r) 654 { 655 assert(x < maxn && r >= 0 && r <= x); 656 int num = fact[x]; 657 int denom = (invfact[r] * invfact[x - r]) % MOD; 658 return (num * denom) % MOD; 659 } 660 661 // O(x - r) 662 int slow_nPr(int x, int r) 663 { 664 assert(r >= 0 && r < maxn); 665 int res = 1; 666 for(int j = 1; j <= r; j++) 667 { 668 res *= (x - j + 1 + MOD) % MOD; 669 res %= MOD; 670 } 671 return res; 672 } 673 674 int32_t main() 675 { 676 ios_base::sync_with_stdio(false); 677 cin.tie(0); 678 cin >> n >> k >> MOD; 679 fact[0] = invfact[0] = 1; 680 for(int i = 1; i < maxn; i++) 681 { 682 modinv[i] = mod_inv(i); 683 fact[i] = (fact[i - 1] * i) % MOD; 684 invfact[i] = mod_inv(fact[i]); 685 } 686 pow2[0] = 1; 687 for(int i = 1; i <= n * k; i++) 688 pow2[i] = (pow2[i - 1] * 2) % MOD; 689 for(int i = 0; i <= n; i++) 690 { 691 for(int j = 0; j <= k; j++) 692 { 693 // The number of ways of selecting i distinct positive values with upto j bits set in total 694 cnt_distinct_positive[i][j] = slow_nPr((mod_expo(2, j) - 1 + MOD) % MOD, i); 695 // The number of ways of selecting i non-negative values with upto j bits set 696 cnt_total[i][j] = pow2[i * j]; 697 // Inclusion exclusion to get the count for exactly j bits for both values. 698 for(int l = 0; l < j; l++) 699 { 700 cnt_distinct_positive[i][j] += (MOD - ((fast_nCr(j, l) * cnt_distinct_positive[i][l])) % MOD); 701 cnt_distinct_positive[i][j] %= MOD; 702 cnt_total[i][j] += (MOD - ((fast_nCr(j, l) * cnt_total[i][l])) % MOD); 703 cnt_total[i][j] %= MOD; 704 } 705 } 706 } 707 // An empty array is good. 708 cnt_total[0][0] = 1; 709 for(int i = 1; i <= n; i++) 710 for(int j = 0; j <= k; j++) 711 { 712 cnt_bad[i][j] = 0; 713 // i' <=> a, j' <=> b 714 for(int a = 0; a < i; a++) 715 for(int b = 0; b < j; b++) 716 { 717 // The only case where this incorrect addition of "bad" arrays of size $i$ occurs is when we consider good 718 // arrays of size $i - 1$ for odd $i$ during this process. So while calculating the answer for $n$ in the 719 // problem we just have to skip good arrays of size $n - 1$ if $n$ is odd. 720 if(i == n && (n & 1) && a == i - 1) 721 continue; 722 // f(i, j, i', j') 723 int cur_bad = 1; 724 // The number of ways of good arrays of length $i'$ distinct positive values with exactly $j'$ bits set in total: 725 cur_bad *= (cnt_total[a][b] - cnt_bad[a][b] + MOD) % MOD; 726 cur_bad %= MOD; 727 // The number of ways of selecting $i - i'$ distinct positive values with exactly $j - j'$ bits set in total. 728 cur_bad *= cnt_distinct_positive[i - a][j - b]; 729 cur_bad %= MOD; 730 // The number of ways of distributing the $i - i'$ values among the existing good array of length $i'$: 731 cur_bad *= fast_nCr(i, a); 732 cur_bad %= MOD; 733 // The number of ways of choosing which $j'$ of the $j$ bits were from the good array. 734 cur_bad *= fast_nCr(j, b); 735 cur_bad %= MOD; 736 // The number of ways of choosing the remaining $j'$ bits of each of the $i - i'$ distinct values. 737 cur_bad *= pow2[(i - a) * b]; 738 cur_bad %= MOD; 739 cnt_bad[i][j] += cur_bad; 740 cnt_bad[i][j] %= MOD; 741 } 742 } 743 int ans = 0; 744 for(int j = 0; j <= k; j++) 745 { 746 int cnt_good = (cnt_total[n][j] - cnt_bad[n][j] + MOD) % MOD; 747 // The number of ways of choosing the j bits from the k total bits. 748 ans += (fast_nCr(k, j) * cnt_good) % MOD; 749 ans %= MOD; 750 } 751 cout << ans << "\n"; 752 return 0; 753 } 754 ``` 755 756 **Solution [c++] (antontrygubO_o)** 757 758 ``` 759 #include <ext/pb_ds/assoc_container.hpp> 760 #include <ext/pb_ds/tree_policy.hpp> 761 #include <bits/stdc++.h> 762 #pragma GCC target ("avx2") 763 #pragma GCC optimization ("O3") 764 #pragma GCC optimization ("unroll-loops") 765 766 using namespace __gnu_pbds; 767 using namespace std; 768 769 using ll = long long; 770 using ld = long double; 771 772 typedef tree< 773 int, 774 null_type, 775 less<int>, 776 rb_tree_tag, 777 tree_order_statistics_node_update> 778 ordered_set; 779 780 #define mp make_pair 781 782 int MOD; 783 784 int mul(int a, int b) { 785 return (1LL * a * b) % MOD; 786 } 787 788 int add(int a, int b) { 789 int s = (a+b); 790 if (s>=MOD) s-=MOD; 791 return s; 792 } 793 794 int sub(int a, int b) { 795 int s = (a+MOD-b); 796 if (s>=MOD) s-=MOD; 797 return s; 798 } 799 800 int po(int a, ll deg) 801 { 802 if (deg==0) return 1; 803 if (deg%2==1) return mul(a, po(a, deg-1)); 804 int t = po(a, deg/2); 805 return mul(t, t); 806 } 807 808 int inv(int n) 809 { 810 return po(n, MOD-2); 811 } 812 813 814 mt19937 rnd(time(0)); 815 816 817 const int LIM = 40000; 818 819 vector<int> facs(LIM), invfacs(LIM); 820 821 vector<vector<int>> C(400, vector<int>(400)); 822 vector<int> degs(LIM); 823 824 void init() 825 { 826 facs[0] = 1; 827 for (int i = 1; i<LIM; i++) facs[i] = mul(facs[i-1], i); 828 invfacs[LIM-1] = inv(facs[LIM-1]); 829 for (int i = LIM-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1); 830 831 for (int i = 0; i<400; i++) 832 for (int j = 0; j<=i; j++) 833 { 834 C[i][j] = mul(facs[i], mul(invfacs[j], invfacs[i-j])); 835 } 836 degs[0] = 1; 837 for (int i = 1; i<LIM; i++) degs[i] = mul(2, degs[i-1]); 838 } 839 840 841 842 int solve1(int n, int k) 843 { 844 vector<vector<int>> ch_diff(n+1, vector<int>(k+1)); 845 846 //Choose len distinct nonzero numbers from 1 to 2^k-1 such that each bit is present somewhere 847 848 for (int len = 1; len<=n; len++) 849 { 850 for (int bits = 1; bits<=k; bits++) 851 { 852 int tot = sub(degs[bits], 1); 853 ch_diff[len][bits] = 1; 854 for (int i = 0; i<len; i++) { 855 ch_diff[len][bits] = mul(ch_diff[len][bits], sub(tot, i)); 856 } 857 //ch[len][bits] = mul(ch[len][bits], invfacs[len]); 858 859 for (int bits1 = 1; bits1<bits; bits1++) 860 { 861 ch_diff[len][bits] = sub(ch_diff[len][bits], mul(ch_diff[len][bits1], C[bits][bits1])); 862 } 863 } 864 } 865 866 ch_diff[0][0] = 1; 867 868 /*cout<<"CH_DIFF:"<<endl; 869 870 for (int len = 0; len<=n; len++) 871 { 872 cout<<len<<": "; 873 for (int bits = 0; bits<=k; bits++) 874 { 875 //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' '; 876 cout<<ch_diff[len][bits]<<' '; 877 } 878 cout<<endl; 879 }*/ 880 881 882 883 vector<vector<int>> ch(n+1, vector<int>(k+1)); 884 885 //Choose len numbers from 0 to 2^k-1 such that each bit is present somewhere 886 887 for (int len = 0; len<=n; len++) 888 { 889 for (int bits = 0; bits<=k; bits++) 890 { 891 ch[len][bits] = degs[bits*len]; 892 893 for (int bits1 = 0; bits1<bits; bits1++) 894 { 895 ch[len][bits] = sub(ch[len][bits], mul(ch[len][bits1], C[bits][bits1])); 896 } 897 } 898 } 899 900 /*cout<<"CH:"<<endl; 901 902 for (int len = 1; len<=n; len++) 903 { 904 cout<<len<<": "; 905 for (int bits = 0; bits<=k; bits++) 906 { 907 //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' '; 908 cout<<ch[len][bits]<<' '; 909 } 910 cout<<endl; 911 }*/ 912 913 914 vector<vector<int>> dp_part(n+1, vector<int>(k+1)); 915 916 //Choose len numbers from 0 to 2^k-1 such that each bit is present somewhere and it's impossible to permutate 917 918 for (int len = 1; len<=n; len++) 919 { 920 for (int bits = 0; bits<=k; bits++) 921 { 922 int ans = 0; 923 for (int sz_bad = 1; sz_bad<=len; sz_bad++) 924 for (int bits_bad = 1; bits_bad<=bits; bits_bad++) 925 { 926 int good_rem = sub(ch[len-sz_bad][bits-bits_bad], dp_part[len-sz_bad][bits-bits_bad]); 927 //good arrays of length len-sz_bad on exactly bits-bits_bad bits 928 int adding = mul(ch_diff[sz_bad][bits_bad], good_rem); 929 930 adding = mul(adding, C[len][sz_bad]); 931 adding = mul(adding, C[bits][bits_bad]); 932 adding = mul(adding, degs[(bits-bits_bad)*sz_bad]); 933 ans = add(ans, adding); 934 } 935 dp_part[len][bits] = ans; 936 } 937 } 938 939 /*cout<<"DP_PART:"<<endl; 940 941 for (int len = 1; len<=n; len++) 942 { 943 cout<<len<<": "; 944 for (int bits = 0; bits<=k; bits++) 945 { 946 //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' '; 947 cout<<dp_part[len][bits]<<' '; 948 } 949 cout<<endl; 950 }*/ 951 952 953 int answer = 0; 954 955 int min_sz_bad = 1; if (n%2==1) min_sz_bad = 2; 956 957 for (int bits = 0; bits<=k; bits++) 958 { 959 int subans = 0; 960 for (int sz_bad = min_sz_bad; sz_bad<=n; sz_bad++) 961 for (int bits_bad = 1; bits_bad<=bits; bits_bad++) 962 { 963 int good_rem = sub(ch[n-sz_bad][bits-bits_bad], dp_part[n-sz_bad][bits-bits_bad]); 964 //good arrays of length len-sz_bad on exactly bits-bits_bad bits 965 int adding = mul(ch_diff[sz_bad][bits_bad], good_rem); 966 967 adding = mul(adding, C[n][sz_bad]); 968 adding = mul(adding, C[bits][bits_bad]); 969 adding = mul(adding, degs[(bits-bits_bad)*sz_bad]); 970 subans = add(subans, adding); 971 //cout<<bits<<' '<<sz_bad<<' '<<bits_bad<<": "<<subans<<endl; 972 } 973 subans = sub(ch[n][bits], subans); 974 subans = mul(subans, C[k][bits]); 975 //cout<<ch[n][bits]<<' '<<subans<<endl; 976 answer = add(answer, subans); 977 978 } 979 return answer; 980 } 981 982 983 int main() 984 { 985 ios_base::sync_with_stdio(0); 986 cin.tie(nullptr); 987 988 int n, k; cin>>n>>k>>MOD; 989 init(); 990 cout<<solve1(n, k)<<endl; 991 992 } 993 ``` 994 995 **Solution [Kotlin] (ExplodingFreeze)** 996 997 ``` 998 fun mod_expo(base: Int, pow: Int, MOD: Int): Long { 999 if(pow == 0) { 1000 return 1; 1001 } 1002 var res = mod_expo(base, pow / 2, MOD) 1003 res = (res * res) % MOD 1004 if(pow % 2 == 1) { 1005 res = (res * base) % MOD; 1006 } 1007 return res; 1008 } 1009 1010 fun mod_inv(base: Int, MOD: Int): Long { 1011 return mod_expo(base, MOD - 2, MOD) 1012 } 1013 1014 fun fast_nCr(n: Int, r: Int, fact: Array<Long>, invfact: Array<Long>, MOD: Int): Long { 1015 val num = fact[n]; 1016 val denom = (invfact[r] * invfact[n - r]) % MOD; 1017 return (num * denom) % MOD; 1018 } 1019 1020 fun slow_nPr(n: Int, r: Int, MOD: Int): Long { 1021 var res = 1L; 1022 for(i in 1..r) { 1023 res *= (n - i + 1 + MOD) % MOD; 1024 res %= MOD; 1025 } 1026 return res; 1027 } 1028 1029 fun main(args: Array<String>) { 1030 val (n, k, MOD) = readLine()!!.split(" ").map { it.toInt() } 1031 val fact = Array<Long>(Math.max(n, k) + 1) { 1L } 1032 val invfact = Array<Long>(Math.max(n, k) + 1) { 1L } 1033 for(i in 1..Math.max(n, k)) { 1034 fact[i] = (fact[i - 1] * i) % MOD 1035 invfact[i] = mod_inv(fact[i].toInt(), MOD) 1036 } 1037 val pow2 = Array<Long>(n * k + 1) { 1 } 1038 for(i in 1..n*k) { 1039 pow2[i] = (pow2[i - 1] * 2) % MOD; 1040 } 1041 val cntDistinctPositive = Array(n + 1) { Array<Long>(k + 1) { 0L } } 1042 val cntTotal = Array(n + 1) { Array<Long>(k + 1) { 0L } } 1043 val cntBad = Array(n + 1) { Array<Long>(k + 1) { 0L } } 1044 for(i in 0..n) { 1045 for(j in 0..k) { 1046 cntDistinctPositive[i][j] = slow_nPr((mod_expo(2, j, MOD).toInt() - 1 + MOD) % MOD, i, MOD) 1047 cntTotal[i][j] = pow2[i * j] 1048 for(l in 0..j-1) { 1049 cntDistinctPositive[i][j] += (MOD - ((fast_nCr(j, l, fact, invfact, MOD) * cntDistinctPositive[i][l])) % MOD) 1050 cntDistinctPositive[i][j] = cntDistinctPositive[i][j] % MOD 1051 cntTotal[i][j] += (MOD - ((fast_nCr(j, l, fact, invfact, MOD) * cntTotal[i][l])) % MOD); 1052 cntTotal[i][j] = cntTotal[i][j] % MOD 1053 } 1054 } 1055 } 1056 cntTotal[0][0] = 1 1057 for(i in 1..n) { 1058 for(j in 0..k) { 1059 cntBad[i][j] = 0 1060 for(a in 0..i-1) { 1061 for(b in 0..j-1) { 1062 if(i == n && n % 2 == 1 && a == i - 1) { 1063 continue; 1064 } 1065 var curBad = (cntTotal[a][b] - cntBad[a][b] + MOD) % MOD 1066 curBad *= (cntDistinctPositive[i - a][j - b]) 1067 curBad = curBad % MOD 1068 curBad *= fast_nCr(i, a, fact, invfact, MOD) 1069 curBad = curBad % MOD 1070 curBad *= fast_nCr(j, b, fact, invfact, MOD) 1071 curBad = curBad % MOD 1072 curBad *= pow2[(i - a) * b] 1073 curBad = curBad % MOD 1074 cntBad[i][j] += curBad 1075 cntBad[i][j] = cntBad[i][j] % MOD 1076 } 1077 } 1078 } 1079 } 1080 var ans = 0L 1081 for(j in 0..k) { 1082 val cntGood = (cntTotal[n][j] - cntBad[n][j] + MOD) % MOD 1083 ans += (fast_nCr(k, j, fact, invfact, MOD) * cntGood) % MOD 1084 } 1085 println(ans % MOD) 1086 } 1087 ```