codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```