2040.md (16470B)
1 Source: https://codeforces.com/blog/entry/137074 2 3 [2040A - Game of Division](/contest/2040/problem/A "Codeforces Round 992 (Div. 2)") 4 5 **Editorial** 6 7 Tutorial is loading... 8 9 **Solution C++** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 int tt; 18 cin >> tt; 19 while (tt--) { 20 int n, k; 21 cin >> n >> k; 22 vector < vector <int> > b(k); 23 for (int i = 1; i <= n; i++) { 24 int x; 25 cin >> x; 26 b[x % k].push_back(i); 27 } 28 int res = -1; 29 for (int i = 0; i < k; i++) { 30 if ((int)b[i].size() == 1) { 31 res = b[i][0]; 32 break; 33 } 34 } 35 if (res == -1) { 36 cout << "NO" << endl; 37 } 38 else { 39 cout << "YES" << endl << res << endl; 40 } 41 } 42 43 return 0; 44 } 45 ``` 46 47 **Solution Python** 48 49 ``` 50 for _ in range(int(input())): 51 n, k = map(int, input().split()) 52 a = list(map(int, input().split())) 53 b = [[] for _ in range(k)] 54 for i in range(0, n): 55 x = a[i] 56 b[x % k].append(i + 1) 57 res = -1 58 for i in range(k): 59 if len(b[i]) == 1: 60 res = b[i][0] 61 break 62 if res == -1: 63 print("NO") 64 else: 65 print("YES\n" + str(res)) 66 ``` 67 68 [2040B - Paint a Strip](/contest/2040/problem/B "Codeforces Round 992 (Div. 2)") 69 70 **Editorial** 71 72 Tutorial is loading... 73 74 **Solution C++** 75 76 ``` 77 #include <bits/stdc++.h> 78 79 using namespace std; 80 81 int main() { 82 int tt; 83 cin >> tt; 84 while (tt--) { 85 int n; 86 cin >> n; 87 for (int ans = 1, cur = 1; ; ans++, cur = cur * 2 + 2) { 88 if (cur >= n) { 89 cout << ans << '\n'; 90 break; 91 } 92 } 93 } 94 95 return 0; 96 } 97 ``` 98 99 **Solution Python** 100 101 ``` 102 tt = int(input()) 103 for _ in range(tt): 104 n = int(input()) 105 ans = 1 106 cur = 1 107 while True: 108 if cur >= n: 109 print(ans) 110 break 111 ans += 1 112 cur = cur * 2 + 2 113 ``` 114 115 **Notes** 116 117 At some point in the development of this problem, the following alternative statement appeared: we need to minimize the total number of operations of both types. How to solve this problem? 118 119 [2040C - Ordered Permutations](/contest/2040/problem/C "Codeforces Round 992 (Div. 2)") 120 121 **Editorial** 122 123 Tutorial is loading... 124 125 **Solution C++** 126 127 ``` 128 #include <bits/stdc++.h> 129 130 using namespace std; 131 132 int main() { 133 int tt; 134 cin >> tt; 135 while (tt--) { 136 int n; 137 long long k; 138 cin >> n >> k; 139 vector <int> a, b; 140 141 if (n <= 60 && (1ll << (n - 1)) < k) { 142 cout << -1 << endl; 143 continue; 144 } 145 k--; 146 vector <int> d; 147 while (k) { 148 d.push_back(k % 2); 149 k /= 2; 150 } 151 while (d.size() < n - 1) d.push_back(0); 152 153 for (int i = n - 2, j = 1; i >= 0; i--, j++) { 154 if (d[i] == 0) a.push_back(j); 155 else b.push_back(j); 156 } 157 158 reverse(b.begin(), b.end()); 159 for (int i : a) cout << i << ' '; 160 cout << n << ' '; 161 for (int i : b) cout << i << ' '; 162 cout << endl; 163 } 164 165 return 0; 166 } 167 ``` 168 169 **Solution Python** 170 171 ``` 172 tt = int(input()) 173 for _ in range(tt): 174 n, k = map(int, input().split()) 175 a, b = [], [] 176 177 if n <= 60 and (1 << (n - 1)) < k: 178 print(-1) 179 continue 180 k -= 1 181 d = [] 182 while k: 183 d.append(k % 2) 184 k //= 2 185 while len(d) < n - 1: 186 d.append(0) 187 188 a, b = [], [] 189 j = 1 190 for i in range(n - 2, -1, -1): 191 if d[i] == 0: 192 a.append(j) 193 else: 194 b.append(j) 195 j += 1 196 197 b.reverse() 198 print(*a, n, *b) 199 ``` 200 201 [2040D - Non Prime Tree](/contest/2040/problem/D "Codeforces Round 992 (Div. 2)") 202 203 **Editorial** 204 205 Tutorial is loading... 206 207 **Solution 1** 208 209 ``` 210 #include <bits/stdc++.h> 211 212 using namespace std; 213 214 int main() { 215 int tt; 216 cin >> tt; 217 while (tt--) { 218 int n; 219 cin >> n; 220 vector < vector <int> > g(n); 221 for (int i = 0; i < n - 1; i++) { 222 int a, b; 223 cin >> a >> b; 224 a--, b--; 225 g[a].push_back(b); 226 g[b].push_back(a); 227 } 228 229 vector <int> res(n); 230 int lst = 1; 231 res[0] = lst; 232 233 function <void(int, int)> dfs = [&](int v, int p) { 234 for (int to : g[v]) { 235 if (to == p) continue; 236 res[to] = lst + 1; 237 while (res[to] != res[v] + 1 && 238 (res[to] % 2 != res[v] % 2 || res[to] - res[v] == 2)) { 239 res[to]++; 240 } 241 lst = res[to]; 242 dfs(to, v); 243 } 244 }; 245 246 dfs(0, 0); 247 for (int i : res) cout << i << ' '; 248 cout << endl; 249 } 250 251 return 0; 252 } 253 ``` 254 255 **Solution 2 (zap4eg)** 256 257 ``` 258 #include <bits/stdc++.h> 259 using namespace std; 260 261 using ll = long long; 262 263 void dfs(int v, vector<vector<int>>& g, vector<int>& h, int p) { 264 h[v] = h[p] + 1; 265 for (int u : g[v]) { 266 if (u == p) 267 continue; 268 dfs(u, g, h, v); 269 } 270 } 271 272 int main() { 273 ios::sync_with_stdio(0); 274 cin.tie(0); 275 cout.tie(0); 276 277 int tt; 278 cin >> tt; 279 while (tt--) { 280 int n; 281 cin >> n; 282 vector<vector<int>> g(n); 283 for (int i = 0; i < n - 1; i++) { 284 int u, v; 285 cin >> u >> v; 286 u--, v--; 287 g[u].push_back(v); 288 g[v].push_back(u); 289 } 290 vector<int> h(n); 291 dfs(0, g, h, 0); 292 vector<vector<int>> hs(n + 1); 293 for (int i = 0; i < n; i++) 294 hs[h[i]].push_back(i); 295 int l = 2, r = 2 * n; 296 int cur = 0; 297 vector<int> ans(n); 298 for (int i = 1; i <= n; i++) { 299 if (cur) { 300 for (int v : hs[i]) { 301 ans[v] = r; 302 r -= 2; 303 } 304 } 305 else { 306 for (int v : hs[i]) { 307 ans[v] = l; 308 l += 2; 309 } 310 } 311 cur ^= 1; 312 } 313 bool found = false; 314 for (int i = 0; i < n; i++) { 315 for (int v : g[i]) { 316 if (h[v] < h[i]) 317 continue; 318 if (abs(ans[v] - ans[i]) == 2) { 319 ans[v] = ans[i] - 1; 320 found = true; 321 break; 322 } 323 } 324 if (found) 325 break; 326 } 327 for (int i = 0; i < n; i++) 328 cout << ans[i] << ' '; 329 cout << '\n'; 330 } 331 332 return 0; 333 } 334 ``` 335 336 **Notes** 337 338 There are many possible solutions to this problem, and almost all testers have implemented a unique solution. There are solutions that we could not prove correct, but we could not hack them either. 339 340 [2040E - Control of Randomness](/contest/2040/problem/E "Codeforces Round 992 (Div. 2)") 341 342 **Editorial** 343 344 Tutorial is loading... 345 346 **Solution** 347 348 ``` 349 #include <bits/stdc++.h> 350 351 using namespace std; 352 353 void solve() { 354 int n, q; 355 cin >> n >> q; 356 357 vector < vector <int> > g(n); 358 for (int i = 0; i < n - 1; i++) { 359 int u, v; 360 cin >> u >> v; 361 u--, v--; 362 g[u].push_back(v); 363 g[v].push_back(u); 364 } 365 366 vector <int> depth(n); 367 vector <int> d(n); 368 vector <int> par(n); 369 370 function <void(int, int)> dfs = [&](int v, int p) { 371 if (depth[v] == 1) d[v] = 1; 372 if (depth[v] > 1) d[v] = d[par[p]] + 2 * (int)g[p].size(); 373 par[v] = p; 374 for(int to : g[v]) { 375 if (to == p) continue; 376 depth[to] = depth[v] + 1; 377 dfs(to, v); 378 } 379 }; 380 381 dfs(0, 0); 382 383 while (q--) { 384 int v, p; 385 cin >> v >> p; 386 v--; 387 int res = d[v]; 388 vector <int> cnt; 389 while (v != 0 && par[v] != 0) { 390 cnt.push_back((int)g[par[v]].size()); 391 v = par[par[v]]; 392 } 393 sort(cnt.rbegin(), cnt.rend()); 394 for (int i = 0; i < min(p, (int)cnt.size()); i++) { 395 res -= 2 * (cnt[i] - 1); 396 } 397 cout << res << '\n'; 398 } 399 } 400 401 int main() { 402 int tt; 403 cin >> tt; 404 while (tt--) { 405 solve(); 406 } 407 408 return 0; 409 } 410 ``` 411 412 **Solution (Notes)** 413 414 ``` 415 #include <bits/stdc++.h> 416 417 using namespace std; 418 419 void solve() { 420 int n, q; 421 cin >> n >> q; 422 423 vector < vector <int> > g(n); 424 for (int i = 0; i < n - 1; i++) { 425 int u, v; 426 cin >> u >> v; 427 u--, v--; 428 g[u].push_back(v); 429 g[v].push_back(u); 430 } 431 432 vector <int> depth(n); 433 vector <int> d(n); 434 vector < vector < pair <int,int> > > qrs(n); // <p, idx> 435 vector <int> res(q); 436 437 for (int i = 0; i < q; i++) { 438 int v, p; 439 cin >> v >> p; 440 v--; 441 qrs[v].push_back({p, i}); 442 } 443 444 multiset <int> st[2]; // store negative number to be able to use usual foreach loop 445 446 function <void(int, int, int)> dfs = [&](int v, int p, int pp) { 447 if (depth[v] == 1) d[v] = 1; 448 if (depth[v] > 1) d[v] = d[pp] + 2 * (int)g[p].size(); 449 450 for (pair <int, int> qr : qrs[v]) { 451 int p = qr.first, idx = qr.second; 452 int ans = d[v]; 453 for (int i : st[1 - depth[v] % 2]) { 454 if (p == 0) break; 455 ans -= (-i - 1) * 2; 456 p--; 457 } 458 res[idx] = ans; 459 } 460 461 if (depth[v] != 0) st[depth[v] % 2].insert(-(int)g[v].size()); 462 463 for (int to : g[v]) { 464 if (to == p) continue; 465 depth[to] = depth[v] + 1; 466 dfs(to, v, p); 467 } 468 469 if (depth[v] != 0) st[depth[v] % 2].erase(st[depth[v] % 2].find(-(int)g[v].size())); 470 }; 471 472 dfs(0, 0, 0); 473 474 for (int i = 0; i < q; i++) 475 cout << res[i] << '\n'; 476 } 477 478 int main() { 479 int tt; 480 cin >> tt; 481 while (tt--) { 482 solve(); 483 } 484 485 return 0; 486 } 487 ``` 488 489 **Notes** 490 491 This problem originally had the following constraints: 492 493 1. $1 \le n, q \le 2 \cdot 10^5$ 494 2. The sum of $p$ in all queries is not greater than $2 \cdot 10^5$ 495 496 How to solve this problem? 497 498 Could you solve this problem without the second constraint? 499 500 **Hint** 501 502 However, it is not hard thanks to a recent [blog](https://codeforces.com/blog/entry/136858). 503 504 [2040F - Number of Cubes](/contest/2040/problem/F "Codeforces Round 992 (Div. 2)") 505 506 **Editorial** 507 508 Tutorial is loading... 509 510 **Solution Phi** 511 512 ``` 513 #include <bits/stdc++.h> 514 #define int long long 515 516 using namespace std; 517 518 const int N = 3000010; 519 const int mod = 998244353; 520 int fact[N], ifact[N], phi[N]; 521 522 int powmod(int a, int n) { 523 int res = 1; 524 while (n) { 525 if (n % 2 == 0) { 526 a = (a * a) % mod; 527 n /= 2; 528 } 529 else { 530 res = (res * a) % mod; 531 n--; 532 } 533 } 534 return res; 535 } 536 537 int inv(int a) { 538 return powmod(a, mod - 2); 539 } 540 541 void prepare() { 542 fact[0] = 1; 543 for (int i = 1; i < N; i++) { 544 fact[i] = (fact[i - 1] * i) % mod; 545 } 546 ifact[N - 1] = inv(fact[N - 1]); 547 for (int i = N - 2; i >= 0; i--) { 548 ifact[i] = (ifact[i + 1] * (i + 1)) % mod; 549 } 550 551 phi[0] = 0; 552 phi[1] = 1; 553 for (int i = 2; i < N; i++) { 554 phi[i] = i - 1; 555 } 556 for (int i = 2; i < N; i++) { 557 for (int j = i * 2; j < N; j += i) { 558 phi[j] -= phi[i]; 559 } 560 } 561 } 562 563 int C(int n, int k) { 564 return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod; 565 } 566 567 int MC(vector <int> &a) { 568 int sum=0; 569 for (int i : a) sum += i; 570 int res = fact[sum]; 571 for (int i : a) { 572 res = (res * ifact[i]) % mod; 573 } 574 return res; 575 } 576 577 int lcm(int a, int b) { 578 return a / __gcd(a, b) * b; 579 } 580 581 vector <int> all_divs(int x) { 582 vector <int> d; 583 for (int i = 1; i * i <= x; i++) { 584 if (x % i == 0) { 585 d.push_back(i); 586 if (i * i != x) { 587 d.push_back(x / i); 588 } 589 } 590 } 591 return d; 592 } 593 594 void solve() { 595 int a, b, c, k; 596 cin >> a >> b >> c >> k; 597 vector <int> v(k); 598 for (int &i : v) cin >> i; 599 600 int g = v[0]; 601 for (int i : v) g = __gcd(g, i); 602 603 map <int, int> mp; 604 for (int i : all_divs(a)) { 605 for (int j : all_divs(b)) { 606 for (int l : all_divs(c)) { 607 int N = lcm(i, lcm(j, l)); 608 if (g % N == 0) { 609 mp[N] += phi[i] * phi[j] * phi[l]; 610 } 611 } 612 } 613 } 614 615 int sum = 0; 616 for (pair <int, int> pr : mp) { 617 int N = pr.first, cnt = pr.second; 618 vector <int> u; 619 for (int t : v) u.push_back(t / N); 620 sum = (sum + (MC(u) * cnt) % mod) % mod; 621 } 622 623 sum = (sum * inv(a * b * c)) % mod; 624 625 cout << sum << endl; 626 } 627 628 int32_t main() { 629 prepare(); 630 631 int tt; 632 cin >> tt; 633 while (tt--) { 634 solve(); 635 } 636 637 return 0; 638 } 639 ``` 640 641 **Solution DP** 642 643 ``` 644 #include <bits/stdc++.h> 645 #define int long long 646 647 using namespace std; 648 649 const int N = 3000010; 650 const int mod = 998244353; 651 int fact[N], ifact[N]; 652 int pos[N]; 653 654 int powmod(int a, int n) { 655 int res = 1; 656 while (n) { 657 if (n % 2 == 0) { 658 a = (a * a) % mod; 659 n /= 2; 660 } 661 else { 662 res = (res * a) % mod; 663 n--; 664 } 665 } 666 return res; 667 } 668 669 int inv(int a) { 670 return powmod(a, mod - 2); 671 } 672 673 void prepare() { 674 fact[0] = 1; 675 for (int i = 1;i < N; i++) { 676 fact[i] = (fact[i - 1] * i) % mod; 677 } 678 ifact[N - 1] = inv(fact[N - 1]); 679 for (int i = N - 2; i >= 0; i--) { 680 ifact[i] = (ifact[i + 1] * (i + 1)) % mod; 681 } 682 } 683 684 int C(int n, int k) { 685 return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod; 686 } 687 688 int MC(vector <int> &a) { 689 int sum=0; 690 for (int i : a) sum += i; 691 int res = fact[sum]; 692 for (int i : a) { 693 res = (res * ifact[i]) % mod; 694 } 695 return res; 696 } 697 698 int lcm(int a, int b) { 699 return a / __gcd(a, b) * b; 700 } 701 702 vector <int> all_divs(int x) { 703 vector <int> d1, d2; 704 for (int i = 1; i * i <= x; i++) { 705 if (x % i == 0) { 706 d1.push_back(i); 707 if (i * i != x) { 708 d2.push_back(x / i); 709 } 710 } 711 } 712 reverse(d2.begin(), d2.end()); 713 for (int i : d2) d1.push_back(i); 714 return d1; 715 } 716 717 void solve() { 718 int a, b, c, k; 719 cin >> a >> b >> c >> k; 720 vector <int> v(k); 721 for (int &i : v) cin >> i; 722 723 int g = v[0]; 724 for (int i : v) g = __gcd(g, i); 725 vector <int> divs_g = all_divs(g); 726 727 set <int> divs; 728 for (int i : all_divs(a)) divs.insert(i); 729 for (int i : all_divs(b)) divs.insert(i); 730 for (int i : all_divs(c)) divs.insert(i); 731 for (int i : all_divs(g)) divs.insert(i); 732 int D = divs.size(); 733 int i = 0; 734 for (int j : divs) { 735 pos[j] = i; 736 i++; 737 } 738 739 int n = max({a, b, c}) + 1; 740 vector < vector <int> > tmp(3, vector <int> (D)); 741 vector < vector <int> > cnt(3, vector <int> (D)); 742 for (int t = 0; t < 3; t++) { 743 int x; 744 if (t == 0) x = a; 745 if (t == 1) x = b; 746 if (t == 2) x = c; 747 vector <int> divs_x = all_divs(x); 748 749 for (int i = (int)divs_x.size() - 1; i >= 0; i--) { 750 tmp[t][pos[divs_x[i]]] += x / divs_x[i]; 751 for (int j = 0; j < i; j++) { 752 if (divs_x[i] % divs_x[j] == 0) { 753 tmp[t][pos[divs_x[j]]] -= tmp[t][pos[divs_x[i]]]; 754 } 755 } 756 cnt[t][pos[x / divs_x[i]]] = tmp[t][pos[divs_x[i]]]; 757 } 758 } 759 760 vector < vector <int> > dp(4, vector <int> (D)); 761 dp[0][0] = 1; 762 for(int i = 0; i < 3; i++) { 763 for (int t1 : divs_g) { 764 for (int t2 : divs_g) { 765 int new_pos = lcm(t1, t2); 766 if (t2 < n) { 767 dp[i + 1][pos[new_pos]] = (dp[i + 1][pos[new_pos]] + dp[i][pos[t1]] * cnt[i][pos[t2]]) % mod; 768 } 769 } 770 } 771 } 772 773 int sum = 0; 774 i = 0; 775 for (int j : divs) { 776 if (g % j != 0) continue; 777 int N = j, cnt = dp[3][pos[j]]; 778 vector <int> u; 779 for (int t : v) u.push_back(t / N); 780 sum = (sum + (MC(u) * cnt) % mod) % mod; 781 } 782 783 sum = (sum * inv(a * b * c)) % mod; 784 785 cout << sum << endl; 786 } 787 788 int32_t main() { 789 prepare(); 790 791 int tt; 792 cin >> tt; 793 while (tt--) { 794 solve(); 795 } 796 797 return 0; 798 } 799 ```