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