1292.md (41984B)
1 Source: https://codeforces.com/blog/entry/73051 2 3 All themes written by [AkiLotus](/profile/AkiLotus "Master AkiLotus") (I am the only one in the team playing Cytus II anyway :D). 4 5 ## [1293A - ConneR and the A.R.C. Markland-N](/contest/1293/problem/A "Codeforces Round 614 (Div. 2)") 6 7 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 8 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999"), [AkiLotus](/profile/AkiLotus "Master AkiLotus") 9 Editorialist: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999"), [AkiLotus](/profile/AkiLotus "Master AkiLotus") 10 11 **Tutorial** 12 13 Tutorial is loading... 14 15 **Solution (Akikaze, C++)** 16 17 Submission link: [69149995](/contest/1293/submission/69149995 "Submission 69149995 by AkiLotus") 18 19 **Source code in plain text** 20 21 ``` 22 #pragma GCC optimize("Ofast") 23 24 #include <bits/stdc++.h> 25 using namespace std; 26 27 #define endl '\n' 28 29 int n, s, k; 30 vector<int> a; 31 32 void Input() { 33 cin >> n >> s >> k; a.clear(); a.resize(k); 34 for (auto &z: a) cin >> z; 35 } 36 37 void Solve() { 38 for (int i=0; i<=k; i++) { 39 if (s-i >= 1 && find(a.begin(), a.end(), s-i) == a.end()) {cout << i << endl; return;} 40 if (s+i <= n && find(a.begin(), a.end(), s+i) == a.end()) {cout << i << endl; return;} 41 } 42 assert(false); // if reached this line, the solution failed to find a free floor 43 } 44 45 int main(int argc, char* argv[]) { 46 ios_base::sync_with_stdio(0); cin.tie(NULL); 47 int T; cin >> T; while (T--) {Input(); Solve();} return 0; 48 } 49 ``` 50 51 **Solution (Akikaze, Java 8)** 52 53 Submission link: [69150848](/contest/1293/submission/69150848 "Submission 69150848 by AkiLotus") 54 55 **Source code in plain text** 56 57 ``` 58 import java.io.*; 59 import java.util.*; 60 61 public class Akisolution { 62 public static Scanner sc = new Scanner(System.in); 63 public static PrintWriter out = new PrintWriter(System.out, true); 64 public static int n, s, k; 65 public static int[] a; 66 67 public static boolean exist(int[] arr, int x) { 68 for (int i=0; i<arr.length; i++) { 69 if (arr[i] == x) return true; 70 } 71 return false; 72 } 73 74 public static void Input() { 75 n = sc.nextInt(); s = sc.nextInt(); k = sc.nextInt(); 76 a = new int[k]; 77 for (int i=0; i<k; i++) a[i] = sc.nextInt(); 78 } 79 80 public static void Solve() { 81 for (int i=0; i<=k; i++) { 82 if (s-i >= 1 && !exist(a, s-i)) {out.println(i); return;} 83 if (s+i <= n && !exist(a, s+i)) {out.println(i); return;} 84 } 85 assert false; // if reached this line, the solution failed to find a free floor 86 } 87 88 public static void main(String[] args) { 89 int t = sc.nextInt(); 90 while (t-- > 0) {Input(); Solve();} 91 } 92 } 93 ``` 94 95 **Solution (Akikaze, Python 3)** 96 97 Submission link: [69150816](/contest/1293/submission/69150816 "Submission 69150816 by AkiLotus") 98 99 **Source code in plain text** 100 101 ``` 102 T = int(input()) 103 for test_no in range(T): 104 n, s, k = map(int, input().split()) 105 a = list(map(int, input().split())) 106 107 for i in range(0, k+1): 108 if s-i >= 1 and not s-i in a: 109 print(i); break 110 if s+i <= n and not s+i in a: 111 print(i); break 112 else: assert(False) # if reached this line, the solution failed to find a free floor 113 ``` 114 115 ## [1293B - JOE is on TV!](/contest/1293/problem/B "Codeforces Round 614 (Div. 2)") 116 117 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 118 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 119 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 120 121 **Tutorial** 122 123 Tutorial is loading... 124 125 **Solution (Akikaze, C++)** 126 127 Submission link: [69151243](/contest/1293/submission/69151243 "Submission 69151243 by AkiLotus") 128 129 **Source code in plain text** 130 131 ``` 132 #pragma GCC optimize("Ofast") 133 134 #include <bits/stdc++.h> 135 using namespace std; 136 137 #define endl '\n' 138 139 int n; 140 141 void Input() { 142 cin >> n; 143 } 144 145 void Solve() { 146 double ans = 0; 147 for (int i=1; i<=n; i++) ans += 1.0 / i; 148 149 cout << fixed << setprecision(12) << ans << endl; 150 } 151 152 int main(int argc, char* argv[]) { 153 ios_base::sync_with_stdio(0); cin.tie(NULL); 154 Input(); Solve(); return 0; 155 } 156 ``` 157 158 **Solution (Akikaze, Java 8)** 159 160 Submission link: [69151737](/contest/1293/submission/69151737 "Submission 69151737 by AkiLotus") 161 162 **Source code in plain text** 163 164 ``` 165 import java.io.*; 166 import java.util.*; 167 168 public class Akisolution { 169 public static Scanner sc = new Scanner(System.in); 170 public static PrintWriter out = new PrintWriter(System.out, true); 171 public static int n; 172 173 public static void Input() { 174 n = sc.nextInt(); 175 } 176 177 public static void Solve() { 178 double ans = 0; 179 for (int i=1; i<=n; i++) ans += 1.0 / i; 180 181 out.printf("%.12f\n", ans); 182 } 183 184 public static void main(String[] args) { 185 Input(); Solve(); 186 } 187 } 188 ``` 189 190 **Solution (Akikaze, Python 3)** 191 192 Submission link: [69151256](/contest/1293/submission/69151256 "Submission 69151256 by AkiLotus") 193 194 **Source code in plain text** 195 196 ``` 197 T = 1 198 for test_no in range(T): 199 n = int(input()) 200 ans = sum([1.0 / i for i in range(1, n+1)]) 201 202 print(ans) 203 ``` 204 205 ## [1292A - NEKO's Maze Game](/contest/1292/problem/A "Codeforces Round 614 (Div. 1)") 206 207 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 208 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999"), [AkiLotus](/profile/AkiLotus "Master AkiLotus") 209 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 210 211 **Tutorial** 212 213 Tutorial is loading... 214 215 **Video editorial** 216 217 Video by [Errichto](/profile/Errichto "International Grandmaster Errichto"): <https://www.youtube.com/watch?v=mhrvlor1qH0> 218 219 **Solution (Akikaze, C++)** 220 221 Submission link: [69151594](/contest/1292/submission/69151594 "Submission 69151594 by AkiLotus") 222 223 **Source code in plain text** 224 225 ``` 226 #pragma GCC optimize("Ofast") 227 228 #include <bits/stdc++.h> 229 using namespace std; 230 231 #define endl '\n' 232 233 int n, q; 234 vector<vector<int>> lava; 235 236 void Input() { 237 cin >> n >> q; 238 lava.resize(2, vector<int>(n, 0)); 239 } 240 241 void Solve() { 242 int blockedPair = 0; 243 while (q--) { 244 int x, y; cin >> x >> y; x--; y--; 245 int delta = (lava[x][y] == 0) ? +1 : -1; 246 247 lava[x][y] = 1 - lava[x][y]; 248 for (int dy=-1; dy<=1; dy++) { 249 if (y+dy < 0 || y+dy >= n) continue; 250 251 if (lava[1-x][y+dy] == 1) blockedPair += delta; 252 } 253 254 cout << ((blockedPair == 0) ? "Yes\n" : "No\n"); 255 } 256 } 257 258 int main(int argc, char* argv[]) { 259 ios_base::sync_with_stdio(0); cin.tie(NULL); 260 Input(); Solve(); return 0; 261 } 262 ``` 263 264 **Solution (Akikaze, Java 8)** 265 266 Submission link: [69151628](/contest/1292/submission/69151628 "Submission 69151628 by AkiLotus") 267 268 **Source code in plain text** 269 270 ``` 271 import java.io.*; 272 import java.util.*; 273 274 public class Akisolution { 275 public static Scanner sc = new Scanner(System.in); 276 public static PrintWriter out = new PrintWriter(System.out, true); 277 public static int n, q; 278 public static int[][] lava; 279 280 public static void Input() { 281 n = sc.nextInt(); q = sc.nextInt(); 282 lava = new int[2][n]; 283 } 284 285 public static void Solve() { 286 int blockedPair = 0; 287 while (q-- > 0) { 288 int x = sc.nextInt() - 1, y = sc.nextInt() - 1; 289 int delta = (lava[x][y] == 0) ? +1 : -1; 290 291 lava[x][y] = 1 - lava[x][y]; 292 for (int dy=-1; dy<=1; dy++) { 293 if (y+dy < 0 || y+dy >= n) continue; 294 295 if (lava[1-x][y+dy] == 1) blockedPair += delta; 296 } 297 298 if (blockedPair == 0) out.println("Yes"); 299 else out.println("No"); 300 } 301 } 302 303 public static void main(String[] args) { 304 Input(); Solve(); 305 } 306 } 307 ``` 308 309 **Solution (Akikaze, Python 3)** 310 311 Submission link: [69151636](/contest/1292/submission/69151636 "Submission 69151636 by AkiLotus") 312 313 **Source code in plain text** 314 315 ``` 316 T = 1 317 for test_no in range(T): 318 n, q = map(int, input().split()) 319 lava = [[0 for j in range(n)] for i in range(2)] 320 321 blockedPair = 0 322 while q > 0: 323 q -= 1 324 x, y = map(lambda s: int(s)-1, input().split()) 325 delta = +1 if lava[x][y] == 0 else -1 326 327 lava[x][y] = 1 - lava[x][y] 328 for dy in range(-1, 2): 329 if y + dy >= 0 and y + dy < n and lava[1-x][y+dy] == 1: 330 blockedPair += delta 331 332 if blockedPair == 0: print('Yes') 333 else: print('No') 334 ``` 335 336 ## [1292B - Aroma's Search](/contest/1292/problem/B "Codeforces Round 614 (Div. 1)") 337 338 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus") feat. [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 339 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999"), [AkiLotus](/profile/AkiLotus "Master AkiLotus") 340 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 341 342 **Tutorial** 343 344 Tutorial is loading... 345 346 **Solution (Akikaze, C++)** 347 348 Submission link: [69152149](/contest/1292/submission/69152149 "Submission 69152149 by AkiLotus") 349 350 **Source code in plain text** 351 352 ``` 353 #pragma GCC optimize("Ofast") 354 355 #include <bits/stdc++.h> 356 using namespace std; 357 358 #define endl '\n' 359 360 long long x0, y0, ax, ay, bx, by, xs, ys, t; 361 362 void Input() { 363 cin >> x0 >> y0 >> ax >> ay >> bx >> by; 364 cin >> xs >> ys >> t; 365 } 366 367 void Solve() { 368 vector<long long> x(1, x0), y(1, y0); 369 long long LIMIT = (1LL << 62) - 1; 370 while ((LIMIT - bx) / ax >= x.back() && (LIMIT - by) / ay >= y.back()) { 371 x.push_back(ax * x.back() + bx); y.push_back(ay * y.back() + by); 372 } 373 374 int n = x.size(); 375 int ans = 0; 376 for (int i=0; i<n; i++) { 377 for (int j=i; j<n; j++) { 378 long long length = x[j] - x[i] + y[j] - y[i]; 379 long long dist2Left = abs(xs - x[i]) + abs(ys - y[i]); 380 long long dist2Right = abs(xs - x[j]) + abs(ys - y[j]); 381 if (length <= t - dist2Left || length <= t - dist2Right) ans = max(ans, j-i+1); 382 } 383 } 384 385 cout << ans << endl; 386 } 387 388 int main(int argc, char* argv[]) { 389 ios_base::sync_with_stdio(0); cin.tie(NULL); 390 Input(); Solve(); return 0; 391 } 392 ``` 393 394 **Solution (Akikaze, Java 8)** 395 396 Submission link: [69152154](/contest/1292/submission/69152154 "Submission 69152154 by AkiLotus") 397 398 **Source code in plain text** 399 400 ``` 401 import java.io.*; 402 import java.util.*; 403 404 public class Akisolution { 405 public static Scanner sc = new Scanner(System.in); 406 public static PrintWriter out = new PrintWriter(System.out, true); 407 public static long x0, y0, ax, ay, bx, by, xs, ys, t; 408 409 public static long abs(long x) {return ((x > 0) ? x : -x);} 410 411 public static void Input() { 412 x0 = sc.nextLong(); y0 = sc.nextLong(); 413 ax = sc.nextLong(); ay = sc.nextLong(); bx = sc.nextLong(); by = sc.nextLong(); 414 xs = sc.nextLong(); ys = sc.nextLong(); t = sc.nextLong(); 415 } 416 417 public static void Solve() { 418 ArrayList<Long> x = new ArrayList<>(), y = new ArrayList<>(); 419 x.add(x0); y.add(y0); 420 long LIMIT = ((long)1 << 62) - 1; 421 int n = x.size(); 422 while ((LIMIT - bx) / ax >= x.get(n - 1) && (LIMIT - by) / ay >= y.get(n - 1)) { 423 x.add(ax * x.get(n - 1) + bx); y.add(ay * y.get(n - 1) + by); n++; 424 } 425 426 int ans = 0; 427 for (int i=0; i<n; i++) { 428 for (int j=i; j<n; j++) { 429 long length = x.get(j) - x.get(i) + y.get(j) - y.get(i); 430 long dist2Left = abs(xs - x.get(i)) + abs(ys - y.get(i)); 431 long dist2Right = abs(xs - x.get(j)) + abs(ys - y.get(j)); 432 if (length <= t - dist2Left || length <= t - dist2Right) { 433 ans = (ans > j-i+1) ? ans : (j - i + 1); 434 } 435 } 436 } 437 438 out.println(ans); 439 } 440 441 public static void main(String[] args) { 442 Input(); Solve(); 443 } 444 } 445 ``` 446 447 **Solution (Akikaze, Python 3)** 448 449 Submission link: [69152156](/contest/1292/submission/69152156 "Submission 69152156 by AkiLotus") 450 451 **Source code in plain text** 452 453 ``` 454 T = 1 455 for test_no in range(T): 456 x0, y0, ax, ay, bx, by = map(int, input().split()) 457 xs, ys, t = map(int, input().split()) 458 459 LIMIT = 2 ** 62 - 1 460 x, y = [x0], [y0] 461 while ((LIMIT - bx) / ax >= x[-1] and (LIMIT - by) / ay >= y[-1]): 462 x.append(ax * x[-1] + bx) 463 y.append(ay * y[-1] + by) 464 465 n = len(x) 466 ans = 0 467 for i in range(n): 468 for j in range(i, n): 469 length = x[j] - x[i] + y[j] - y[i] 470 dist2Left = abs(xs - x[i]) + abs(ys - y[i]) 471 dist2Right = abs(xs - x[j]) + abs(ys - y[j]) 472 if (length <= t - dist2Left or length <= t - dist2Right): ans = max(ans, j-i+1) 473 474 print(ans) 475 ``` 476 477 ## [1292C - Xenon's Attack on the Gangs](/contest/1292/problem/C "Codeforces Round 614 (Div. 1)") 478 479 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 480 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 481 Editorialist: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 482 483 **Tutorial** 484 485 Tutorial is loading... 486 487 **Solution (xuanquang1999, C++)** 488 489 Submission link: [69152556](/contest/1292/submission/69152556 "Submission 69152556 by AkiLotus") 490 491 **Source code in plain text** 492 493 ``` 494 #include <bits/stdc++.h> 495 496 using namespace std; 497 498 int n, root; 499 vector<vector<int>> tree, par, sub; 500 vector<vector<long long>> dp; 501 502 void dfs(int u) { 503 sub[root][u] = 1; 504 for(int v: tree[u]) { 505 if (v == par[root][u]) 506 continue; 507 par[root][v] = u; 508 dfs(v); 509 sub[root][u] += sub[root][v]; 510 } 511 } 512 513 long long getDP(int u, int v) { 514 if (u == v) return 0; 515 if (dp[u][v] != -1) return dp[u][v]; 516 517 long long res = sub[u][v] * sub[v][u] + max(getDP(par[v][u], v), getDP(u, par[u][v])); 518 return dp[u][v] = res; 519 } 520 521 void input() { 522 scanf("%d", &n); 523 524 tree.assign(n, vector<int>()); 525 for(int i = 0; i < n-1; ++i) { 526 int u, v; 527 scanf("%d%d", &u, &v); 528 --u; --v; 529 tree[u].push_back(v); tree[v].push_back(u); 530 } 531 } 532 533 void solve() { 534 // Preprocessing 535 par.assign(n, vector<int>(n, -1)); 536 sub.assign(n, vector<int>(n, -1)); 537 for(int u = 0; u < n; ++u) { 538 root = u; 539 dfs(u); 540 } 541 542 // Calculating DP 543 dp.assign(n, vector<long long>(n, -1LL)); 544 long long ans = 0; 545 for(int u = 0; u < n; ++u) 546 for(int v = 0; v < n; ++v) 547 ans = max(ans, getDP(u, v)); 548 549 cout << ans << endl; 550 } 551 552 int main() { 553 input(); 554 solve(); 555 556 return 0; 557 } 558 ``` 559 560 **Solution (xuanquang1999, Java 8)** 561 562 Submission link: [69152568](/contest/1292/submission/69152568 "Submission 69152568 by AkiLotus") 563 564 **Source code in plain text** 565 566 ``` 567 import java.io.PrintWriter; 568 import java.util.ArrayList; 569 import java.util.Scanner; 570 571 public class Main { 572 private static Scanner in; 573 private static PrintWriter out; 574 575 private static int n, root; 576 private static ArrayList<Integer>[] tree; 577 private static int[][] par, sub; 578 private static long[][] dp; 579 580 private static long getDP(int u, int v) { 581 if (u == v) return 0; 582 if (dp[u][v] != -1) return dp[u][v]; 583 584 long res = sub[u][v] * sub[v][u] + Math.max(getDP(par[v][u], v), getDP(u, par[u][v])); 585 return dp[u][v] = res; 586 } 587 588 private static void dfs(int u) { 589 sub[root][u] = 1; 590 for(int v: tree[u]) { 591 if (v == par[root][u]) 592 continue; 593 par[root][v] = u; 594 dfs(v); 595 sub[root][u] += sub[root][v]; 596 } 597 } 598 599 private static void input() { 600 n = in.nextInt(); 601 602 tree = new ArrayList[n]; 603 for(int u = 0; u < n; ++u) 604 tree[u] = new ArrayList<>(); 605 for(int i = 0; i < n-1; ++i) { 606 int u = in.nextInt(), v = in.nextInt(); 607 u -= 1; v -= 1; 608 tree[u].add(v); tree[v].add(u); 609 } 610 } 611 612 private static void solve() { 613 // Preprocessing 614 par = new int[n][n]; 615 sub = new int[n][n]; 616 for(int u = 0; u < n; ++u) { 617 par[u][u] = -1; 618 root = u; 619 dfs(u); 620 } 621 622 // Calculating DP 623 dp = new long[n][n]; 624 for(int u = 0; u < n; ++u) 625 for(int v = 0; v < n; ++v) 626 dp[u][v] = -1; 627 628 long ans = 0; 629 for(int u = 0; u < n; ++u) 630 for(int v = 0; v < n; ++v) 631 ans = Math.max(ans, getDP(u, v)); 632 633 out.println(ans); 634 } 635 636 public static void main(String[] args) { 637 in = new Scanner(System.in); 638 out = new PrintWriter(System.out); 639 640 input(); 641 solve(); 642 643 out.close(); 644 } 645 } 646 ``` 647 648 **Solution (pajenegod, PyPy3)** 649 650 Submission link: [72000655](/contest/1292/submission/72000655 "Submission 72000655 by pajenegod") 651 652 **Source code in plain text** 653 654 ``` 655 import sys 656 657 # Read input and build the graph 658 inp = [int(x) for x in sys.stdin.buffer.read().split()]; ii = 0 659 n = inp[ii]; ii += 1 660 coupl = [[] for _ in range(n)] 661 for _ in range(n - 1): 662 u = inp[ii] - 1; ii += 1 663 v = inp[ii] - 1; ii += 1 664 coupl[u].append(v) 665 coupl[v].append(u) 666 667 # Relabel to speed up n^2 operations later on 668 bfs = [0] 669 found = [0]*n 670 found[0] = 1 671 for node in bfs: 672 for nei in coupl[node]: 673 if not found[nei]: 674 found[nei] = 1 675 bfs.append(nei) 676 677 new_label = [0]*n 678 for i in range(n): 679 new_label[bfs[i]] = i 680 681 coupl = [coupl[i] for i in bfs] 682 for c in coupl: 683 c[:] = [new_label[x] for x in c] 684 685 ##### DP using multisource bfs 686 687 DP = [0] * (n * n) 688 size = [1] * (n * n) 689 P = [-1] * (n * n) 690 691 # Create the bfs ordering 692 bfs = [root * n + root for root in range(n)] 693 for ind in bfs: 694 P[ind] = ind 695 696 for ind in bfs: 697 node, root = divmod(ind, n) 698 for nei in coupl[node]: 699 ind2 = nei * n + root 700 if P[ind2] == -1: 701 bfs.append(ind2) 702 P[ind2] = ind 703 704 del bfs[:n] 705 706 # Do the DP 707 for ind in reversed(bfs): 708 node, root = divmod(ind, n) 709 ind2 = root * n + node 710 pind = P[ind] 711 parent = pind//n 712 713 # Update size of (root, parent) 714 size[pind] += size[ind] 715 716 # Update DP value of (root, parent) 717 DP[pind] = max(DP[pind], max(DP[ind], DP[ind2]) + size[ind] * size[ind2]) 718 print(max(DP[root * n + root] for root in range(n))) 719 ``` 720 721 **Additional notes** 722 723 [pajenegod](/profile/pajenegod "Grandmaster pajenegod") uses a variant of BFS dedicated for speed efficiency on Python 3 / PyPy3. More details [here](https://codeforces.com/blog/entry/124286?#comment-1103326). 724 725 ## [1292D - Chaotic V.](/contest/1292/problem/D "Codeforces Round 614 (Div. 1)") 726 727 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 728 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 729 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 730 731 **Tutorial** 732 733 Tutorial is loading... 734 735 **Solution (Akikaze, C++)** 736 737 Submission link: [69153064](/contest/1292/submission/69153064 "Submission 69153064 by AkiLotus") 738 739 **Source code in plain text** 740 741 ``` 742 #pragma GCC optimize("Ofast") 743 744 #include <bits/stdc++.h> 745 using namespace std; 746 747 #define endl '\n' 748 749 const int MAXK = 5000; 750 int n; vector<int> cnt(MAXK + 1, 0); 751 vector<vector<int>> primeExponential(MAXK + 1, vector<int>(MAXK + 1, 0)); 752 753 void Preprocess() { 754 for (int i=2; i<MAXK + 1; i++) { 755 for (int j=0; j<MAXK + 1; j++) primeExponential[i][j] += primeExponential[i-1][j]; 756 int tmp = i; 757 for (int x=2; x<=sqrt(tmp); x++) { 758 while (tmp % x == 0) {primeExponential[i][x]++; tmp /= x;} 759 } 760 if (tmp > 1) primeExponential[i][tmp]++; 761 } 762 } 763 764 void Input() { 765 cin >> n; 766 for (int i=0; i<n; i++) { 767 int k; cin >> k; cnt[k]++; 768 } 769 } 770 771 void Solve() { 772 Preprocess(); 773 774 vector<int> bestPD(MAXK + 1, 1); 775 long long ans = 0, cur = 0; 776 for (int i=1; i<MAXK + 1; i++) { 777 if (!cnt[i]) {bestPD[i] = 1; continue;} 778 for (int j=1; j<MAXK + 1; j++) { 779 ans += 1LL * primeExponential[i][j] * cnt[i]; 780 cur += 1LL * primeExponential[i][j] * cnt[i]; 781 if (primeExponential[i][j]) bestPD[i] = j; 782 } 783 } 784 785 while (*max_element(bestPD.begin(), bestPD.end()) > 1) { 786 vector<int> frequency(MAXK + 1, 0); 787 788 for (int i=0; i<MAXK + 1; i++) frequency[bestPD[i]] += cnt[i]; 789 790 int bestPrime = max_element(frequency.begin(), frequency.end()) - frequency.begin(); 791 int bestGroup = frequency[bestPrime]; 792 if (bestGroup * 2 <= n) break; 793 if (bestPrime == 1) break; 794 cur -= bestGroup; cur += (n - bestGroup); ans = min(ans, cur); 795 796 for (int i=0; i<MAXK + 1; i++) { 797 if (bestPD[i] != bestPrime) bestPD[i] = 1; 798 if (bestPD[i] == 1) continue; 799 primeExponential[i][bestPD[i]] -= 1; 800 while (bestPD[i] > 1 && primeExponential[i][bestPD[i]] == 0) bestPD[i]--; 801 } 802 } 803 804 cout << ans << endl; 805 } 806 807 int main(int argc, char* argv[]) { 808 ios_base::sync_with_stdio(0); cin.tie(NULL); 809 Input(); Solve(); return 0; 810 } 811 ``` 812 813 **Solution (Akikaze, Java 8)** 814 815 Submission link: [69153077](/contest/1292/submission/69153077 "Submission 69153077 by AkiLotus") 816 817 **Source code in plain text** 818 819 ``` 820 import java.io.*; 821 import java.util.*; 822 823 public class Akisolution { 824 public static Scanner sc = new Scanner(System.in); 825 public static PrintWriter out = new PrintWriter(System.out, true); 826 public static final int MAXK = 5000; 827 public static int n; 828 public static int[] cnt = new int[MAXK + 1]; 829 public static int[][] primeExponential = new int[MAXK + 1][MAXK + 1]; 830 831 public static long min(long a, long b) {return ((a < b) ? a : b);} 832 833 public static int max_element(int[] arr) { 834 int res = -1000000000; 835 for (int i=0; i<arr.length; i++) { 836 if (arr[i] > res) res = arr[i]; 837 } 838 return res; 839 } 840 841 public static int max_id(int[] arr) { 842 int res = -1000000000, id = -1; 843 for (int i=0; i<arr.length; i++) { 844 if (arr[i] > res) { 845 res = arr[i]; 846 id = i; 847 } 848 } 849 return id; 850 } 851 852 public static void Preprocess() { 853 for (int i=2; i<MAXK + 1; i++) { 854 for (int j=0; j<MAXK + 1; j++) primeExponential[i][j] += primeExponential[i-1][j]; 855 int tmp = i; 856 for (int x=2; x<=Math.sqrt(tmp); x++) { 857 while (tmp % x == 0) {primeExponential[i][x]++; tmp /= x;} 858 } 859 if (tmp > 1) primeExponential[i][tmp]++; 860 } 861 } 862 863 public static void Input() { 864 n = sc.nextInt(); 865 for (int i=0; i<n; i++) { 866 int k = sc.nextInt(); 867 cnt[k] += 1; 868 } 869 } 870 871 public static void Solve() { 872 Preprocess(); 873 874 int[] bestPD = new int[MAXK + 1]; 875 for (int i=0; i<MAXK + 1; i++) bestPD[i] = 1; 876 long ans = 0, cur = 0; 877 for (int i=1; i<MAXK + 1; i++) { 878 if (cnt[i] == 0) {bestPD[i] = 1; continue;} 879 for (int j=1; j<MAXK + 1; j++) { 880 ans += (long)primeExponential[i][j] * cnt[i]; 881 cur += (long)primeExponential[i][j] * cnt[i]; 882 if (primeExponential[i][j] != 0) bestPD[i] = j; 883 } 884 } 885 886 while (max_element(bestPD) > 1) { 887 int[] frequency = new int[MAXK + 1]; 888 889 for (int i=0; i<MAXK + 1; i++) frequency[bestPD[i]] += cnt[i]; 890 891 int bestPrime = max_id(frequency); 892 int bestGroup = frequency[bestPrime]; 893 if (bestGroup * 2 <= n) break; 894 if (bestPrime == 1) break; 895 cur -= bestGroup; cur += (n - bestGroup); ans = min(ans, cur); 896 897 for (int i=0; i<MAXK + 1; i++) { 898 if (bestPD[i] != bestPrime) bestPD[i] = 1; 899 if (bestPD[i] == 1) continue; 900 primeExponential[i][bestPD[i]] -= 1; 901 while (bestPD[i] > 1 && primeExponential[i][bestPD[i]] == 0) bestPD[i]--; 902 } 903 } 904 905 out.println(ans); 906 } 907 908 public static void main(String[] args) { 909 Input(); Solve(); 910 } 911 } 912 ``` 913 914 **Solution (Akikaze, PyPy 3)** 915 916 Submission link: [69153090](/contest/1292/submission/69153090 "Submission 69153090 by AkiLotus") 917 918 **Source code in plain text** 919 920 ``` 921 T = 1 922 for test_no in range(T): 923 MAXK = 5000 924 n = int(input()) 925 cnt = [0] * (MAXK + 1) 926 primeExponential = [[0 for j in range(MAXK + 1)] for i in range(MAXK + 1)] 927 928 line, num = (input() + ' '), 0 929 for c in line: 930 if c != ' ': num = num * 10 + (ord(c) - 48) 931 else: 932 cnt[num] += 1 933 num = 0 934 935 for i in range(2, MAXK + 1): 936 for j in range(0, MAXK + 1): primeExponential[i][j] += primeExponential[i-1][j] 937 tmp, x = i, 2 938 while x * x <= tmp: 939 while tmp % x == 0: 940 primeExponential[i][x] += 1 941 tmp //= x 942 x += 1 943 if tmp > 1: primeExponential[i][tmp] += 1 944 945 bestPD = [1] * (MAXK + 1) 946 ans, cur = 0, 0 947 948 for i in range(1, MAXK + 1): 949 if cnt[i] == 0: continue 950 for j in range(1, MAXK + 1): 951 ans += primeExponential[i][j] * cnt[i] 952 cur += primeExponential[i][j] * cnt[i] 953 if primeExponential[i][j]: bestPD[i] = j 954 955 frequency = [0] * (MAXK + 1) 956 while max(bestPD) > 1: 957 for i in range(MAXK + 1): frequency[i] = 0 958 for i in range(MAXK + 1): frequency[bestPD[i]] += cnt[i] 959 960 bestGroup = max(frequency) 961 bestPrime = frequency.index(bestGroup) 962 if bestGroup * 2 <= n: break 963 if bestPrime == 1: break 964 cur -= bestGroup 965 cur += (n - bestGroup); ans = min(ans, cur) 966 967 for i in range(MAXK + 1): 968 if bestPD[i] != bestPrime: bestPD[i] = 1 969 if bestPD[i] == 1: continue 970 primeExponential[i][bestPD[i]] -= 1 971 while bestPD[i] > 1 and primeExponential[i][bestPD[i]] == 0: bestPD[i] -= 1 972 973 print(ans) 974 ``` 975 976 ## [1292E - Rin and The Unknown Flower](/contest/1292/problem/E "Codeforces Round 614 (Div. 1)") 977 978 Author: [low_](/profile/low_ "Master low_") ([Sulfox](/profile/Sulfox "Grandmaster Sulfox") Remix) 979 Development: [low_](/profile/low_ "Master low_"), [Sulfox](/profile/Sulfox "Grandmaster Sulfox"), [AkiLotus](/profile/AkiLotus "Master AkiLotus") 980 Editorialist: [low_](/profile/low_ "Master low_") 981 982 **Tutorial** 983 984 Tutorial is loading... 985 986 **Solution (Akikaze, C++)** 987 988 Submission link: [69153383](/contest/1292/submission/69153383 "Submission 69153383 by AkiLotus") 989 990 **Source code in plain text** 991 992 ``` 993 #pragma GCC optimize("Ofast") 994 995 #include <bits/stdc++.h> 996 using namespace std; 997 998 #define endl '\n' 999 1000 int n, L, minID; 1001 string s; 1002 1003 void fill(int id, char c) { 1004 L -= (s[id] == 'L'); s[id] = c; 1005 minID = min(minID, id); 1006 } 1007 1008 void query(char cmd, string str) { 1009 cout << cmd << " " << str << endl; cout.flush(); 1010 if (cmd == '?') { 1011 int k; cin >> k; 1012 assert(k != -1); 1013 vector<int> a(k); 1014 for (auto &z: a) { 1015 cin >> z; z--; 1016 for (int i=0; i<str.size(); i++) { 1017 assert(s[z+i] == 'L' || s[z+i] == str[i]); 1018 fill(z+i, str[i]); 1019 } 1020 } 1021 } 1022 else if (cmd == '!') { 1023 int correct; cin >> correct; 1024 assert(correct); 1025 } 1026 } 1027 1028 void Input() { 1029 cin >> n; s.clear(); 1030 L = n; minID = n; s.resize(n, 'L'); 1031 } 1032 1033 void Solve() { 1034 query('?', "CH"); query('?', "CO"); 1035 query('?', "HC"); query('?', "HO"); 1036 if (L == n) { 1037 // the string exists in form O...OX...X, with X=C or X=H 1038 // or it's completely mono-character 1039 query('?', "CCC"); 1040 if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');} 1041 else { 1042 query('?', "HHH"); 1043 if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');} 1044 else { 1045 query('?', "OOO"); 1046 if (minID == n) { 1047 // obviously n=4 1048 query('?', "OOCC"); 1049 if (minID == n) {fill(0, 'O'); fill(1, 'O'); fill(2, 'H'); fill(3, 'H');} 1050 } 1051 if (s[n-1] == 'L') { 1052 string t = s; t[n-1] = 'C'; 1053 if (t[n-2] == 'L') t[n-2] = 'C'; 1054 query('?', t); 1055 if (s[n-1] == 'L') { 1056 fill(n-1, 'H'); 1057 if (s[n-2] == 'L') fill(n-2, 'H'); 1058 } 1059 } 1060 } 1061 } 1062 } 1063 else { 1064 int maxID = minID; while (maxID < n-1 && s[maxID+1] != 'L') maxID++; 1065 for (int i=minID-1; i>=0; i--) { 1066 query('?', s.substr(i+1, 1) + s.substr(minID, maxID-minID+1)); 1067 if (minID != i) { 1068 for (int x=0; x<=i; x++) fill(x, 'O'); 1069 break; 1070 } 1071 } 1072 int nextFilled; 1073 for (int i=maxID+1; i<n; i++) { 1074 if (s[i] != 'L') continue; 1075 nextFilled = i; 1076 while (nextFilled < n && s[nextFilled] == 'L') nextFilled++; 1077 query('?', s.substr(0, i) + s[i-1]); 1078 if (s[i] == 'L') { 1079 if (s[i-1] != 'O') fill(i, 'O'); 1080 else { 1081 if (nextFilled == n) { 1082 query('?', s.substr(0, i) + 'C'); 1083 if (s[i] == 'L') fill(i, 'H'); 1084 for (int x=i+1; x<nextFilled; x++) fill(x, s[i]); 1085 } 1086 else for (int x=i; x<nextFilled; x++) fill(x, s[nextFilled]); 1087 i = nextFilled - 1; 1088 } 1089 } 1090 } 1091 } 1092 query('!', s); 1093 } 1094 1095 int main(int argc, char* argv[]) { 1096 ios_base::sync_with_stdio(0); cin.tie(NULL); 1097 int T; cin >> T; while (T--) {Input(); Solve();} return 0; 1098 } 1099 ``` 1100 1101 **Solution (Akikaze, Java 8)** 1102 1103 Submission link: [69153556](/contest/1292/submission/69153556 "Submission 69153556 by AkiLotus") 1104 1105 **Source code in plain text** 1106 1107 ``` 1108 import java.io.*; 1109 import java.util.*; 1110 1111 public class Akisolution { 1112 public static Scanner sc = new Scanner(System.in); 1113 1114 public static class CPPString { 1115 // as the Java String is insanely cryptic to modify 1116 public char[] arr; 1117 1118 public CPPString() {} 1119 public CPPString(String str) {this.arr = str.toCharArray();} 1120 public CPPString(char[] ca) {this.arr = ca;} 1121 public CPPString(CPPString other) { 1122 this.arr = new char[other.arr.length]; 1123 for (int i=0; i<other.arr.length; i++) this.arr[i] = other.arr[i]; 1124 } 1125 public void resize(int length, char defaultChar) { 1126 this.arr = new char[length]; 1127 for (int i=0; i<length; i++) this.arr[i] = defaultChar; 1128 } 1129 public int size() {return this.arr.length;} 1130 public CPPString substr(int L, int len) { 1131 // get substring [L, L+len) 1132 char[] res = new char[len]; 1133 for (int i=0; i<len; i++) res[i] = this.arr[L+i]; 1134 return new CPPString(res); 1135 } 1136 public CPPString add(char ch) { 1137 char[] new_ca = new char[this.arr.length + 1]; new_ca[this.arr.length] = ch; 1138 for (int i=0; i<this.arr.length; i++) new_ca[i] = this.arr[i]; 1139 return new CPPString(new_ca); 1140 } 1141 public CPPString add(CPPString other) { 1142 char[] new_ca = new char[this.arr.length + other.arr.length]; 1143 for (int i=0; i<this.arr.length; i++) new_ca[i] = this.arr[i]; 1144 for (int i=0; i<other.arr.length; i++) new_ca[this.arr.length + i] = other.arr[i]; 1145 return new CPPString(new_ca); 1146 } 1147 1148 @Override 1149 public String toString() {return new String(arr);} 1150 } 1151 1152 public static int n, L, minID; 1153 public static CPPString s; 1154 1155 public static void fill(int id, char c) { 1156 if (s.arr[id] == 'L') L--; 1157 s.arr[id] = c; 1158 minID = (minID < id) ? minID : id; 1159 } 1160 1161 public static void query(char cmd, CPPString str) { 1162 System.out.println(cmd + " " + str); System.out.flush(); 1163 System.err.println(cmd + " " + str); 1164 if (cmd == '?') { 1165 int k = sc.nextInt(); 1166 assert (k != -1); 1167 int[] a = new int[k]; 1168 for (int index = 0; index < k; index++) { 1169 a[index] = sc.nextInt() - 1; 1170 for (int i=0; i<str.size(); i++) { 1171 assert (s.arr[a[index]+i] == 'L' || s.arr[a[index]+i] == str.arr[i]); 1172 fill(a[index]+i, str.arr[i]); 1173 } 1174 } 1175 } 1176 else if (cmd == '!') { 1177 int correct = sc.nextInt(); 1178 assert (correct == 1); 1179 } 1180 } 1181 1182 public static void query(char cmd, String str) { 1183 query(cmd, new CPPString(str)); 1184 } 1185 1186 public static void Input() { 1187 n = sc.nextInt(); s = new CPPString(); 1188 L = n; minID = n; s.resize(n, 'L'); 1189 } 1190 1191 public static void Solve() { 1192 query('?', "CH"); query('?', "CO"); 1193 query('?', "HC"); query('?', "HO"); 1194 if (L == n) { 1195 // the string exists in form O...OX...X, with X=C or X=H 1196 // or it's completely mono-character 1197 query('?', "CCC"); 1198 if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');} 1199 else { 1200 query('?', "HHH"); 1201 if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');} 1202 else { 1203 query('?', "OOO"); 1204 if (minID == n) { 1205 // obviously n=4 1206 query('?', "OOCC"); 1207 if (minID == n) { 1208 fill(0, 'O'); fill(1, 'O'); 1209 fill(2, 'H'); fill(3, 'H'); 1210 } 1211 } 1212 if (s.arr[n-1] == 'L') { 1213 CPPString t = new CPPString(s); t.arr[n-1] = 'C'; 1214 if (t.arr[n-2] == 'L') t.arr[n-2] = 'C'; 1215 query('?', t); 1216 if (s.arr[n-1] == 'L') { 1217 fill(n-1, 'H'); 1218 if (s.arr[n-2] == 'L') fill(n-2, 'H'); 1219 } 1220 } 1221 } 1222 } 1223 } 1224 else { 1225 int maxID = minID; while (maxID < n-1 && s.arr[maxID+1] != 'L') maxID++; 1226 for (int i=minID-1; i>=0; i--) { 1227 query('?', s.substr(i+1, 1).add(s.substr(minID, maxID-minID+1))); 1228 if (minID != i) { 1229 for (int x=0; x<=i; x++) fill(x, 'O'); 1230 break; 1231 } 1232 } 1233 int nextFilled; 1234 for (int i=maxID+1; i<n; i++) { 1235 if (s.arr[i] != 'L') continue; 1236 nextFilled = i; 1237 while (nextFilled < n && s.arr[nextFilled] == 'L') nextFilled++; 1238 query('?', s.substr(0, i).add(s.arr[i-1])); 1239 if (s.arr[i] == 'L') { 1240 if (s.arr[i-1] != 'O') fill(i, 'O'); 1241 else { 1242 if (nextFilled == n) { 1243 query('?', s.substr(0, i).add('C')); 1244 if (s.arr[i] == 'L') fill(i, 'H'); 1245 for (int x=i+1; x<nextFilled; x++) fill(x, s.arr[i]); 1246 } 1247 else for (int x=i; x<nextFilled; x++) fill(x, s.arr[nextFilled]); 1248 i = nextFilled - 1; 1249 } 1250 } 1251 } 1252 } 1253 query('!', s); 1254 } 1255 1256 public static void main(String[] args) { 1257 int T = sc.nextInt(); 1258 while (T-- > 0) {Input(); Solve();} 1259 } 1260 } 1261 ``` 1262 1263 **Solution (Akikaze, Python 3)** 1264 1265 Submission link: [69153398](/contest/1292/submission/69153398 "Submission 69153398 by AkiLotus") 1266 1267 **Source code in plain text** 1268 1269 ``` 1270 import sys 1271 n, L, minID = None, None, None 1272 s = [] 1273 1274 def fill(id, c): 1275 global n, L, s, minID 1276 L -= (s[id] == 'L') 1277 s = s[0:id] + c + s[id+1:] 1278 minID = min(minID, id) 1279 1280 def query(cmd, str): 1281 global n, L, s, minID 1282 print(cmd, ''.join(str)) 1283 print(cmd, ''.join(str), file=sys.stderr) 1284 sys.stdout.flush() 1285 if (cmd == '?'): 1286 result = list(map(int, input().split())) 1287 assert(result[0] != -1) 1288 for z in result[1:]: 1289 z -= 1 1290 for i in range(len(str)): 1291 assert(s[z+i] == 'L' or s[z+i] == str[i]) 1292 fill(z+i, str[i]) 1293 elif (cmd == '!'): 1294 correct = int(input()) 1295 assert(correct == 1) 1296 1297 T = int(input()) 1298 for test_no in range(T): 1299 n = int(input()) 1300 L, minID = n, n 1301 s = 'L' * n 1302 1303 query('?', "CH") 1304 query('?', "CO") 1305 query('?', "HC") 1306 query('?', "HO") 1307 if (L == n): 1308 # the string exists in form O...OX...X, with X=C or X=H 1309 # or it's completely mono-character 1310 query('?', "CCC") 1311 if (minID < n): 1312 for x in range(minID-1, -1, -1): fill(x, 'O') 1313 else: 1314 query('?', "HHH") 1315 if (minID < n): 1316 for x in range(minID-1, -1, -1): fill(x, 'O') 1317 else: 1318 query('?', "OOO") 1319 if (minID == n): 1320 # obviously n=4 1321 query('?', "OOCC") 1322 if (minID == n): 1323 fill(0, 'O') 1324 fill(1, 'O') 1325 fill(2, 'H') 1326 fill(3, 'H') 1327 1328 if (s[n-1] == 'L'): 1329 t = s[0:n-1] + 'C' 1330 if (t[n-2] == 'L'): t = t[0:n-2] + 'C' + t[n-1:] 1331 query('?', t) 1332 if (s[n-1] == 'L'): 1333 fill(n-1, 'H') 1334 if (s[n-2] == 'L'): fill(n-2, 'H') 1335 else: 1336 maxID = minID 1337 while (maxID < n-1 and s[maxID+1] != 'L'): maxID += 1 1338 for i in range(minID-1, -1, -1): 1339 query('?', s[i+1:i+2] + s[minID:maxID+1]) 1340 if (minID != i): 1341 for x in range(i+1): fill(x, 'O') 1342 break 1343 1344 nextFilled = None 1345 i = maxID + 1 1346 while i < n: 1347 if (s[i] != 'L'): 1348 i += 1 1349 continue 1350 nextFilled = i 1351 while (nextFilled < n and s[nextFilled] == 'L'): nextFilled += 1 1352 query('?', s[0:i] + s[i-1]) 1353 if (s[i] == 'L'): 1354 if (s[i-1] != 'O'): fill(i, 'O') 1355 else: 1356 if (nextFilled == n): 1357 query('?', s[0:i] + 'C') 1358 if (s[i] == 'L'): fill(i, 'H') 1359 for x in range(i+1, nextFilled): fill(x, s[i]) 1360 else: 1361 for x in range(i, nextFilled): fill(x, s[nextFilled]) 1362 i = nextFilled - 1 1363 i += 1 1364 query('!', s) 1365 ``` 1366 1367 ## [1292F - Nora's Toy Boxes](/contest/1292/problem/F "Codeforces Round 614 (Div. 1)") 1368 1369 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") × [MofK](/profile/MofK "Grandmaster MofK") 1370 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 1371 Editorialist: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 1372 1373 **Tutorial** 1374 1375 Tutorial is loading... 1376 1377 **Solution (xuanquang1999, C++)** 1378 1379 Submission link: [69153931](/contest/1292/submission/69153931 "Submission 69153931 by AkiLotus") 1380 1381 **Source code in plain text** 1382 1383 ``` 1384 #include <bits/stdc++.h> 1385 1386 using namespace std; 1387 1388 const int MOD = 1000000007; 1389 1390 bool isSubset(int a, int b) { 1391 return (a & b) == a; 1392 } 1393 1394 bool isIntersect(int a, int b) { 1395 return (a & b) != 0; 1396 } 1397 1398 void add(int &a, long long b) { 1399 a = (a + b) % MOD; 1400 } 1401 1402 // Solve for each weakly connected component (WCC) 1403 int cntOrder(vector<int> s, vector<int> t) { 1404 int p = s.size(), m = t.size(); 1405 1406 vector<int> inMask(m, 0); 1407 for(int x = 0; x < p; ++x) 1408 for(int i = 0; i < m; ++i) 1409 if (t[i] % s[x] == 0) 1410 inMask[i] |= 1 << x; 1411 1412 vector<int> cnt(1<<p, 0); 1413 for(int mask = 0; mask < (1<<p); ++mask) 1414 for(int i = 0; i < m; ++i) 1415 if (isSubset(inMask[i], mask)) 1416 ++cnt[mask]; 1417 1418 vector<vector<int>> dp(m+1, vector<int>(1<<p, 0)); 1419 for(int i = 0; i < m; ++i) 1420 dp[1][inMask[i]] += 1; 1421 for(int k = 1; k < m; ++k) { 1422 for(int mask = 0; mask < (1<<p); ++mask) { 1423 for(int i = 0; i < m; ++i) 1424 if (!isSubset(inMask[i], mask) && isIntersect(inMask[i], mask)) 1425 add(dp[k+1][mask | inMask[i]], dp[k][mask]); 1426 add(dp[k+1][mask], 1LL * dp[k][mask] * (cnt[mask] - k)); 1427 } 1428 } 1429 1430 return dp[m][(1<<p)-1]; 1431 } 1432 1433 int n; 1434 vector<int> a, degIn, s, t; 1435 vector<vector<int>> graph; 1436 vector<bool> visited; 1437 1438 void dfs(int u) { 1439 visited[u] = true; 1440 if (degIn[u] == 0) 1441 s.push_back(a[u]); 1442 else 1443 t.push_back(a[u]); 1444 1445 for(int v: graph[u]) 1446 if (!visited[v]) 1447 dfs(v); 1448 } 1449 1450 void input() { 1451 scanf("%d", &n); 1452 a.resize(n); 1453 for(int u = 0; u < n; ++u) 1454 scanf("%d", &a[u]); 1455 } 1456 1457 void solve() { 1458 // Pre-calculate C(n, k) 1459 vector<vector<int>> c(n, vector<int>(n, 0)); 1460 for(int i = 0; i < n; ++i) { 1461 c[i][0] = 1; 1462 for(int j = 1; j <= i; ++j) 1463 c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD; 1464 } 1465 1466 // Building divisibility graph 1467 degIn.assign(n, 0); 1468 graph.assign(n, vector<int>()); 1469 for(int u = 0; u < n; ++u) { 1470 for(int v = 0; v < n; ++v) { 1471 if (u != v && a[v] % a[u] == 0) { 1472 graph[u].push_back(v); 1473 graph[v].push_back(u); 1474 ++degIn[v]; 1475 } 1476 } 1477 } 1478 1479 // Solve for each WCC of divisibility graph and combine result 1480 int ans = 1; 1481 int curLen = 0; 1482 visited.assign(n, false); 1483 for(int u = 0; u < n; ++u) { 1484 if (!visited[u]) { 1485 s.clear(); 1486 t.clear(); 1487 dfs(u); 1488 1489 if (!t.empty()) { 1490 int sz = t.size() - 1; 1491 int cnt = cntOrder(s, t); 1492 1493 // Number of orders for current WCC 1494 ans = (1LL * ans * cnt) % MOD; 1495 // Number of ways to insert <sz> number to array of <curLen> elements 1496 ans = (1LL * ans * c[curLen + sz][sz]) % MOD; 1497 curLen += sz; 1498 } 1499 } 1500 } 1501 1502 printf("%d\n", ans); 1503 } 1504 1505 int main() { 1506 input(); 1507 solve(); 1508 1509 return 0; 1510 } 1511 ``` 1512 1513 **Solution (xuanquang1999, Java 8)** 1514 1515 Submission link: [69153932](/contest/1292/submission/69153932 "Submission 69153932 by AkiLotus") 1516 1517 **Source code in plain text** 1518 1519 ``` 1520 import java.io.PrintWriter; 1521 import java.util.ArrayList; 1522 import java.util.Scanner; 1523 1524 public class Main { 1525 private static Scanner in; 1526 private static PrintWriter out; 1527 private static final int MOD = (int)1e9 + 7; 1528 1529 private static int n; 1530 private static int[] a, degIn; 1531 private static ArrayList<Integer> s, t; 1532 private static boolean[] visited; 1533 private static ArrayList<Integer>[] graph; 1534 1535 private static boolean isSubset(int a, int b) { 1536 return (a & b) == a; 1537 } 1538 1539 private static boolean isIntersect(int a, int b) { 1540 return (a & b) != 0; 1541 } 1542 1543 // Solve for each weakly connected component (WCC) 1544 private static int cntOrder(ArrayList<Integer> s, ArrayList<Integer> t) { 1545 int p = s.size(), m = t.size(); 1546 1547 int[] inMask = new int[m]; 1548 for(int x = 0; x < p; ++x) 1549 for(int i = 0; i < m; ++i) 1550 if (t.get(i) % s.get(x) == 0) 1551 inMask[i] |= 1 << x; 1552 1553 int[] cnt = new int[1<<p]; 1554 for(int mask = 0; mask < (1<<p); ++mask) 1555 for(int i = 0; i < m; ++i) 1556 if (isSubset(inMask[i], mask)) 1557 ++cnt[mask]; 1558 1559 int[][] dp = new int[m+1][1<<p]; 1560 for(int i = 0; i < m; ++i) 1561 dp[1][inMask[i]] += 1; 1562 for(int k = 1; k < m; ++k) { 1563 for(int mask = 0; mask < (1<<p); ++mask) { 1564 for(int i = 0; i < m; ++i) 1565 if (!isSubset(inMask[i], mask) && isIntersect(inMask[i], mask)) 1566 dp[k+1][mask | inMask[i]] = (int)((dp[k+1][mask | inMask[i]] + dp[k][mask]) % MOD); 1567 dp[k+1][mask] = (int)((dp[k+1][mask] + (long)dp[k][mask] * (cnt[mask] - k)) % MOD); 1568 } 1569 } 1570 1571 return dp[m][(1<<p)-1]; 1572 } 1573 1574 private static void dfs(int u) { 1575 visited[u] = true; 1576 if (degIn[u] == 0) 1577 s.add(a[u]); 1578 else 1579 t.add(a[u]); 1580 1581 for(int v: graph[u]) 1582 if (!visited[v]) 1583 dfs(v); 1584 } 1585 1586 private static void input() { 1587 n = in.nextInt(); 1588 a = new int[n]; 1589 for(int u = 0; u < n; ++u) 1590 a[u] = in.nextInt(); 1591 } 1592 1593 private static void solve() { 1594 // Pre-calculate C(n, k) 1595 int[][] c = new int[n][n]; 1596 for(int i = 0; i < n; ++i) { 1597 c[i][0] = 1; 1598 for(int j = 1; j <= i; ++j) 1599 c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD; 1600 } 1601 1602 // Building divisibility graph 1603 degIn = new int[n]; 1604 graph = new ArrayList[n]; 1605 for(int u = 0; u < n; ++u) 1606 graph[u] = new ArrayList<>(); 1607 for(int u = 0; u < n; ++u) { 1608 for(int v = 0; v < n; ++v) { 1609 if (u != v && a[v] % a[u] == 0) { 1610 graph[u].add(v); 1611 graph[v].add(u); 1612 ++degIn[v]; 1613 } 1614 } 1615 } 1616 1617 // Solve for each WCC of divisibility graph and combine result 1618 int ans = 1; 1619 int curLen = 0; 1620 visited = new boolean[n]; 1621 for(int u = 0; u < n; ++u) { 1622 if (!visited[u]) { 1623 s = new ArrayList<>(); 1624 t = new ArrayList<>(); 1625 dfs(u); 1626 1627 if (!t.isEmpty()) { 1628 int sz = t.size() - 1; 1629 int cnt = cntOrder(s, t); 1630 1631 // Number of orders for current WCC 1632 ans = (int)(((long)ans * cnt) % MOD); 1633 // Number of ways to insert <sz> number to array of <curLen> elements 1634 ans = (int)(((long)ans * c[curLen + sz][sz]) % MOD); 1635 curLen += sz; 1636 } 1637 } 1638 } 1639 1640 out.println(ans); 1641 } 1642 1643 public static void main(String[] args) { 1644 in = new Scanner(System.in); 1645 out = new PrintWriter(System.out); 1646 1647 input(); 1648 solve(); 1649 1650 out.close(); 1651 } 1652 } 1653 ``` 1654 1655 **Solution (xuanquang1999, PyPy 3)** 1656 1657 Submission link: [69153968](/contest/1292/submission/69153968 "Submission 69153968 by AkiLotus") 1658 1659 **Source code in plain text** 1660 1661 ``` 1662 MOD = 1000000007 1663 1664 def isSubset(a, b): 1665 return (a & b) == a 1666 1667 def isIntersect(a, b): 1668 return (a & b) != 0 1669 1670 # Solve for each weakly connected component (WCC) 1671 def cntOrder(s, t): 1672 p = len(s) 1673 m = len(t) 1674 1675 inMask = [0 for i in range(m)] 1676 1677 for x in range(p): 1678 for i in range(m): 1679 if t[i] % s[x] == 0: 1680 inMask[i] |= 1 << x 1681 1682 cnt = [0 for mask in range(1<<p)] 1683 for mask in range(1<<p): 1684 for i in range(m): 1685 if isSubset(inMask[i], mask): 1686 cnt[mask] += 1 1687 1688 dp = [[0 for mask in range(1<<p)] for k in range(m+1)] 1689 for i in range(m): 1690 dp[1][inMask[i]] += 1 1691 for k in range(m): 1692 for mask in range(1<<p): 1693 for i in range(m): 1694 if not isSubset(inMask[i], mask) and isIntersect(inMask[i], mask): 1695 dp[k+1][mask | inMask[i]] = (dp[k+1][mask | inMask[i]] + dp[k][mask]) % MOD 1696 dp[k+1][mask] = (dp[k+1][mask] + dp[k][mask] * (cnt[mask] - k)) % MOD 1697 1698 return dp[m][(1<<p)-1] 1699 1700 def dfs(u): 1701 global a, graph, degIn, visited, s, t 1702 1703 visited[u] = True 1704 if degIn[u] == 0: 1705 s.append(a[u]) 1706 else: 1707 t.append(a[u]) 1708 1709 for v in graph[u]: 1710 if not visited[v]: 1711 dfs(v) 1712 1713 def main(): 1714 global a, graph, degIn, visited, s, t 1715 1716 # Reading input 1717 n = int(input()) 1718 a = list(map(int, input().split())) 1719 1720 # Pre-calculate C(n, k) 1721 c = [[0 for j in range(n)] for i in range(n)] 1722 for i in range(n): 1723 c[i][0] = 1 1724 for j in range(1, i+1): 1725 c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD 1726 1727 # Building divisibility graph 1728 degIn = [0 for u in range(n)] 1729 graph = [[] for u in range(n)] 1730 for u in range(n): 1731 for v in range(n): 1732 if u != v and a[v] % a[u] == 0: 1733 graph[u].append(v) 1734 graph[v].append(u) 1735 degIn[v] += 1 1736 1737 # Solve for each WCC of divisibility graph and combine result 1738 ans = 1 1739 curLen = 0 1740 visited = [False for u in range(n)] 1741 for u in range(n): 1742 if not visited[u]: 1743 s = [] 1744 t = [] 1745 dfs(u) 1746 1747 if len(t) > 0: 1748 sz = len(t) - 1 1749 cnt = cntOrder(s, t) 1750 1751 # Number of orders for current WCC 1752 ans = (ans * cnt) % MOD 1753 # Number of ways to insert <sz> number to array of <curLen> elements 1754 ans = (ans * c[curLen + sz][sz]) % MOD 1755 curLen += sz 1756 1757 print(ans) 1758 1759 if __name__ == "__main__": 1760 main() 1761 ```