codeforces-scrape

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

2176.md (26093B)


      1 Source: https://codeforces.com/blog/entry/149154
      2 
      3 Thank you all for participation! We hope, you enjoyed the problems.
      4 
      5 ### [2176A - Operations with Inversions](/contest/2176/problem/A "Codeforces Round 1070 (Div. 2)")
      6 
      7 **Hints**
      8 
      9 **Hint 1**
     10 
     11 Which element of the array cannot be removed using the described operations?
     12 
     13 **Hint 2**
     14 
     15 Under what condition the element $a_j$ **cannot** be removed?
     16 
     17 **Solution**
     18 
     19 Note that the element $a_1$ cannot be removed using the described operations.
     20 
     21 In general, the $j$-th element **cannot** be removed if $a_j$ is not less than all elements $a_1 \ldots a_{j - 1}$.
     22 
     23 Otherwise, among the elements $a_1 \ldots a_{j - 1}$, there will always be an element $a_i \gt a_j$, which means that $a_j$ can be removed.
     24 
     25 The constraints are small enough, so for each element, this statement can be checked in $O(n)$ for one check — resulting in a total of $O(n^2)$ for the test.
     26 
     27 The idea for solving it in $O(n)$ is as follows:
     28 
     29 * We will process the elements starting from $a_2$ to $a_n$.
     30 * Let $M$ denote the largest among the already processed elements, initially $M = a_1$.
     31 * If $M \gt a_j$, then $a_j$ is removed; otherwise, we set $M$ equal to $a_j$.
     32 
     33 **Implementation**
     34 
     35 ```
     36 #include <iostream>
     37 #include <vector>
     38 #include <algorithm>
     39 #include <map>
     40 #include <ctime>
     41 #include <queue>
     42 #include <iomanip>
     43 #include "assert.h"
     44 #include <math.h>
     45 #include <set>
     46 #include <deque>
     47  
     48 using namespace std;
     49  
     50  
     51 #define vi vector<int>
     52 #define vii vector<pair<int, int>>
     53 #define pii pair<int, int>
     54 #define ll long long
     55 #define pll pair<ll, ll>
     56  
     57 const ll INF = 2e18;
     58  
     59 void solve() {
     60     int n;
     61     cin >> n;
     62     vi a(n);
     63     for (int i = 0; i < n; i++) cin >> a[i];
     64  
     65     int cmx = 0;
     66  
     67     int mx = 0;
     68  
     69     for (int i = 0; i < n; i++) {
     70         mx = max(mx, a[i]);
     71         if (a[i] == mx) cmx++;
     72     }
     73  
     74     int res = n - cmx;
     75     cout << res << "\n";
     76 }
     77  
     78  
     79 int main() {
     80     srand(time(0));
     81     ios::sync_with_stdio(0);
     82     cout.tie(0), cin.tie(0);
     83     int T = 1;
     84     cin >> T;
     85     while (T--) {
     86         solve();
     87     }
     88 }
     89 ```
     90 
     91 ### [2176B - Optimal Shifts](/contest/2176/problem/B "Codeforces Round 1070 (Div. 2)")
     92 
     93 **Hints**
     94 
     95 **Hint 1**
     96 
     97 What is the answer for the strings "101", "1010", "10101", "101010", and so on?
     98 
     99 **Hint 2**
    100 
    101 Is the optimal set of operations different for the strings "100", "010", and "001"?
    102 
    103 **Hint 3**
    104 
    105 What is the answer for the strings "100", "0100", "00100", "001000", and so on?
    106 
    107 **Hint 4**
    108 
    109 Is the answer different for the strings "0100100", "100011", "001110110"?
    110 
    111 **Solution**
    112 
    113 Consider all groups of consecutive zeros in the cyclic string $S$.
    114 
    115 Let the number of zeros in these groups be $z_1, z_2, \ldots, z_k$, where $k$ is the number of groups.
    116 
    117 In this case, the answer is $MZ = \max(z_j)$.
    118 
    119 We will show that the answer $MZ$ is always achievable as a result:
    120 
    121 * We can perform the operation with $d = 1$ exactly $MZ$ times.
    122 * After each operation, all $z_j \gt 0$ will decrease by $1$, as the leftmost zero **in each block** will turn into a one.
    123 * Since $MZ = \max(z_j)$, after **exactly** $MZ$ operations, all $z_j$ will be equal to zero.
    124 
    125 We will show that it is impossible to obtain an answer better than $MZ$:
    126 
    127 * Suppose there exists an answer with the sum of cyclic shifts $S = d_1 + d_2 + \dots + d_m$, where $S \lt MZ$.
    128 * Consider the largest block of zeros (its size is $MZ$) and the one to the left of this block.
    129 * When applying the first operation with shift $d_1$, we could not have created ones in positions to the right of $d_1$ in this block.
    130 * When applying the subsequent cyclic shifts, this one can also only move to the right by the value of the shifts.
    131 * In total, this one can only move $S$ positions to the right from its original position, which is strictly less than $MZ$ — thus the last zero of the block will remain a zero, contradicting the initial assumption.
    132 
    133 **Implementation**
    134 
    135 ```
    136 #include <iostream>
    137 #include <vector>
    138  
    139 using namespace std;
    140  
    141 #define vi vector<int>
    142 #define ll long long
    143  
    144 void solve() {
    145 	int n;
    146 	cin >> n;
    147 	string s;
    148 	cin >> s;
    149 	s += s;
    150 	n *= 2;
    151 	int cur = 0;
    152  
    153 	int res = 0;
    154  
    155 	for (int i = 0; i < n; i++) {
    156 		if (s[i] == '1') cur = 0;
    157 		else cur++;
    158 		res = max(res, cur);
    159 	}
    160 	cout << res << "\n";
    161 }
    162  
    163 int main() {
    164 	int T;
    165 	cin >> T;
    166 	while (T--) {
    167 		solve();
    168 	}
    169  
    170 }
    171 ```
    172 
    173 ### [2176C - Odd Process](/contest/2176/problem/C "Codeforces Round 1070 (Div. 2)")
    174 
    175 **Hints**
    176 
    177 **Hint 1**
    178 
    179 You have $n$ coins, and all of them are even. What will the answers be for all $k$?
    180 
    181 **Hint 2**
    182 
    183 You have two coins: one even and one odd. What will the answers be for $k = 1$ and $k = 2$?
    184 
    185 **Hint 3**
    186 
    187 You have $n$ coins, and exactly one of them is odd. What will the answers be for all $k$?
    188 
    189 **Hint 4**
    190 
    191 You have $n$ coins, and all of them are odd. What will the answers be for all $k$?
    192 
    193 **Hint 5**
    194 
    195 You have $n$ coins, and exactly three of them are odd. What will the answers be for $k = (n - 2)$, $(n - 1)$, and $n$, respectively?
    196 
    197 **Hint 6**
    198 
    199 You have $n$ coins, and exactly four of them are odd. What will the answers be for $k$ from $(n - 3)$ to $n$?
    200 
    201 **Solution**
    202 
    203 If all the coins you have are even, then regardless of your actions, the bag will be empty every time.
    204 
    205 Let's say we have one odd coin $oc$ and several even coins $ec_1, ec_2, \dots, ec_m$.
    206 
    207 We will sort the even coins in descending order: $ec_1 \ge ec_2 \ge \dots ec_m$.
    208 
    209 In this case, for $k = 1 \dots (m + 1)$, we can construct the following answers:
    210 
    211 * $oc$
    212 * $oc + ec_1$
    213 * $oc + ec_1 + ec_2$
    214 * $\dots$
    215 * $oc + ec_1 + ec_2 + \dots + ec_m$.
    216 
    217 But what to do if there are several odd coins?
    218 
    219 Let $oc$ be the largest of the odd coins.
    220 
    221 We will perform the above actions for all $k$ from $1$ to $(m + 1)$.
    222 
    223 For $k = (m + 2)$, we will use the following construction:
    224 
    225 * First, we will put any two odd coins that are not the coin $oc$ into the bag.
    226 * Next, we will put the coin $oc$ and all even coins except the smallest one $ec_m$.
    227 
    228 For $k = (m + 3)$, we will add the smallest even coin $ec_m$ to the already constructed answer.
    229 
    230 For $k = (m + 4)$, we will add two more "unnecessary" odd coins at the beginning and again remove $ec_m$.
    231 
    232 For $k = (m + 5)$, we will add $ec_m$ again, and so on.
    233 
    234 Note for $k = n$: if you have an even number of odd coins in total, then regardless of the order of addition, the bag will be emptied in the end.
    235 
    236 **Implementation**
    237 
    238 ```
    239 #include <iostream>
    240 #include <vector>
    241 #include <algorithm>
    242 #include <map>
    243 #include <ctime>
    244 #include <queue>
    245 #include <iomanip>
    246 #include "assert.h"
    247 #include <math.h>
    248 #include <set>
    249 #include <deque>
    250  
    251 using namespace std;
    252  
    253  
    254 #define vi vector<int>
    255 #define vii vector<pair<int, int>>
    256 #define pii pair<int, int>
    257 #define ll long long
    258 #define pll pair<ll, ll>
    259  
    260 const ll INF = 2e18;
    261  
    262 void solve() {
    263     int n;
    264     cin >> n;
    265     vi a(n);
    266     for (int i = 0; i < n; i++) cin >> a[i];
    267  
    268  
    269     vi odd, even;
    270  
    271     for (int i = 0; i < n; i++) {
    272         if (a[i] & 1) odd.push_back(a[i]);
    273         else even.push_back(a[i]);
    274     }
    275  
    276     sort(odd.begin(), odd.end());
    277     sort(even.begin(), even.end());
    278     reverse(even.begin(), even.end());
    279  
    280     vector<ll> prefeven((int)even.size() + 1);
    281  
    282     if (even.size() > 0) {
    283         prefeven[0] = 0;
    284         for (int i = 0; i < even.size(); i++) prefeven[i + 1] = prefeven[i] + even[i];
    285     }
    286  
    287     ll ans = -INF;
    288  
    289     int cntodd = (int)odd.size();
    290     int cnteven = 0;
    291     for (int i = 0; i < n; i++) {
    292         if (a[i] % 2 == 0) cnteven++;
    293     }
    294  
    295     int odd1 = 1, even1 = 0;
    296  
    297     if (odd.size() == 0) odd1 = 0, even1 = 1;
    298  
    299     for (int k = 1; k <= n; k++) {
    300         if (k > 1) {
    301             if (even1 < even.size()) even1++;
    302             else {
    303                 if (odd1 + 2 <= odd.size() && even1 > 0) {
    304                     odd1 += 2;
    305                     even1--;
    306                 }
    307                 else {
    308                     odd1++;
    309                 }
    310             }
    311         }
    312         if (odd1 & 1) {
    313             cout << odd.back() + prefeven[even1] << " ";
    314         }
    315         else {
    316             cout << 0 << " ";
    317         }
    318     }
    319     cout << '\n';
    320 }
    321  
    322  
    323 int main() {
    324     srand(time(0));
    325     ios::sync_with_stdio(0);
    326     cout.tie(0), cin.tie(0);
    327     int T = 1;
    328     cin >> T;
    329     while (T--) {
    330         solve();
    331     }
    332 }
    333 ```
    334 
    335 ### [2176D - Fibonacci Paths](/contest/2176/problem/D "Codeforces Round 1070 (Div. 2)")
    336 
    337 In this Editorial, we will refer to simple paths in the graph, where the sequence of numbers forms a generalized Fibonacci sequence, as Fibonacci paths.
    338 
    339 **Hints**
    340 
    341 **Hint 1**
    342 
    343 Think about what the simplest Fibonacci paths look like.
    344 
    345 **Hint 2**
    346 
    347 The simplest Fibonacci paths are paths of two vertices ($u,v$) connected by an edge. Moreover, any edge in the graph is a Fibonacci path, as the corresponding sequence of numbers (the ends of the edge) consists of only two numbers.
    348 
    349 Now think about what longer Fibonacci paths look like.
    350 
    351 **Hint 3**
    352 
    353 Longer Fibonacci paths consist of a sequence of edges such that the numbers at the ends of the first edge are arbitrary. But the number at the end of any other edge is the sum of the numbers at the ends of the previous edge and the beginning of the current edge.
    354 
    355 ![](/predownloaded/24/fe/24fe9dc94b3e8d227694a584f1140e2d54555947.png)
    356 
    357 Think about dynamic programming on edges.
    358 
    359 **Solution**
    360 
    361 Let's count $dp[uv]$ — the number of Fibonacci paths that start with the edge ($u,v$). The transitions in such dynamics will look like $dp[uv]=\sum dp[vw]$, for such edges ($v,w$) for which $cost[w]=cost[u]+cost[v]$.
    362 
    363 How to compute such dynamics if it depends on the order of processing edges? We could introduce a parameter $k$ — fix the length of the Fibonacci path, and then the dynamics would look like $dp[uv][k]=\sum dp[vw][k-1]$. But there is a simpler way.
    364 
    365 Notice that in a Fibonacci path, for each subsequent edge, the sum of the numbers at its ends is strictly greater than the sum of the numbers at the ends of the previous edge. This means that edges with a greater sum of numbers should be processed strictly before edges with a smaller sum of numbers, and the order of processing edges with the same sum can be arbitrary, as they cannot be part of the same Fibonacci path.
    366 
    367 Then we will sort the edges, and it will remain only to quickly recalculate the sum $dp[uv]=\sum dp[vw]$ from the dynamics. Naively searching for edges ($v, w$) where $cost[w]=cost[u]+cost[v]$ will not work, as the asymptotic complexity of such a solution will easily be $O(E^2)$ or worse.
    368 
    369 Therefore, we will compress edges with the same value at the end and coming from the same vertex together. For each vertex $u$, we will maintain a dictionary $dp[u][cost]$ — the number of Fibonacci paths from vertex $u$ that go to some vertex $v$ with value $cost$.
    370 
    371 The recalculation of this dynamics is such that $dp[u][cost[v]] = dp[u][cost[v]] + (1 + dp[v][cost[u] + cost[v]])$ — the value of the dynamics $dp[u][cost[v]]$ is incremented by the number of paths from vertex $v$ with cost $cost[u]+cost[v]$, plus one for the path from a single edge ($u,v$).
    372 
    373 The asymptotic complexity of the solution is $O(E\cdot\operatorname{log}(E))$.
    374 
    375 **Implementation**
    376 
    377 ```
    378 #include <bits/stdc++.h>
    379  
    380 using namespace std;
    381  
    382 #define vi vector<int>
    383 #define vii vector<pair<int, int>>
    384 #define pii pair<int, int>
    385 #define ll long long
    386 #define pll pair<ll, ll>
    387  
    388 const ll INF = 2e18;
    389 const int MOD = 998244353;
    390  
    391 struct Edge {
    392     int u, v;
    393     ll s;
    394     Edge(){}
    395     Edge(int u, int v, ll s) : u(u), v(v), s(s){}
    396     bool operator < (const Edge &other) const {
    397         return s < other.s;
    398     }
    399 };
    400  
    401 void add(int &a, int b) {
    402     a += b;
    403     if (a >= MOD) a -= MOD;
    404 }
    405  
    406  
    407 void solve() {
    408     int n, m;
    409     cin >> n >> m;
    410     vector <ll> a(n);
    411     for (int i = 0; i < n; i++) cin >> a[i];
    412     vector <vi> g(n);
    413     vector <Edge> edges;
    414  
    415     for (int i = 0; i < m; i++) {
    416         int u, v;
    417         cin >> u >> v;
    418         u--;
    419         v--;
    420         g[u].push_back(v);
    421         edges.push_back(Edge(u, v, a[u] + a[v]));
    422     }
    423  
    424     sort(edges.begin(), edges.end());
    425     reverse(edges.begin(), edges.end());
    426  
    427     vector<map <ll, int>> sumdp(n);
    428  
    429     int ans = 0;
    430  
    431     for (auto e : edges) {
    432         int u = e.u;
    433         int v = e.v;
    434         ll s = e.s;
    435         //cout << u << " " << v << " " << s << endl;
    436         int curdp = sumdp[v][s];
    437         add(curdp, 1);
    438         add(sumdp[u][a[v]], curdp);
    439         add(ans, curdp);
    440     }
    441  
    442     cout << ans << "\n";
    443 }
    444  
    445  
    446 int main() {
    447     srand(time(0));
    448     ios::sync_with_stdio(0);
    449     cout.tie(0), cin.tie(0);
    450     int T = 1;
    451     cin >> T;
    452     while (T--) {
    453         solve();
    454     }
    455 }
    456 ```
    457 
    458 ### [2176E - Remove at the lowest cost](/contest/2176/problem/E "Codeforces Round 1070 (Div. 2)")
    459 
    460 **Hints**
    461 
    462 **Hint 1**
    463 
    464 Come up with a solution to the problem without queries.
    465 
    466 **Hint 2**
    467 
    468 Let's look at the maximum elements. What can you say about the segments between them?
    469 
    470 **Solution without queries**
    471 
    472 Let's first provide a theoretical estimate for the answer, followed by an algorithm that achieves this estimate.
    473 
    474 Let's introduce $\operatorname{f}(l, r, x)$, which means the following: suppose we only consider the elements $a_l, a_{l + 1}, \ldots, a_{r - 1}$, and we can eliminate each of them using an element with a removal cost of $x$. What is the minimum removal cost for the entire range? Let's assume that we pass the best possible value to $x$.
    475 
    476 Then let $p_1, p_2, \ldots, p_m$ be the positions of all the maxima on the interval. Note the following facts:
    477 
    478 * For any $i, j$ for which there exists $k$ such that $l \leq i \lt p_k \lt j \lt r$, there is no sequence of operations in which one of these elements removes the other
    479 * At least one of the elements $p$ must be removed by an element outside this interval
    480 * The elements $p_1, p_2, \ldots, p_m$ can be removed either for the cost of $x$ or for the cost of another maximum element
    481 
    482 Define $x' = min(x, c_{p_1}, c_{p_2}, \ldots, c_{_m})$. Then from these three remarks, we can conclude that, with the optimal choice of $x$ earlier, $\operatorname{f}(l, r, x) = x' \cdot m + \operatorname{f}(l, p_1, x') + \operatorname{f}(p_1 + 1, p_2, x') + \ldots + \operatorname{f}(p_m + 1, r, x')$.
    483 
    484 This is true because, according to point 2, there must be at least one element that is removed by an element outside the interval. According to point 3, we can remove the remaining $m - 1$ maxima only using $x$ and other elements $p_i$, and the remaining maximum is $x'$(according to the condition). And according to point 1, all the segments are independent of each other, if we do not consider the maxima.
    485 
    486 In this case, the answer to the problem is $\operatorname{f}(0, n, inf) - inf$.
    487 
    488 Now, we will show that this sequence of deletions is valid.
    489 
    490 We will also recursively remove segments, but with the condition that this minimum element outside the segment will lie strictly to the left or to the right of the segment $l, r$. Then, when we have selected $x'$, we can perform the following process:
    491 
    492 We have a set of segments $(l_1, r_1), \ldots, (l_{m + 1}, r_{m + 1})$. We will find a segment that is a neighbor of the element $x'$, and we will recursively remove it. After that, this optimal neighbor will have one of the maximum elements as a neighbor (or we will have removed the entire segment). We remove it for $x'$.
    493 
    494 This process will end when there is exactly one element that can be removed for $x'$. It is easy to see that we have reached our estimate, which means that the recursive algorithm above actually returns the answer to the problem.
    495 
    496 **Hint 3**
    497 
    498 What is the structure of the recursive calls to the function $\operatorname{f}$? Can we remember it and then use it to efficiently process requests? For which elements will the cost of deleting them change when we set it to zero?
    499 
    500 **Solution with queries**
    501 
    502 Note that the structure of the function calls $\operatorname{f}$ is a tree. Let's save it and remember the price we paid for removing each element, let's call it $r_i$.
    503 
    504 Then, when the request to zero $c_{p_i}$ comes, we take the node for which $p_i$ is one of the maximums and perform a depth-first search on the subtree of this node, avoiding the nodes that have already been zeroed. Thus, we change the corresponding values of $r_i$ to $0$ and recalculate the global answer.
    505 
    506 The complexity of the solution is $O(n \log{n})$, as we need to calculate the maximum on a segment to implement the function $\operatorname{f}$, which may require a segment tree or a sparse table.
    507 
    508 There may be other approaches to the problem.
    509 
    510 **Implementation**
    511 
    512 ```
    513 #include <iostream>
    514 #include <vector>
    515 #include <set>
    516 #include <map>
    517 #include <algorithm>
    518 #include <deque>
    519 #include <queue>
    520 #include <iomanip>
    521  
    522 using namespace std;
    523  
    524 #define ll long long
    525 #define vi vector<int>
    526 #define pii pair<int, int>
    527 #define vii vector<pii>
    528  
    529  
    530 const int N = 505010;
    531 const int MOD = 1e9 + 7;
    532  
    533 vi g[3 * N];
    534 int cost1[3 * N], cost2[3 * N];
    535 int tree[4 * N], pos[4 * N], a[N], c[N];
    536 int nxtL[N], nxtR[N];
    537 int num[N];
    538 int n, q;
    539  
    540 void build(int v, int tl, int tr) {
    541     if (tl == tr) {
    542         tree[v] = a[tl];
    543         pos[v] = tl;
    544         return;
    545     }
    546     int tm = (tl + tr) / 2;
    547     build(v * 2, tl, tm);
    548     build(v * 2 + 1, tm + 1, tr);
    549     if (tree[v * 2] > tree[v * 2 + 1]) {
    550         tree[v] = tree[v * 2];
    551         pos[v] = pos[v * 2];
    552     }
    553     else {
    554         tree[v] = tree[v * 2 + 1];
    555         pos[v] = pos[v * 2 + 1];
    556     }
    557 }
    558  
    559 pii getmax(int v, int tl, int tr, int l, int r) {
    560     if (l > r) return { -1, -1 };
    561     if (l == tl && r == tr) {
    562         return { tree[v], pos[v] };
    563     }
    564     int tm = (tl + tr) / 2; 
    565     pii tmp = max(getmax(v * 2, tl, tm, l, min(r, tm)), getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
    566     return tmp;
    567 }
    568  
    569  
    570 int state = -1;
    571 ll ans;
    572  
    573 void addEdge(int v, int u) {
    574     if (v == -1 || u == -1) return;
    575     g[v].push_back(u);
    576 }
    577  
    578 int it = 0;
    579  
    580 int precalc(int l, int r, int minc) {
    581     int xx = minc;
    582     state++;
    583     int vres = state;
    584     if (l > r) return vres;
    585     pii p = getmax(1, 0, n - 1, l, r);
    586 
    587     vi t;
    588  
    589     int pos = p.second;
    590     while (pos >= l) {
    591         t.push_back(pos);
    592         pos = nxtL[pos];
    593     }
    594  
    595     reverse(t.begin(), t.end());
    596  
    597     pos = nxtR[p.second];
    598     while (pos <= r) {
    599         t.push_back(pos);
    600         pos = nxtR[pos];
    601     }
    602  
    603     for (int x : t) minc = min(minc, c[x]);
    604     for (int x : t) num[x] = vres;
    605     if (xx <= (int)1e9) ans += minc;
    606  
    607     cost1[vres] = minc;
    608  
    609     ans += 1ll * minc * ((int)t.size() - 1);
    610     addEdge(vres, precalc(l, t[0] - 1, minc));
    611  
    612     for (int i = 1; i < t.size(); i++) {
    613         addEdge(vres, precalc(t[i - 1] + 1, t[i] - 1, minc));
    614     }
    615  
    616     addEdge(vres, precalc(t.back() + 1, r, minc));
    617  
    618     for (int v : t) num[v] = vres;
    619     return vres;
    620 }
    621  
    622 void go(int v) {
    623     if (!cost1[v]) return;
    624     if (!g[v].size()) return;
    625     if (v == 1) ans -= 1ll * ((int)g[v].size() - 2) * cost1[v];
    626     else ans -= 1ll * ((int)g[v].size() - 1) * cost1[v];
    627     cost1[v] = 0;
    628     for (int u : g[v]) {
    629         go(u);
    630     }
    631  
    632  
    633 }
    634  
    635 void solve() {
    636     cin >> n;
    637     for (int i = 0; i < n; i++) cin >> a[i];
    638     for (int i = 0; i < n; i++) cin >> c[i];
    639     vi p(n);
    640     for (int i = 0; i < n; i++) cin >> p[i], p[i]--;
    641     map <int, int> lst;
    642     for (int i = 0; i < n; i++) {
    643         if (lst.find(a[i]) == lst.end()) nxtL[i] = -1;
    644         else nxtL[i] = lst[a[i]];
    645         lst[a[i]] = i;
    646     }
    647     lst.clear();
    648     for (int i = n - 1; i >= 0; i--) {
    649         if (lst.find(a[i]) == lst.end()) nxtR[i] = n;
    650         else nxtR[i] = lst[a[i]];
    651         lst[a[i]] = i;
    652     }
    653  
    654     build(1, 0, n - 1);
    655     for (int i = 0; i <= 3 * n; i++) g[i].clear();
    656     ans = 0;
    657     state = 0;
    658     int root = precalc(0, n - 1, (int)1e9 + 1);
    659     cout << ans << " ";
    660  
    661     for (int i = 0; i < n; i++) {
    662         int j = num[p[i]];
    663         go(j);
    664         cout << ans << " ";
    665     }
    666     
    667     cout << "\n";
    668 }
    669  
    670 int main()
    671 {
    672     int T = 1;
    673     cin >> T;
    674     while (T--) {
    675         solve();
    676     }
    677     return 0;
    678 }
    679 ```
    680 
    681 ### [2176F - Omega Numbers](/contest/2176/problem/F "Codeforces Round 1070 (Div. 2)")
    682 
    683 **Hints**
    684 
    685 **Hint 1**
    686 
    687 Try to express $\omega(x \cdot y)$ in terms of $\omega(x)$ and $\omega(y)$.
    688 
    689 **Hint 2**
    690 
    691 $\omega(x \cdot y) = \omega(x) + \omega(y) - \omega(\operatorname{gcd}(x,y))$. How large can $\omega(x)$ and $\omega(x \cdot y)$ be?
    692 
    693 **Hint 3**
    694 
    695 $\omega(x) \leq 6$, $\omega(x \cdot y) \leq 12$. How can we count the number of pairs ($x,y$) with a fixed sum $\omega(x)+\omega(y)=const$ and a fixed $\operatorname{gcd}(x,y)=const$?
    696 
    697 **Solution**
    698 
    699 Let $K$ denote the maximum number of unique primes in the factorization of any number under the given constraints. In this problem, $K \leq 6$, and asymptotically $K=O(\operatorname{log}(maxA))$.
    700 
    701 Let's try to compute $dp[g][sum_{len}]$ — the number of ordered pairs ($i,j$) such that $\operatorname{gcd}(a_i,a_j)=g$, and $\omega(a_i)+\omega(a_j)=sum_{len}$. If we can compute this dynamic programming, then the answer to the problem is: $\sum_{g=1}^{g=n}\sum_{len=1}^{len=2 \cdot K}dp[g][sum_{len}] \cdot (sum_{len}-\omega(g))^k$.
    702 
    703 A well-known method can be used to count the number of pairs of numbers in the array ($i,j$) for which $\operatorname{gcd}(a_i,a_j)=g$ for any number $g$ from $1$ to $maxA$. Let's modify this method for our problem.
    704 
    705 Let $cnt[x][len]$ be the number of numbers in the original array that are divisible by $x$, and for which $\omega(x)$ equals $len$.
    706 
    707 To compute this auxiliary dynamic programming, we can iterate over each $x$ from $1$ to $maxA$, and for each $x$, iterate over its multiples and add to $cnt[x][\omega(i \cdot x)]$ the count of multiples $i \cdot x$ from the array. The asymptotic complexity of this counting is $O(n \cdot \operatorname{log}(n))$ (partial sums of the harmonic series).
    708 
    709 Now we are ready to compute the dynamic programming $dp[g][sum_{len}]$. Let's iterate over the greatest common divisor $g$ from $maxA$ down to $1$. If we simply wanted to count the number of pairs with $\operatorname{gcd}=g$, we would subtract the already counted pairs with larger multiples of $\operatorname{gcd}$.
    710 
    711 But now we also have a fixed total length $\omega(x)$ of both numbers in the pair. Therefore, for a fixed $g$, we will also iterate over 2 parameters — $len_a$ and $len_b$, that is, $\omega(a)$ and $\omega(b)$ for both numbers.
    712 
    713 Then $dp[g][sum_{len}]=dp[g][\omega(a) + \omega(b)]=dp[g][i+j]=cnt[g][i] \cdot cnt[g][j]$, where $i,j$ are iterated from $1$ to $K$. Here we also need to be careful and account for the case when $i=j$, in which case we add $\frac{cnt[g][i] \cdot (cnt[g][i] - 1)}{2}$ to $dp[g][i+j]$.
    714 
    715 Next, we simply iterate over the multiples of $g$: $2 \cdot g, 3 \cdot g, \ldots$, to subtract the intersections $dp[g][sum_{len}] = dp[g][sum_{len}] - dp[i \cdot g][sum_{len}]$.
    716 
    717 The asymptotic complexity of the solution is $O(maxA \cdot (K^2 + K \cdot \operatorname{log}(maxA)))$.
    718 
    719 **Implementation**
    720 
    721 ```
    722 #include <bits/stdc++.h>
    723  
    724 using std::cin;
    725 using std::cout;
    726 using vi = std::vector<int>;
    727 using vvi = std::vector<vi>;
    728 using ll = long long;
    729  
    730 const auto ready = []()
    731     {
    732         cin.tie(0);
    733         std::ios_base::sync_with_stdio(false);
    734         return true;
    735     }();
    736  
    737 ll binpow(ll a, ll p, ll mod)
    738 {
    739     ll res = 1;
    740     ll mult = a;
    741     while (p) {
    742         if (p & 1) res = res * mult % mod;
    743         mult = mult * mult % mod;
    744         p >>= 1;
    745     }
    746     return res;
    747 }
    748  
    749 const ll mod = 998244353;
    750 const int max_a = 2e5 + 10;
    751 const int max_len = 6;
    752 vi fi_div(max_a);
    753 vi num_len(max_a);
    754  
    755 void precalc() {
    756     // Here we precompute the number of unique primes in each number, i.e. w(n)
    757     for (int i = 2; i < max_a; ++i) {
    758         if (fi_div[i] == 0) {
    759             for (int j = i; j < max_a; j += i) {
    760                 if (fi_div[j] == 0) fi_div[j] = i;
    761             }
    762         }
    763     }
    764  
    765     for (int i = 2; i < max_a; ++i) {
    766         int x = i;
    767         int len = 0;
    768         while (x > 1) {
    769             ++len;
    770             int tmp = fi_div[x];
    771             while (fi_div[x] == tmp) x /= tmp;
    772         }
    773         num_len[i] = len;
    774     }
    775 }
    776  
    777 void solve() {
    778     int n, k;
    779     cin >> n >> k;
    780  
    781     vi vec(n);
    782     for(int i = 0; i < n; ++i) cin >> vec[i];
    783  
    784     vvi cnt(n + 1, vi(max_len + 1));
    785  
    786     for(int i = 0; i < n; ++i) {
    787         int x = vec[i];
    788         cnt[vec[i]][num_len[x]] += 1;
    789     }
    790     
    791     // Here we calcualte auxilary dp - cnt[x][len] - how many numbers with w(n) = len are divisible by x
    792     for (int i = 1; i < n + 1; ++i) {
    793         vi dp(max_len + 1);
    794  
    795         for (int j = i; j < n + 1; j += i) {
    796             for(int s =0 ; s < max_len + 1; ++s) dp[s] += cnt[j][s];
    797         }
    798         cnt[i] = dp;
    799     }
    800     
    801     vvi dp(n + 1, vi(2 * max_len + 1));
    802     ll ans = 0LL;
    803     
    804     // Here we calcualte dp[g][len]
    805     for (int g = n; g >= 1; --g) {
    806         // Account for cases len_a != len_b
    807         for (int len1 = 0; len1 <= max_len; ++len1) {
    808             for (int len2 = len1 + 1; len2 <= max_len; ++len2) {
    809                 dp[g][len1 + len2] += 1LL * cnt[g][len1] * cnt[g][len2] % mod;
    810                 dp[g][len1 + len2] %= mod;
    811             }
    812         }
    813         // Account for cases len_a = len_b
    814         for (int len = 0; len <= max_len; ++len) {
    815             dp[g][len + len] += 1LL * cnt[g][len] * (cnt[g][len] - 1) / 2 % mod;
    816             dp[g][len + len] %= mod;
    817         }
    818         
    819         // Subtruct states with where gcd is multiple of current g
    820         for (int j = 2 * g; j < n + 1; j += g) {
    821             for(int s = 0; s < 2 * max_len + 1; ++s) {
    822                 dp[g][s] -= dp[j][s];
    823                 dp[g][s] %= mod;
    824             }
    825         }
    826         
    827         for(int s = 0; s <  2 * max_len + 1; ++s) {
    828             dp[g][s] %= mod;
    829             dp[g][s] += mod;
    830             dp[g][s] %= mod;
    831         }
    832     
    833         // Add k-th powers to the answer
    834         int gcd_len = num_len[g];
    835         for (int len = 0; len < 2 * max_len + 1; ++len) {
    836             int rad = len - gcd_len;
    837             ans += dp[g][len] % mod * binpow(rad, k, mod) % mod;
    838             ans %= mod;
    839         }
    840  
    841     }
    842     cout << ans << "\n";
    843 }
    844  
    845 int main()
    846 {
    847     precalc();
    848     int t;
    849     cin >> t;
    850     while (t--) solve();
    851     return 0;
    852 }
    853 ```
    854 
    855 Tutorial of [Codeforces Round 1070 (Div. 2)](https://codeforces.com/contest/2176)