2264.md (29993B)
1 Source: https://codeforces.com/blog/entry/156680 2 3 # Codeforces Round 1121 — Editorial 4 5 Thanks for participating! 6 7 ### [2264A - Рамбу нужна рука](/contest/2264/problem/A "Codeforces Round 1121 (Div. 2)") 8 9 Problem by [qwexd](/profile/qwexd "Мастер qwexd"). 10 11 **Hint** 12 13 Look at the elements that are not in the right position. Which of them must be selected? Can selecting any other element help? 14 15 **Solution** 16 17 Every element that is not in the right position has to be selected; otherwise, it never moves. 18 19 Selecting an element that is already in the right position cannot help. For it to stay correct after the reversal, it has to be paired with itself, because its value occurs nowhere else in the permutation. Thus it can only be the middle selected element, and removing it changes nothing. 20 21 So, if the array is already sorted, choose any one element. Otherwise, select exactly the misplaced elements and reverse them. The answer is `YES` if this sorts the array, and `NO` otherwise. 22 23 If the misplaced positions are listed from left to right, the reversal pairs the first with the last, the second with the second-last, and so on. Check that every pair contains the two values those positions need. 24 25 This takes $O(n)$ time and $O(n)$ memory. 26 27 **Code (GNU C++17)** 28 29 ``` 30 #include <bits/stdc++.h> 31 32 using namespace std; 33 34 int main() { 35 ios::sync_with_stdio(false); 36 cin.tie(nullptr); 37 38 int t; 39 cin >> t; 40 while (t--) { 41 int n; 42 cin >> n; 43 44 vector<int> p(n); 45 for (int &x : p) cin >> x; 46 47 vector<int> bad; 48 for (int i = 0; i < n; ++i) { 49 if (p[i] != i + 1) { 50 bad.push_back(i); 51 } 52 } 53 54 bool ok = true; 55 int k = bad.size(); 56 for (int i = 0; i < k; ++i) { 57 if (p[bad[i]] != bad[k - 1 - i] + 1) { 58 ok = false; 59 break; 60 } 61 } 62 63 cout << (ok ? "YES\n" : "NO\n"); 64 } 65 } 66 ``` 67 68 ### [2264B - Ферма пилюль Найфа](/contest/2264/problem/B "Codeforces Round 1121 (Div. 2)") 69 70 Problem by [qwexd](/profile/qwexd "Мастер qwexd"). 71 72 **Hint 1** 73 74 Write out the score for a few terms and collect the coefficient of each chosen value. 75 76 **Hint 2** 77 78 Fix the last chosen position. Which $m-1$ earlier values are best, and how can we maintain them while moving this position to the right? 79 80 **Solution** 81 82 Expanding the score gives 83 84 $ b_1+2(b_2-b_1)+\cdots+m(b_m-b_{m-1}) =mb_m-\sum\limits_{i=1}^{m-1}b_i. $ 85 86 Only the last chosen value has a positive coefficient. Once we decide that $a_j$ is last, we should take the $m-1$ smallest values before it. Their positions are already in the right order, so they always form a valid subsequence together with $a_j$. 87 88 Scan $j$ from left to right. Before considering $a_j$, keep the $m-1$ smallest values among $a_1,\ldots,a_{j-1}$ in a max-heap, and let their sum be $s$. The best score ending at $j$ is 89 90 $ma_j-s.$ 91 92 Then insert $a_j$ for later positions and remove the maximum if the heap becomes too large. Take the best score over all $j$. For $m=1$, the heap is empty and this simply takes the maximum element. 93 94 The complexity is $O(n\log(m+1))$ time and $O(m)$ extra memory. 95 96 **Code (GNU C++17)** 97 98 ``` 99 #include <bits/stdc++.h> 100 101 using namespace std; 102 103 using ll = long long; 104 105 int main() { 106 ios::sync_with_stdio(false); 107 cin.tie(nullptr); 108 109 int t; 110 cin >> t; 111 while (t--) { 112 int n, m; 113 cin >> n >> m; 114 115 vector<ll> a(n); 116 for (ll &x : a) cin >> x; 117 118 priority_queue<ll> pq; 119 ll sum = 0, ans = LLONG_MIN; 120 121 for (int i = 0; i < n; ++i) { 122 if ((int)pq.size() == m - 1) { 123 ans = max(ans, m * a[i] - sum); 124 } 125 126 pq.push(a[i]); 127 sum += a[i]; 128 if ((int)pq.size() == m) { 129 sum -= pq.top(); 130 pq.pop(); 131 } 132 } 133 134 cout << ans << '\n'; 135 } 136 } 137 ``` 138 139 ### [2264C - Династия фигуристов Мадамант](/contest/2264/problem/C "Codeforces Round 1121 (Div. 2)") 140 141 Problem by [qwexd](/profile/qwexd "Мастер qwexd"). 142 143 **Hint 1** 144 145 After sorting, every parent lies to the right of their child. What does that imply about cycles and the root? 146 147 **Hint 2** 148 149 The total cost is a sum of edge costs. Fix one possible edge; how many choices remain for the other children? 150 151 **Solution** 152 153 Sort the ratings: 154 155 $ b_0 \lt b_1 \lt \cdots \lt b_{n-1}. $ 156 157 The maximum is forced to be the root. Give every other position $i$ any parent $j \gt i$. Following parent links always moves right, so there is no cycle and every path ends at the maximum. Thus any such choices form a valid tree. 158 159 We cannot enumerate the trees. Instead, consider one possible edge at a time and add its cost once for every tree containing it. 160 161 Fix the edge from child $i$ to parent $j \gt i$. Its cost is $b_j-b_i$. Every other child $k$ still has $n-k-1$ choices, so this edge appears in 162 163 $ W_i=\prod\limits_{\substack{0\le k \lt n-1\\k\ne i}}(n-k-1) $ 164 165 trees. The value $W_i$ does not depend on $j$, so all edges leaving $i$ contribute 166 167 $ W_i\sum\limits_{j=i+1}^{n-1}(b_j-b_i) =W_i\left(\sum\limits_{j=i+1}^{n-1}b_j\right) - W_i (n-i-1)b_i. $ 168 169 A suffix sum gives the sum of ratings to the right of each $i$. Prefix and suffix products of the numbers $n-k-1$ give every $W_i$ without division. 170 171 The complexity is $O(n\log n)$ time and $O(n)$ memory. 172 173 **Code (GNU C++17)** 174 175 ``` 176 #include <bits/stdc++.h> 177 178 using namespace std; 179 180 using ll = long long; 181 182 const int MOD = 998244353; 183 184 int main() { 185 ios::sync_with_stdio(false); 186 cin.tie(nullptr); 187 188 int t; 189 cin >> t; 190 while (t--) { 191 int n; 192 cin >> n; 193 vector<ll> b(n); 194 for (ll &x : b) cin >> x; 195 sort(b.begin(), b.end()); 196 197 vector<ll> sum(n + 1); 198 for (int i = n - 1; i >= 0; --i) { 199 sum[i] = sum[i + 1] + b[i]; 200 } 201 202 vector<ll> pref(n, 1), suff(n, 1); 203 for (int i = 0; i < n - 1; ++i) { 204 pref[i + 1] = pref[i] * (n - i - 1) % MOD; 205 } 206 for (int i = n - 2; i >= 0; --i) { 207 suff[i] = suff[i + 1] * (n - i - 1) % MOD; 208 } 209 210 ll ans = 0; 211 for (int i = 0; i < n - 1; ++i) { 212 ll diff = sum[i + 1] - (n - i - 1) * b[i]; 213 ll ways = pref[i] * suff[i + 1] % MOD; 214 ans = (ans + diff % MOD * ways) % MOD; 215 } 216 cout << ans << '\n'; 217 } 218 } 219 ``` 220 221 ### [2264D - Тёмная тема доктора Агоса](/contest/2264/problem/D "Codeforces Round 1121 (Div. 2)") 222 223 Problem by [qwexd](/profile/qwexd "Мастер qwexd"). 224 225 **Hint 1** 226 227 Since $2\equiv-1\pmod 3$, try an alternating prefix sum. 228 229 **Hint 2** 230 231 A divisible substring corresponds to two equal prefix remainders. How should the counts of the three remainders be distributed? 232 233 **Hint 3** 234 235 With three ones, the prefix remainder is constant on four blocks. Try their boundaries around $n/3$, $2n/3$, and the end of the string. 236 237 **Solution** 238 239 Modulo $3$, the powers of $2$ alternate between $1$ and $-1$. Define the alternating prefix sum 240 241 $ p_0=0,\qquad p_i\equiv\sum\limits_{j=1}^{i}(-1)^js_j\pmod 3. $ 242 243 If $v$ is the binary value of $s_l\ldots s_r$, then 244 245 $ v\equiv(-1)^r(p_r-p_{l-1})\pmod 3. $ 246 247 Therefore, this substring is divisible by $3$ exactly when $p_{l-1}=p_r$. 248 249 Suppose the remainders $0,1,2$ occur $c_0,c_1,c_2$ times among the $n+1$ prefix sums. Every pair of equal prefix remainders gives one divisible substring, so 250 251 $ f(s)=\binom{c_0}{2}+\binom{c_1}{2}+\binom{c_2}{2}. $ 252 253 For a fixed sum $c_0+c_1+c_2=n+1$, this is smallest when the three counts differ by at most one. 254 255 Now we only need to build a string with such balanced counts. A zero repeats the current prefix remainder. A one changes it by $-1$ at an odd position and by $+1$ at an even position. Thus, three ones divide the prefix sums into four constant blocks. To make the three remainders appear almost equally often, the block boundaries should be near the thirds of the string. 256 257 For $n\ge3$, simply try: 258 259 * the first one at $\lfloor n/3\rfloor$ or $\lfloor n/3\rfloor+1$; 260 * the second one at $\lfloor2n/3\rfloor$ or $\lfloor2n/3\rfloor+1$; 261 * either no third one, or a third one at $n$. 262 263 For each of these at most eight strings, count how many prefix sums have each remainder. Output the first one whose three counts differ by at most one. 264 265 The searched ranges contain the following construction. Let $q=\lfloor n/3\rfloor$ and consider a string of length $3q+2$. 266 267 * If $q$ is odd, put ones at $q$, $2q+1$, and $3q+2$. The four blocks have remainders $0,2,1,0$ and lengths $q,q+1,q+1,1$. 268 * If $q$ is even, put ones at $q+1$, $2q+1$, and $3q+2$. The blocks have remainders $0,2,1,2$ and lengths $q+1,q,q+1,1$. 269 270 In both cases, each remainder occurs $q+1$ times. The real length $n$ is obtained by cutting off at most two characters. The last two prefix remainders are different, so the remaining counts are still balanced. If position $3q+2$ was cut off, this is exactly the choice with no third one. Hence, the string is among the eight candidates above. 271 272 For $n=1$ and $n=2$, output `1` and `10`, respectively. For $n=2$, three distinct prefix remainders are impossible, while `10` has only one divisible substring, so it is optimal. 273 274 The complexity is $O(n)$ time and $O(n)$ memory per test case. 275 276 **Code (GNU C++17)** 277 278 ``` 279 #include <bits/stdc++.h> 280 281 using namespace std; 282 283 bool hasBalancedPrefixes(const string& s) { 284 array<int, 3> count{1, 0, 0}; 285 int remainder = 0; 286 287 for (int i = 0; i < (int)s.size(); ++i) { 288 if (s[i] == '1') { 289 remainder = (remainder + (i % 2 == 0 ? 2 : 1)) % 3; 290 } 291 ++count[remainder]; 292 } 293 294 return *max_element(count.begin(), count.end()) 295 - *min_element(count.begin(), count.end()) <= 1; 296 } 297 298 string constructString(int n) { 299 if (n == 1) { 300 return "1"; 301 } 302 if (n == 2) { 303 return "10"; 304 } 305 306 for (int first = n / 3; first <= n / 3 + 1; ++first) { 307 for (int second = 2 * n / 3; second <= 2 * n / 3 + 1; ++second) { 308 for (int putLastOne = 0; putLastOne <= 1; ++putLastOne) { 309 if (first >= second || (putLastOne && second >= n)) { 310 continue; 311 } 312 313 string s(n, '0'); 314 s[first - 1] = '1'; 315 s[second - 1] = '1'; 316 if (putLastOne) { 317 s[n - 1] = '1'; 318 } 319 320 if (hasBalancedPrefixes(s)) { 321 return s; 322 } 323 } 324 } 325 } 326 327 assert(false); 328 return {}; 329 } 330 331 int main() { 332 ios::sync_with_stdio(false); 333 cin.tie(nullptr); 334 335 int t; 336 cin >> t; 337 while (t--) { 338 int n; 339 cin >> n; 340 cout << constructString(n) << '\n'; 341 } 342 return 0; 343 } 344 ``` 345 346 ### [2264E1 - Простое наводнение (простая версия)](/contest/2264/problem/E1 "Codeforces Round 1121 (Div. 2)") 347 348 Problem by [qwexd](/profile/qwexd "Мастер qwexd"). 349 350 **Hint 1** 351 352 An operation never changes the order of two values. If the minimum and maximum become equal, what happens to every value between them? 353 354 **Hint 2** 355 356 Let $dp[x][y]$ be the answer for minimum $x$ and maximum $y$. For $x \lt y$, can we decrease $y$ while leaving $x$ unchanged? 357 358 **Hint 3** 359 360 After computing every $dp[x][y]$, count subsequences with minimum $x$ and maximum $y$. 361 362 **Solution** 363 364 First ignore the counting of subsequences. Let $dp[x][y]$ be the largest value to which the pair $[x,y]$ can be made equal. 365 366 Every operation preserves the order of the values. Therefore, if the minimum and maximum of a subsequence become equal, every value between them becomes equal as well. The contribution of a subsequence $b$ is simply 367 368 $ dp[\min(b)][\max(b)]. $ 369 370 We can compute this table directly. Clearly, $dp[x][x]=x$. Now suppose $x \lt y$ and try to decrease the larger endpoint. 371 372 If some prime divides $y$ but does not divide $x$, choosing it changes the pair to $[x,y-1]$. Also, any sequence that equalizes $x$ and $y$ must equalize the value $y-1$ between them. Thus, this case gives $dp[x][y-1]$. 373 374 Otherwise, every prime divisor of $y$ also divides $x$, so choosing any of them changes the pair to $[x-1,y-1]$. 375 376 Why can doing something else first not give a better result? Look at the first operation in any successful sequence that decreases $y$. Immediately after it, the upper endpoint is $y-1$, while the lower endpoint is already at most $x-1$: it either decreased earlier, or the same prime decreases it together with $y$. The remaining operations equalize these two values, so order preservation means that they also equalize the value $x-1$ between them. Therefore, this case gives $dp[x-1][y-1]$. 377 378 The transition is 379 380 $ dp[x][y]= \begin{cases} dp[x-1][y-1],&\text{if every prime divisor of }y\text{ divides }x,\\ dp[x][y-1],&\text{otherwise}. \end{cases} $ 381 382 Here the limit is only $M=3\,000$, so we can build the whole $M\times M$ table. Let `need[y]` be the product of the distinct prime divisors of $y$. Sieve all `need[y]`; the first case applies exactly when `x % need[y] == 0`. Process $y-x$ from small to large and $x$ from small to large, so both states used by the transition are ready. 383 384 Now count subsequences by their minimum and maximum. Let $c_v$ be the number of occurrences of $v$. 385 386 If both endpoints are $v$, any nonempty subset of its occurrences works, giving $2^{c_v}-1$ choices. 387 388 For $x \lt y$, choose at least one occurrence of both $x$ and $y$. Every occurrence with value strictly between them is optional, so the number of choices is 389 390 $ (2^{c_x}-1)(2^{c_y}-1) 2^{\sum\limits_{x \lt v \lt y}c_v}. $ 391 392 Use prefix sums of the frequencies for the exponent, multiply each count by $dp[x][y]$, and add everything to the answer. 393 394 The one-time DP takes $O(M^2)$ time and memory. Each test case takes $O(n^2)$ time and $O(n)$ additional memory. 395 396 **Code (GNU C++17)** 397 398 ``` 399 #include <bits/stdc++.h> 400 401 using namespace std; 402 403 const int MAXV = 3000; 404 const int MOD = 998244353; 405 406 int dp[MAXV + 1][MAXV + 1], need[MAXV + 1], p2[MAXV + 1]; 407 408 void precompute() { 409 fill(need, need + MAXV + 1, 1); 410 for (int p = 2; p <= MAXV; ++p) { 411 if (need[p] != 1) { 412 continue; 413 } 414 for (int value = p; value <= MAXV; value += p) { 415 need[value] *= p; 416 } 417 } 418 419 for (int x = 1; x <= MAXV; ++x) { 420 dp[x][x] = x; 421 } 422 for (int difference = 1; difference < MAXV; ++difference) { 423 for (int x = 1; x + difference <= MAXV; ++x) { 424 int y = x + difference; 425 if (x % need[y] == 0) { 426 dp[x][y] = dp[x - 1][y - 1]; 427 } else { 428 dp[x][y] = dp[x][y - 1]; 429 } 430 } 431 } 432 433 p2[0] = 1; 434 for (int i = 1; i <= MAXV; ++i) { 435 p2[i] = 2LL * p2[i - 1] % MOD; 436 } 437 } 438 439 int main() { 440 ios::sync_with_stdio(false); 441 cin.tie(nullptr); 442 443 precompute(); 444 445 int t; 446 cin >> t; 447 while (t--) { 448 int n; 449 cin >> n; 450 vector<int> freq(n + 1); 451 for (int i = 0; i < n; ++i) { 452 int value; 453 cin >> value; 454 ++freq[value]; 455 } 456 457 vector<int> prefix(n + 1); 458 for (int value = 1; value <= n; ++value) { 459 prefix[value] = prefix[value - 1] + freq[value]; 460 } 461 462 long long answer = 0; 463 for (int x = 1; x <= n; ++x) { 464 if (freq[x] == 0) { 465 continue; 466 } 467 int chooseX = p2[freq[x]] - 1; 468 answer = (answer + 1LL * x * chooseX) % MOD; 469 470 for (int y = x + 1; y <= n; ++y) { 471 if (freq[y] == 0) { 472 continue; 473 } 474 int chooseY = p2[freq[y]] - 1; 475 476 int middle = prefix[y - 1] - prefix[x]; 477 long long ways = 1LL * chooseX * chooseY % MOD; 478 ways = ways * p2[middle] % MOD; 479 answer = (answer + ways * dp[x][y]) % MOD; 480 } 481 } 482 cout << answer << '\n'; 483 } 484 } 485 ``` 486 487 ### [2264E2 - Простое наводнение (сложная версия)](/contest/2264/problem/E2 "Codeforces Round 1121 (Div. 2)") 488 489 Problem by [qwexd](/profile/qwexd "Мастер qwexd") and solved for bigger constraints by [jeroenodb](/profile/jeroenodb "Легендарный гроссмейстер jeroenodb"). 490 491 **Hint 1** 492 493 Let $dp[x][y]$ be the answer for minimum $x$ and maximum $y$. E1 builds and sums over every pair. Fix $x$ and scan larger values of $y$. When can $dp[x][y]$ differ from $dp[x][y-1]$? 494 495 **Hint 2** 496 497 Let $r(y)$ be the product of the distinct prime divisors of $y$. The row for $x$ can change only at positions where $r(y)\mid x$. Generate these positions by fixing $y$ and visiting the smaller multiples of $r(y)$. 498 499 **Hint 3** 500 501 For fixed $x$, separate the number of subsequences with endpoints $(x,y)$ into an $x$-only factor and a $y$-only factor. Prefix sums of the $y$-only factors can add a whole constant part of the row at once. 502 503 **Solution** 504 505 The easy solution builds the full DP table and then loops over every minimum and maximum. We need to compress both quadratic parts. 506 507 Let $r(y)$ be the product of the distinct prime divisors of $y$. The transition from E1 is 508 509 $ dp[x][y]= \begin{cases} dp[x-1][y-1],&r(y)\mid x,\\ dp[x][y-1],&r(y)\nmid x. \end{cases} $ 510 511 Fix $x$ and read the row from left to right. Unless $r(y)$ divides $x$, the value is copied from the previous position. Thus, the row can change only at positions satisfying $r(y)\mid x$; call them blockers. 512 513 For example, the blockers of row $2$ are $4,8,16,\ldots$. At $y=4$, the row changes from $2$ to $dp[1][3]=1$. Every later blocker also reads $1$ from row $1$, so the whole row is stored as only $(2,2)$ and $(4,1)$. 514 515 We can generate all blockers without checking every pair. For each $y$, visit 516 517 $ x=r(y),2r(y),3r(y),\ldots\qquad(x \lt y) $ 518 519 and add $y$ to the blocker list of each visited $x$. Processing $y$ in increasing order keeps every list sorted. 520 521 Now build the rows in increasing order of $x$. Store a row as breakpoints $(s,z)$: its value becomes $z$ starting at position $s$. Begin row $x$ with $(x,x)$. At a blocker $y$, advance a pointer in row $x-1$ while the next breakpoint starts at or before $y-1$. Its current value is $dp[x-1][y-1]$. Add a new breakpoint only when this value differs from the previous one. 522 523 For the fixed limit $M=300\,000$, generating the blocker lists visits $5\,970\,168$ pairs. Unfortunately, a bound on the number of generated pairs is not easy to calculate for general $n$, so the best way to solve the problem in-contest is to experimentally verify that the number of pairs is small enough for the given $n$. After equal neighboring parts are merged, all rows together contain $640\,704$ breakpoints, and no row contains more than eight. 524 525 We still need to avoid iterating over every pair of endpoints. Let $c_v$ be the frequency of $v$, and write 526 527 $ C_v=2^{c_v}-1,\qquad S(v)=\sum\limits_{u\le v}c_u. $ 528 529 For $x \lt y$, the number of subsequences with minimum $x$ and maximum $y$ is 530 531 $ C_xC_y2^{S(y-1)-S(x)} =\left(C_x2^{-S(x)}\right) \left(C_y2^{S(y-1)}\right). $ 532 533 Call the two factors $L_x$ and $R_y$. Build prefix sums of $R_y$. Intersect each compressed part with $x \lt y\le n$. If the remaining interval is $u\le y\le v$ and the row value there is $z$, its whole contribution is 534 535 $ L_xz\sum\limits_{y=u}^{v}R_y, $ 536 537 which is one prefix-sum query. Skip values with $c_x=0$. The case $x=y$ contributes $xC_x$ separately. 538 539 The radical sieve takes $O(M\log\log M)$ time. The remaining preprocessing is linear in the $5\,970\,168$ generated pairs and $640\,704$ stored breakpoints. Afterward, each present minimum scans at most eight parts, so the additional work is virtually linear in the total input size. The blocker lists and compressed rows have the sizes given above; together with the $O(M)$ arrays, they fit comfortably in memory. 540 541 **Code (GNU C++17)** 542 543 ``` 544 #include <bits/stdc++.h> 545 546 using namespace std; 547 548 const int MAXN = 300000; 549 const int MOD = 998244353; 550 551 struct Breakpoint { 552 int pos; 553 int value; 554 }; 555 556 array<int, MAXN + 1> freq, prefixCount, prefix, p2, ip2; 557 vector<vector<Breakpoint>> rows; 558 559 void buildRows() { 560 vector<int> rad(MAXN + 1, 1); 561 for (int p = 2; p <= MAXN; ++p) { 562 if (rad[p] != 1) { 563 continue; 564 } 565 for (int x = p; x <= MAXN; x += p) { 566 rad[x] *= p; 567 } 568 } 569 570 vector<vector<int>> blockers(MAXN + 1); 571 for (int y = 2; y <= MAXN; ++y) { 572 for (int x = rad[y]; x < y; x += rad[y]) { 573 blockers[x].push_back(y); 574 } 575 } 576 577 rows.resize(MAXN + 1); 578 rows[0].push_back({0, 0}); 579 for (int x = 1; x <= MAXN; ++x) { 580 auto &row = rows[x]; 581 auto &previous = rows[x - 1]; 582 row.push_back({x, x}); 583 584 int ptr = 0; 585 for (int y : blockers[x]) { 586 while (ptr + 1 < (int)previous.size() && 587 previous[ptr + 1].pos < y) { 588 ++ptr; 589 } 590 int value = previous[ptr].value; 591 if (value != row.back().value) { 592 row.push_back({y, value}); 593 } 594 } 595 } 596 } 597 598 void buildPowers() { 599 const int inv2 = (MOD + 1) / 2; 600 p2[0] = ip2[0] = 1; 601 for (int i = 1; i <= MAXN; ++i) { 602 p2[i] = 2LL * p2[i - 1] % MOD; 603 ip2[i] = 1LL * inv2 * ip2[i - 1] % MOD; 604 } 605 } 606 607 int rangeSum(int left, int right) { 608 if (left > right) { 609 return 0; 610 } 611 return (prefix[right] - prefix[left - 1] + MOD) % MOD; 612 } 613 614 int main() { 615 ios::sync_with_stdio(false); 616 cin.tie(nullptr); 617 618 buildRows(); 619 buildPowers(); 620 621 int t; 622 cin >> t; 623 while (t--) { 624 int n; 625 cin >> n; 626 vector<int> values; 627 for (int i = 0; i < n; ++i) { 628 int x; 629 cin >> x; 630 if (freq[x] == 0) { 631 values.push_back(x); 632 } 633 ++freq[x]; 634 } 635 636 int before = 0, ans = 0; 637 prefixCount[0] = prefix[0] = 0; 638 for (int x = 1; x <= n; ++x) { 639 int ways = p2[freq[x]] - 1; 640 int rightWeight = 1LL * ways * p2[before] % MOD; 641 prefix[x] = prefix[x - 1] + rightWeight; 642 if (prefix[x] >= MOD) { 643 prefix[x] -= MOD; 644 } 645 ans = (ans + 1LL * x * ways) % MOD; 646 before += freq[x]; 647 prefixCount[x] = before; 648 } 649 650 for (int x : values) { 651 int ways = p2[freq[x]] - 1; 652 int leftWeight = 1LL * ways * ip2[prefixCount[x]] % MOD; 653 654 int rowSum = 0; 655 auto &row = rows[x]; 656 for (int i = 0; i < (int)row.size(); ++i) { 657 int left = max(x + 1, row[i].pos); 658 if (left > n) { 659 break; 660 } 661 int right = n; 662 if (i + 1 < (int)row.size()) { 663 right = min(n, row[i + 1].pos - 1); 664 } 665 rowSum = (rowSum + 666 1LL * row[i].value * rangeSum(left, right)) % MOD; 667 } 668 ans = (ans + 1LL * leftWeight * rowSum) % MOD; 669 } 670 671 cout << ans << '\n'; 672 for (int x : values) { 673 freq[x] = 0; 674 } 675 } 676 } 677 ``` 678 679 ### [2264F - Калькулятор беспорядков](/contest/2264/problem/F "Codeforces Round 1121 (Div. 2)") 680 681 Problem by [jeroenodb](/profile/jeroenodb "Легендарный гроссмейстер jeroenodb"). Testing tool created by [turska](/profile/turska "Мастер turska") 682 683 **Hint 1** 684 685 Try to make an expression for $n!$ as a warm-up 686 687 **Hint 2** 688 689 Try to use round and division to make an expression which is $0$ or $1$ at specific $n$. 690 691 **Hint 3** 692 693 Look for a formula relating $n!$ and the number of derangements. 694 695 **Solution** 696 697 Note that $10\,000$ looks like a lot of characters for an expression, but for $n$ up to $50$, due to the particular restrictions of the Deranged Calculator language, this limit is quite tight. So for everything we come up with, we have to be sure we are not wasting too many characters. The model solution uses $5969$ characters, and there are even better methods that achieve (way) fewer characters. 698 699 Let's first try to solve an easier problem: what if, instead of the number of derangements of $n$ elements, we try to calculate the number of permutations, $n!$, instead? 700 701 We can immediately notice that if we want to use integer constants in our program, we have to make them using workarounds such as `n/n` or `(n+n+n)/n`. To save some length, we can precompute a dynamic programming table, which tells us a small construction for the constant $i$ for $1\leq i\leq50$. Transitions can be coded to use `+` and `*` operators, considering all ways to make $i=x+y$ or $i=x\cdot y$, with some appropriate use of parentheses and `/n`. It turns out that if the the other parts of the expression are well optimized, even writing constants naively in the form $(n+n+\dots+n)/n$ can work. In less optimized expressions, optimizing expressions for constants is maybe required 702 703 Next up, we have to face the issue that we cannot use recursion or loops to calculate the factorial. The one saving grace is that the `round` function can help us to make some kind of step functions so we can filter out specific $n$ for our needs. 704 705 It would be great if we could make the following program: 706 707 ``` 708 (1*[n>=2]+1)*(2*[n>=3]+1)*...*(49*[n>=50]+1) 709 ``` 710 711 In such a program, we basically compute $50!$, but we modulate which terms we want to multiply and which we replace with $1$. Here `[n>=2]` is an indicator expression that should output $1$ if the given inequality is true and $0$ otherwise. 712 713 So now our goal has shifted to building an indicator expression `[n>=x]` for a given constant $x$. Here lots of tricks can be used involving the `round` function. One particularly nice one is the following: `round(n/(n+x))`. For a given constant $x$ (for which we have a short expression precomputed), this function gives exactly $1$ once $n\geq x$, and $0$ for $2\leq n \lt x$. So this solves calculating factorials in the DC language in a reasonable number of characters (this depends on how optimized your `round`-based "if statement" is, and how well optimized the DP is). 714 715 But what about derangements? It turns out there are some nice formulas relating factorials and derangements. One particular fact is that 716 717 $ \operatorname{round}(n!/e)=D_n, $ 718 719 where $e\approx2.71828$ is Euler's number, and $D_n$ is the number of derangements for this $n$. This means we can basically reuse all our work for the factorial case, but now we have to find a way to get a sufficiently precise approximation of $e$ in our program. There are again many possibilities, but as we already know how to create all integer constants up to $50$ with a small number of characters, one way is to use the Taylor expansion of $e^x$, evaluated at $x=1$: 720 721 $ e^1=\sum\limits_{k=0}^{\infty}\frac{1}{k!}. $ 722 723 We can cut off the series at some point, and as we are dividing $50!$ by $e$, it makes sense that we need roughly the first $50$ terms of the expansion, as we need a relative error of $\sim \frac{1}{50!}$. Summing all the terms from $k=0$ to $k=50$ can be confirmed to work. Naively writing a sum of the inverse factorials will use $\sim50^2/2$ constants, and this will probably not fit. Instead, we can rewrite the sum as 724 725 $ 2+\frac{1}{2}\left(1+\frac{1}{3}\left(1+\frac{1}{4}(\dots)\right)\right), $ 726 727 making use of the common terms in the factorials. This only uses $\sim50$ constants, and some $1$'s, which are very cheap. 728 729 Taking this all together, we can write our final solution as `round(n!/e)`, with our expressions for $n!$ and $e$ substituted. 730 731 The model solution tries to do some more tricks to optimize the precomputation DP for the constants, but they are not needed: 732 733 * Use a bigger DP table $DP_{i,j}$, for $0\leq j \lt 4$, which calculates a small-length expression for getting an expression with value $i\cdot n^j$, and also consider dividing using `/n` as transitions. 734 * Think about when exactly you can skip parentheses. 735 * Try to also use the `-` operator in your DP. Due to both `-` and `/` transitions, the DP is no longer acyclic, but as the table is very small, we can just keep iterating through all possible transitions multiple times, and eventually the DP table stays unchanged. 736 737 As a bonus, what is the lowest you can push the number of characters? 738 739 **Code (PyPy 3)** 740 741 ``` 742 N = 50 743 L = 4 744 dp = [[None]*L for i in range(N+1)] 745 def upd(l,n,s): 746 if not dp[n][l] or len(s)<len(dp[n][l]): dp[n][l]=s 747 for i in range(1,L): 748 upd(i,1,'n' + (i-1)*'*n') 749 750 def parens(s): 751 if len(s)>1: return '(' + s + ')' 752 return s 753 754 for iter in range(1,N): 755 for l1 in range(0,L): 756 for l2 in range(0,L): 757 for i in range(1,N+1): 758 for j in range(1,N+1): 759 if dp[i][l1] and dp[j][l2]: 760 a = dp[i][l1] 761 b = dp[j][l2] 762 if i<j and l1==l2: upd(l1,j-i,b + '-' + parens(a)) 763 if i+j<=N and l1==l2: upd(l1,i+j,f"{a}+{b}") 764 if i*j<=N and l1+l2<L: upd(l1+l2,i*j,f"{parens(a)}*{parens(b)}") 765 if i%j==0 and l1-l2>=0: upd(l1-l2, i//j, f"{parens(a)}/{parens(b)}") 766 767 e = "n/n" 768 for i in range(N,0,-1): e = f"n/n+n/({dp[i][1]})*({e})" 769 770 def geqn(i): return f"round(n/({dp[i][0]}+n))" 771 772 def factorial(): 773 res = "n/n" 774 for j in range(2,N+1): 775 res += f"*({geqn(j)}*({dp[j-1][0]})+n/n)" 776 return res 777 fact = factorial() 778 ans = f"round({fact}/({e}))" 779 print(ans) 780 ``` 781 782 **Code (PyPy 3) simplified and golfed** 783 784 ``` 785 def n(x): 786 if x==1: return "n/n" 787 else: return '(' + "+".join("n"*x) + ')/n' 788 N, e, fact = 50, n(1),n(1) 789 def geqn(i): return f"round(n/({n(i)}+n))" 790 for j in range(2,N+1): fact += f"*({geqn(j)}*({n(j-1)})+n/n)" 791 for i in range(N,0,-1): e = f"n/n+n/({'+'.join('n'*i)})*({e})" 792 print(f"round({fact}/({e}))") 793 ```