2134.md (25114B)
1 Source: https://codeforces.com/blog/entry/145832 2 3 Unfortunately, the round turns out to be very unbalanced :( I'm deeply sorry about this issue. 4 5 I hope you still enjoy the problems. 6 7 **Rate the contest! (definitely not copied from past contests)** 8 9 **Quality** 10 11 * Excellent contest 12 * Good contest 13 * Average contest 14 * Bad contest 15 * Horrible contest 16 17 **Difficulty** 18 19 * Trivial contest 20 * Easy contest 21 * Average contest 22 * Hard contest 23 * Impossible contest 24 25 [2134A - Painting With Two Colors](/contest/2134/problem/A "Codeforces Round 1045 (Div. 2)") 26 27 **Hint 1** 28 29 Check the parity of numbers $a$, $b$, and $n$. 30 31 **Solution** 32 33 Let us first consider the $b$ blue cells. Since all $b$ cells appear in the final painting, for the coloring to be symmetric, they must be placed at the middle of the grid. Consequently, $b$ and $n$ must have the same parity. 34 35 Next, we examine two possible cases: 36 37 * If $b \geq a$, then the blue cells can fully cover all red cells. In this situation, the value of $a$ does not affect the final coloring. 38 * If $b \lt a$, then the red cells are not completely covered by the blue ones. Therefore, the red cells must also be placed in the middle of the grid, which means $a$ and $n$ must have the same parity as well. 39 40 Thus, by checking these conditions, we can determine whether a symmetric coloring exists. This requires only $\mathcal{O}(1)$ time. 41 42 **Code (C++)** 43 44 ``` 45 #include <iostream> 46 using namespace std; 47 48 int main() { 49 ios::sync_with_stdio(false); 50 cin.tie(0); 51 int t; 52 cin >> t; 53 while (t--) { 54 int n, a, b; 55 cin >> n >> a >> b; 56 if (a <= b) { 57 cout << ((n % 2) == (b % 2) ? "YES\n" : "NO\n"); 58 } else { 59 cout << ((n % 2) == (b % 2) && (n % 2) == (a % 2) ? "YES\n" : "NO\n"); 60 } 61 } 62 } 63 ``` 64 65 **Code (Python)** 66 67 ``` 68 t = int(input()) 69 for _ in range(t): 70 n, a, b = map(int, input().split()) 71 if a <= b: 72 if n % 2 == b % 2: 73 print('YES') 74 else: 75 print('NO') 76 else: 77 if n % 2 == a % 2 and n % 2 == b % 2: 78 print('YES') 79 else: 80 print('NO') 81 ``` 82 83 **Rate the problem!** 84 85 **Quality** 86 87 * Excellent problem 88 * Good problem 89 * Average problem 90 * Bad problem 91 * Horrible problem 92 93 **Difficulty** 94 95 * Trivial problem 96 * Easy problem 97 * Average problem 98 * Hard problem 99 * Impossible problem 100 101 [2134B - Add 0 or K](/contest/2134/problem/B "Codeforces Round 1045 (Div. 2)") 102 103 There are (at least) two solutions to the problem. Vote for your solution! 104 105 **How did you solve the problem?** 106 107 * $a_i \gets a_i + k \cdot (a_i \bmod (k+1))$ 108 * Find a small prime number $p$ and make all elements divisible by $p$ 109 * Others 110 111 **Hint 1** 112 113 Find an integer $g \gt 1$ and integers $c_1, c_2, \ldots, c_n$ such that each $a_i + k \cdot c_i$ is divisible by $g$. 114 115 **Hint 2** 116 117 Decide the value of $g$ only based on $k$. There may be more than one possible choices. 118 119 **Solution** 120 121 The problem is equivalent to finding an array of $n$ non-negative integers $c_1, c_2, \ldots, c_n$ such that $0 \le c_i \le k$ for $1 \le i \le n$ and 122 123 $\gcd(a_1 + k \cdot c_1, a_2 + k \cdot c_2, \ldots, a_n + k \cdot c_n) \gt 1$ 124 125 The idea is as follows. If we can find an integer $g \gt 1$ and integers $c_1, c_2, \ldots, c_n$ such that each $a_i + k \cdot c_i$ is divisible by $g$ (for $1 \le i \le n$), then the GCD condition is satisfied. 126 127 There are (at least) two ways to construct such a solution. The simplest solution is to take $g = k+1$ and define $c_i = a_i \bmod (k+1)$. This works because 128 129 $a_i + k \cdot c_i \equiv c_i + k \cdot c_i \equiv (k+1) \cdot c_i \equiv 0 \pmod{k+1}$ 130 131 Hence every term is divisible by $k+1$. 132 133 Alternatively, you can also find the smallest integer $x$ such that $\gcd(x,k) = 1$, and set $g = x$. Note that $g \leq 29$, since $k \leq 10^9$ and the product of all prime numbers from $2$ to $29$ already exceeds $10^9$. 134 135 Then, for each $a_i$, we can add $k$ to it until it becomes divisible by $g$. In fact, the value of $c_i$ can be determined explicitly (though it is not required) as 136 137 $a_i + k \cdot c_i \equiv 0 \pmod{g} \quad \implies \quad c_i \equiv (-a_i \cdot k^{-1}) \pmod{g}$ 138 139 where $k^{-1}$ is the modular inverse of $k$ modulo $g$. 140 141 Thus, in either method, we can always construct a valid array so that the GCD of the resulting numbers is greater than $1$. 142 143 **Code for solution 1 (C++)** 144 145 ``` 146 #include <iostream> 147 #include <vector> 148 using namespace std; 149 150 int main() { 151 ios::sync_with_stdio(false); 152 cin.tie(0); 153 int t; 154 cin >> t; 155 while (t--) { 156 int n, k; 157 cin >> n >> k; 158 vector<long long> a(n); 159 for (auto &i : a) { 160 cin >> i; 161 i += (i % (k + 1)) * k; 162 } 163 for (auto i : a) 164 cout << i << ' '; 165 cout << '\n'; 166 } 167 } 168 ``` 169 170 **Code for solution 1 (Python)** 171 172 ``` 173 t = int(input()) 174 for _ in range(t): 175 n, k = map(int, input().split()) 176 a = list(map(int, input().split())) 177 for i in range(n): 178 a[i] += (a[i] % (k + 1)) * k 179 print(*a) 180 ``` 181 182 **Code for solution 2 (C++)** 183 184 ``` 185 #include <iostream> 186 #include <numeric> 187 #include <vector> 188 using namespace std; 189 190 int main() { 191 ios::sync_with_stdio(false); 192 cin.tie(0); 193 int t; 194 cin >> t; 195 while (t--) { 196 int n, k; 197 cin >> n >> k; 198 vector<long long> a(n); 199 for (auto &i : a) { 200 cin >> i; 201 } 202 203 for (int g = 2;; g++) { 204 if (gcd(g, k) != 1) 205 continue; 206 for (auto &i : a) { 207 while (i % g != 0) 208 i += k; 209 } 210 for (auto i : a) 211 cout << i << ' '; 212 cout << '\n'; 213 break; 214 } 215 } 216 } 217 ``` 218 219 **Code for solution 2 (Python)** 220 221 ``` 222 import math 223 t = int(input()) 224 for _ in range(t): 225 n, k = map(int, input().split()) 226 a = list(map(int, input().split())) 227 for g in range(2, k + 2): 228 if math.gcd(g, k) > 1: 229 continue 230 ok = True 231 b = list(a) 232 for i in range(n): 233 if b[i] % g == 0: 234 continue 235 for j in range(1, k + 1): 236 b[i] += k 237 if b[i] % g == 0: 238 break 239 if b[i] % g != 0: 240 ok = False 241 if ok: 242 print(*b) 243 break 244 ``` 245 246 **Rate the problem!** 247 248 **Quality** 249 250 * Excellent problem 251 * Good problem 252 * Average problem 253 * Bad problem 254 * Horrible problem 255 256 **Difficulty** 257 258 * Trivial problem 259 * Easy problem 260 * Average problem 261 * Hard problem 262 * Impossible problem 263 264 [2134C - Even Larger](/contest/2134/problem/C "Codeforces Round 1045 (Div. 2)") 265 266 **Hint 1** 267 268 Only subarrays with length equal to $2$ or $3$ are useful. 269 270 **Hint 2** 271 272 Propose a greedy algorithm to decide which element to perform an operation. 273 274 **Solution** 275 276 For convenience, if $n$ is even, we append $a_{n+1}=0$ to the end of the array. Note that $a_{n+1}$ cannot be modified. 277 278 The first key observation is the following: 279 280 **Observation.** If all subarrays $[a_l, a_{l+1}, \ldots, a_r]$ with the following properties satisfy the condition, then all subarrays satisfy the condition: 281 282 * $r = l + 2$, 283 * $l$ and $r$ are both odd. 284 285 **Proof.** Consider such subarrays where both $l$ and $r$ are odd: 286 287 $\begin{array}{rcl} \displaystyle \sum_{\substack{l \leq i \leq r \\ i \ \text{even}}} a_i &\geq& \displaystyle \sum_{\substack{l \leq i \leq r \\ i \ \text{even}}} \bigl(a_{i-1} + a_{i+1}\bigr) \\[1.2em] 288 289 &=& a_l \;+\; \displaystyle \left( \sum_{\substack{l+2 \leq i \leq r-2 \\ i \ \text{odd}}} 2a_i \right) \;+\; a_r \\[1.2em] 290 291 &\geq& a_l \;+\; \displaystyle \left( \sum_{\substack{l+2 \leq i \leq r-2 \\ i \ \text{odd}}} a_i \right) \;+\; a_r \\[1.2em] 292 293 &=& \displaystyle \sum_{\substack{l \leq i \leq r \\ i \ \text{odd}}} a_i \end{array}$ 294 295 The second inequality holds because all numbers are non-negative. 296 297 Thus, checking only these subarrays is sufficient: all other subarrays will automatically satisfy the condition because they involve fewer elements at odd positions. $\square$ 298 299 We will call these subarrays **important** in the following discussion. 300 301 Now we find the minimum number of operations. Instead of directly minimizing the number of operations, we can think in terms of constructing the final array $b$ after the operations. Our goal is to maximize the sum of the elements in $b$. 302 303 Initially, we set $b_i = 0$ for all $i$. Notice that it is never beneficial to reduce values at even indices. Therefore, we can safely set $b_i = a_i$ for every even $i$. 304 305 The task is then to determine the values of $b_i$ at odd indices. It turns out that the following greedy algorithm works: 306 307 * Repeatedly pick the smallest odd index $i$ such that $b_i \lt a_i$, and increasing $b_i$ by $1$ does not violate the condition for any important subarray. Then increment $b_i$ by $1$. 308 309 This greedy algorithm ensures that we maximize the sum of $b$ while preserving validity. It can be simulated in $\mathcal{O}(n)$ time. 310 311 **Code (C++)** 312 313 ``` 314 #include <algorithm> 315 #include <iostream> 316 #include <vector> 317 using namespace std; 318 319 int main() { 320 ios::sync_with_stdio(false); 321 cin.tie(0); 322 int t; 323 cin >> t; 324 while (t--) { 325 int n; 326 cin >> n; 327 vector<int> a(n); 328 for (auto &i : a) 329 cin >> i; 330 331 vector<int> b(n + 1); 332 long long ans = 0; 333 for (int i = 0; i < n; i += 2) { 334 int mn = a[i]; 335 if (i >= 2) 336 mn = min(mn, a[i - 1] - b[i - 2]); 337 if (i + 1 < n) 338 mn = min(mn, a[i + 1]); 339 b[i] = mn; 340 ans += (a[i] - b[i]); 341 } 342 343 cout << ans << '\n'; 344 } 345 } 346 ``` 347 348 **Code (Python)** 349 350 ``` 351 t = int(input()) 352 for _ in range(t): 353 n = int(input()) 354 a = list(map(int, input().split())) 355 b = [0] * (n + 1) 356 ans = 0 357 for i in range(0, n, 2): 358 mn = a[i] 359 if i >= 2: 360 mn = min(mn, a[i - 1] - b[i - 2]) 361 if i + 1 < n: 362 mn = min(mn, a[i + 1]) 363 b[i] = mn 364 ans += (a[i] - b[i]) 365 print(ans) 366 ``` 367 368 **Rate the problem!** 369 370 **Quality** 371 372 * Excellent problem 373 * Good problem 374 * Average problem 375 * Bad problem 376 * Horrible problem 377 378 **Difficulty** 379 380 * Trivial problem 381 * Easy problem 382 * Average problem 383 * Hard problem 384 * Impossible problem 385 386 [2134D - Sliding Tree](/contest/2134/problem/D "Codeforces Round 1045 (Div. 2)") 387 388 **Hint 1** 389 390 Consider the diameter of the tree. What do you discover? 391 392 **Hint 2** 393 394 Each sliding operation increases the diameter of the tree by at most $1$. 395 396 **Hint 3** 397 398 Now about the construction. How to perform an operation at each step that increases the diameter by exactly $1$? 399 400 **Solution** 401 402 We begin with the following observation: 403 404 **Observation.** Each sliding operation increases the diameter of the tree by at most $1$. 405 406 **Proof.** Consider an operation $(a,b,c)$, any pair of indices $(u,v)$, and the unique path $p$ between $u$ and $v$. If $p$ does not pass through $b$, or if $b$ is an endpoint of $p$, then the length of $p$ increases by at most $1$ before and after the operation. Otherwise, let $i_1$ and $i_2$ denote the two neighbors of $b$ on the path $p$. Then: 407 408 * If $i_1 = a$ and $i_2 = c$ (or vice versa), the length of $p$ does not change. 409 * If $i_1 = a$ and $i_2 \neq c$ (or vice versa), the length of $p$ increases by $1$. 410 * If $i_1 \neq a$ and $i_2 = c$ (or vice versa), the length of $p$ decreases by $1$. 411 * In all other cases, the length of $p$ does not change. 412 413 Thus, for any path in the tree, its length can increase by at most $1$. Consequently, the diameter of the tree increases by at most $1$ after a single operation. $\square$ 414 415 Let $l$ denote the diameter of the input tree. To transform it into a path graph (whose diameter is $n-1$), it is clear that at least $(n-1) - l$ operations are required. 416 417 The remaining question is whether it is always possible to perform an operation at each step that increases the diameter by exactly $1$. This turns out to be true. To see this, take any diameter of the tree and root the tree at one of its endpoints. In each operation, select an edge adjacent to the diameter. Suppose this edge is $(u,v)$, where $u$ lies on the diameter and $v$ does not. Then perform the operation with $a$ as the parent of $u$ (in the rooted tree), $b = u$, and $c = v$. One can verify that this increases the diameter by $1$. 418 419 From the above construction, we conclude not only that the minimum number of operations is $(n-1)-l$, but also that we can explicitly construct a sequence of operations that transforms the given tree into a path graph with this minimum number of moves. 420 421 Finally, finding the first sliding operation can be done in $\mathcal{O}(n)$ time. 422 423 **Code (C++)** 424 425 ``` 426 #include <algorithm> 427 #include <functional> 428 #include <iostream> 429 #include <vector> 430 using namespace std; 431 432 int main() { 433 ios::sync_with_stdio(false); 434 cin.tie(0); 435 int t; 436 cin >> t; 437 while (t--) { 438 int n; 439 cin >> n; 440 vector<vector<int>> G(n); 441 for (int i = 0; i < n - 1; i++) { 442 int u, v; 443 cin >> u >> v; 444 u--, v--; 445 G[u].push_back(v); 446 G[v].push_back(u); 447 } 448 449 vector<int> dist(n), p(n); 450 function<void(int, int)> dfs = [&](int now, int par) { 451 p[now] = par; 452 for (int i : G[now]) { 453 if (i != par) { 454 dist[i] = dist[now] + 1; 455 dfs(i, now); 456 } 457 } 458 }; 459 460 dist[0] = 0; 461 dfs(0, -1); 462 int x = max_element(dist.begin(), dist.end()) - dist.begin(); 463 dist[x] = 0; 464 dfs(x, -1); 465 int y = max_element(dist.begin(), dist.end()) - dist.begin(); 466 467 if (dist[y] == n - 1) { 468 cout << -1 << '\n'; 469 } else { 470 vector<int> on_diameter(n); 471 int now = y; 472 while (now != -1) { 473 on_diameter[now] = 1; 474 now = p[now]; 475 } 476 int a = -1, b = -1, c = -1; 477 for (int u = 0; u < n; u++) { 478 for (int v : G[u]) { 479 if (on_diameter[u] && !on_diameter[v]) { 480 a = p[u], b = u, c = v; 481 break; 482 } 483 } 484 if (a != -1) 485 break; 486 } 487 cout << a + 1 << ' ' << b + 1 << ' ' << c + 1 << '\n'; 488 } 489 } 490 } 491 ``` 492 493 **Rate the problem!** 494 495 **Quality** 496 497 * Excellent problem 498 * Good problem 499 * Average problem 500 * Bad problem 501 * Horrible problem 502 503 **Difficulty** 504 505 * Trivial problem 506 * Easy problem 507 * Average problem 508 * Hard problem 509 * Impossible problem 510 511 [2134E - Power Boxes](/contest/2134/problem/E "Codeforces Round 1045 (Div. 2)") 512 513 **Hint 1** 514 515 An intuitive starting point may be to perform a throw query on every coordinate $i$. For which $i$ we can decide the value of $a_i$ immediately? 516 517 **Hint 2** 518 519 For those incides whose $a_i$ is unknown, try to perform some swap queries on them to get the values of $a_i$ for them. 520 521 **Hint 3** 522 523 No two unknown indices are adjacent. 524 525 **Solution** 526 527 An intuitive starting point is to perform a throw query on every coordinate $i$ ($1 \le i \le n$). Let $d_i$ denote the total number of jumps the ball makes when starting from coordinate $i$. For convenience, define $d_{n+1} = d_{n+2} = 0$. 528 529 Notice that for $1 \le i \le n$, if $d_{i+1} \neq d_{i+2}$, then we can immediately determine $a_i$: if $d_i = d_{i+1} + 1$, then $a_i = 1$; otherwise $a_i = 2$. 530 531 The difficult part of the problem is when $d_{i+1} = d_{i+2}$. We call an index $i$ \textbf{unknown} if $d_{i+1} = d_{i+2}$. In such cases, we can deduce $d_i$ without issuing a query, thus saving it for later use. The following observation is crucial: 532 533 **Observation.** No two unknown indices are adjacent. 534 535 **Proof.** If $i$ is unknown, then $d_i = d_{i+1} + 1$, hence $d_i \neq d_{i+1}$. Therefore, $i-1$ cannot be unknown. $\square$ 536 537 To exploit this fact, we adopt the following strategy: After computing all $d_i$, for each unknown index $i$ (in increasing order), we swap the boxes at positions $i$ and $i+1$, and then perform a throw query at coordinate $i+1$. Since index $i+1$ is not unknown, this reveals $a_i$. The special case is $i = n$: here, we swap boxes $n-1$ and $n$, then perform a throw query on coordinate $n-1$ to obtain $a_n$. 538 539 To sum up: 540 541 * For $i$ from $n$ down to $1$: perform a throw query on coordinate $i$. If $d_{i+1} = d_{i+2}$, skip the query for $i$ and mark $i$ as unknown (but still compute $d_i$). Otherwise, determine both $a_i$ and $d_i$. 542 * For each $i$ from $1$ to $n-1$: if $i$ is unknown, swap box $i$ with box $i+1$ and perform a throw query at coordinate $i+1$. This reveals $a_i$. 543 * Finally, swap $n-1$ and $n$, and perform a throw query on coordinate $n-1$ to determine $a_n$. 544 545 For every unknown index we use $2$ queries, and for each known index we use $1$. Since no two unknown indices are adjacent, there are at most $\lceil \frac{n}{2} \rceil$ unknown indices. Hence, the total number of queries is at most $\left\lceil \frac{3n}{2} \right\rceil$. 546 547 **Code (C++)** 548 549 ``` 550 #include <iostream> 551 #include <vector> 552 using namespace std; 553 554 int main() { 555 ios::sync_with_stdio(false); 556 cin.tie(0); 557 int t; 558 cin >> t; 559 while (t--) { 560 int n; 561 cin >> n; 562 563 vector<int> a(n); 564 auto swap = [&](int x) { 565 cout << "swap " << x + 1 << endl; 566 }; 567 auto throw_ball = [&](int x) { 568 cout << "throw " << x + 1 << endl; 569 int ret; 570 cin >> ret; 571 return ret; 572 }; 573 auto answer = [&]() { 574 cout << "!"; 575 for (auto i : a) 576 cout << ' ' << i; 577 cout << endl; 578 }; 579 580 vector<int> jumps(n + 2); 581 for (int i = n - 1; i >= 0; i--) { 582 if (jumps[i + 1] == jumps[i + 2]) { 583 jumps[i] = jumps[i + 1] + 1; 584 } else { 585 jumps[i] = throw_ball(i); 586 if (jumps[i] == jumps[i + 1] + 1) 587 a[i] = 1; 588 else 589 a[i] = 2; 590 } 591 } 592 for (int i = 0; i + 1 < n; i++) { 593 if (a[i] == 0) { 594 swap(i); 595 int jumps_i = throw_ball(i + 1); 596 if (jumps_i == jumps[i + 2] + 1) 597 a[i] = 1; 598 else 599 a[i] = 2; 600 } 601 } 602 swap(n - 2); 603 int jumps_last = throw_ball(n - 2); 604 if (jumps_last == 2) 605 a[n - 1] = 1; 606 else 607 a[n - 1] = 2; 608 answer(); 609 } 610 } 611 ``` 612 613 **Rate the problem!** 614 615 **Quality** 616 617 * Excellent problem 618 * Good problem 619 * Average problem 620 * Bad problem 621 * Horrible problem 622 623 **Difficulty** 624 625 * Trivial problem 626 * Easy problem 627 * Average problem 628 * Hard problem 629 * Impossible problem 630 631 [2134F - Permutation Oddness](/contest/2134/problem/F "Codeforces Round 1045 (Div. 2)") 632 633 Thanks to [Misuki](/profile/Misuki "Grandmaster Misuki") for coming up with a better solution! My original solution has a much larger constant. 634 635 **Hint 1** 636 637 Consider two groups of numbers; one is ${0, 2}$ and another is ${1, 3}$. What do you discover? 638 639 **Hint 2** 640 641 Consider the segments formed by ${0, 2}$ (same for ${1, 3}$). For each $i$ and $j$, find the number of ways to arrange them into $i$ segments so that the total number of adjacent pairs inside all segments contribute oddness $j$. 642 643 **Hint 3** 644 645 Enumerate all binary strings consisting of $c_0$ zeros and $c_2$ twos. Then split these strings into several substrings. 646 647 **Hint 4** 648 649 Brute force over the number of runs of the binary string. Find the contribution to the count. 650 651 **Solution** 652 653 Consider any rearrangement $b$. We color all elements $b_i$ with value $0$ or $2$ as red, and those with value $1$ or $3$ as blue. Then the array can be viewed as alternating red and blue segments. 654 655 We observe the following: 656 657 * Adjacent pairs within a red segment contribute $0$ or $2$ to the oddness. The same holds for blue segments. 658 * Adjacent pairs between red and blue segments contribute exactly $1$ to the oddness. 659 * The number of red and blue segments differs by at most $1$. 660 661 Hence, if we can calculate the following: 662 663 * $r_{i,j}$: number of ways to arrange $c_0$ zeros and $c_2$ twos into $i$ segments, so that the total number of adjacent pairs inside all segments contribute oddness $j$. 664 * Similarly define $b_{i,j}$ for the blue digits ($1$ and $3$) 665 666 Then the final answer can be computed in $\mathcal{O}(n^3)$ by performing convolutions between the arrays pairs $(r_i, b_i), (r_{i+1}, b_i), (r_i, b_{i+1})$. 667 668 Now about computing $r_{i,j}$. This reduces to counting tuples of $i$ binary strings formed from $c_0$ zeros and $c_2$ twos, such that the total number of alternating adjacent pairs inside them equals $j$. 669 670 The idea is as follows. First, enumerate all binary strings consisting of $c_0$ zeros and $c_2$ twos. Then split these strings into several substrings. 671 672 Suppose a binary string has $l$ runs. Let $l_1 = \left\lceil \frac l 2 \right\rceil$ be the number of runs of $0$, and $l_2 = l - l_1$ the number of runs of $2$ (or vice versa). The number of such binary strings is 673 674 $\displaystyle \binom{c_0 - 1}{l_1 - 1} \cdot \binom{c_2 - 1}{l_2 - 1}$ 675 676 In such strings, there are $l-1$ adjacent pairs with different numbers, and $c_0 + c_2 - l$ adjacent pairs with the same numbers. 677 678 Now split the string into several substrings. Assume we choose $k_1$ positions among the $l-1$ differing adjacencies, and $k_2$ positions among the $c_0 + c_2 - l$ equal adjacencies. The number of ways to do this is 679 680 $\displaystyle \binom{l - 1}{k_1} \cdot \binom{c_0 + c_2 - l}{k_2}$ 681 682 This partition produces $k_1 + k_2 + 1$ substrings, each contributing oddness $2 \cdot (l - 1 - k_1)$. 683 Thus, the contribution to $r_{k_1 + k_2 + 1, \, 2 \cdot (l - 1 - k_1)}$ is 684 685 $\displaystyle \binom{c_0 - 1}{l_1 - 1} \cdot \binom{c_2 - 1}{l_2 - 1} \cdot \binom{l - 1}{k_1} \cdot \binom{c_0 + c_2 - l}{k_2}$ 686 687 Enumerating all possible tuples $(l, k_1, k_2)$ suffices to compute all $r_{i,j}$. This computation takes $\mathcal{O}(n^3)$ time. 688 689 By the same process, we can compute $b_{i,j}$ in $\mathcal{O}(n^3)$. Finally, convolving the results yields the number of distinct permutations for each oddness value. The entire algorithm runs in $\mathcal{O}(n^3)$ time. 690 691 **Code (C++)** 692 693 ``` 694 #include <iostream> 695 #include <vector> 696 using namespace std; 697 698 constexpr int MAXN = 800; 699 700 // Modified from https://github.com/ToxicPie/NaCl 701 template <typename T> struct M { 702 constexpr static T MOD = 1'000'000'007; 703 T v; 704 M(T x = 0) { 705 v = (-MOD <= x && x < MOD) ? x : x % MOD; 706 if (v < 0) 707 v += MOD; 708 } 709 explicit operator T() const { return v; } 710 bool operator==(const M &b) const { return v == b.v; } 711 bool operator!=(const M &b) const { return v != b.v; } 712 M operator-() { return M(-v); } 713 M operator+(M b) { return M(v + b.v); } 714 M operator-(M b) { return M(v - b.v); } 715 M operator*(M b) { return M((long long)v * b.v % MOD); } 716 M operator/(M b) { return *this * (b ^ (MOD - 2)); } 717 friend M operator^(M a, int b) { 718 M ans(1); 719 for (; b; b >>= 1, a *= a) 720 if (b & 1) 721 ans *= a; 722 return ans; 723 } 724 friend M &operator+=(M &a, M b) { return a = a + b; } 725 friend M &operator-=(M &a, M b) { return a = a - b; } 726 friend M &operator*=(M &a, M b) { return a = a * b; } 727 friend M &operator/=(M &a, M b) { return a = a / b; } 728 }; 729 using Mod = M<int>; 730 731 int main() { 732 ios::sync_with_stdio(false); 733 cin.tie(0); 734 vector<vector<Mod>> binom_(MAXN + 1, vector(MAXN + 1, Mod(0))); 735 for (int i = 0; i <= MAXN; i++) 736 for (int j = 0; j <= i; j++) { 737 if (j == 0 || j == i) 738 binom_[i][j] = 1; 739 else 740 binom_[i][j] = binom_[i - 1][j] + binom_[i - 1][j - 1]; 741 } 742 auto binom = [&](int x, int y) { 743 if (x >= y && y >= 0 && x >= 0) 744 return binom_[x][y]; 745 else 746 return Mod(0); 747 }; 748 749 int t; 750 cin >> t; 751 while (t--) { 752 vector<int> cnt(4); 753 for (auto &i : cnt) 754 cin >> i; 755 int n = cnt[0] + cnt[1] + cnt[2] + cnt[3]; 756 757 vector<vector<Mod>> r(n + 1, vector(n + 1, Mod(0))), 758 b(n + 1, vector(n + 1, Mod(0))); 759 760 auto fill_table = [&](int x, int y, vector<vector<Mod>> &table) { 761 for (int i = 2; i <= x + y; i++) { 762 vector<pair<int, int>> segments; 763 if (i & 1) 764 segments = {{i / 2, i - i / 2}, {i - i / 2, i / 2}}; 765 else 766 segments = {{i / 2, i / 2}, {i / 2, i / 2}}; 767 for (auto [l1, l2] : segments) { 768 if (x < l1 || y < l2) 769 continue; 770 auto mul = binom(x - 1, l1 - 1) * binom(y - 1, l2 - 1); 771 int different = i - 1, same = (x + y) - 1 - different; 772 for (int j = 0; j <= different; j++) 773 for (int k = 0; k <= same; k++) { 774 auto mul2 = binom(different, j) * binom(same, k); 775 int c = different - j; 776 table[j + k + 1][c] += mul * mul2; 777 } 778 } 779 } 780 }; 781 782 fill_table(cnt[0], cnt[2], r); 783 fill_table(cnt[1], cnt[3], b); 784 785 vector<Mod> ans(2 * (n - 1) + 1); 786 for (int i = 1; i <= (n + 1) / 2; i++) 787 for (int j = 0; j <= n; j++) 788 for (int k = 0; k <= n; k++) { 789 int oddness = (j + k) * 2 + (i * 2 - 1); 790 if (oddness >= 0 && oddness <= 2 * (n - 1)) 791 ans[oddness] += r[i][j] * b[i][k] * 2; 792 } 793 for (int i = 1; i <= (n + 1) / 2 && i + 1 <= n; i++) 794 for (int j = 0; j <= n; j++) 795 for (int k = 0; k <= n; k++) { 796 int oddness = (j + k) * 2 + i * 2; 797 if (oddness >= 0 && oddness <= 2 * (n - 1)) { 798 ans[oddness] += r[i][j] * b[i + 1][k]; 799 ans[oddness] += r[i + 1][j] * b[i][k]; 800 } 801 } 802 803 for (int i = 0; i <= 2 * (n - 1); i++) 804 cout << ans[i].v << " \n"[i == 2 * (n - 1)]; 805 } 806 } 807 ``` 808 809 **Rate the problem!** 810 811 **Quality** 812 813 * Excellent problem 814 * Good problem 815 * Average problem 816 * Bad problem 817 * Horrible problem 818 819 **Difficulty** 820 821 * Trivial problem 822 * Easy problem 823 * Average problem 824 * Hard problem 825 * Impossible problem