1553.md (25022B)
1 Source: https://codeforces.com/blog/entry/93105 2 3 Hope you all enjoyed the problemset! Editorials to problems H and I are not ready yet, we will add them as soon as possible. We apologize for weak pretests and easy problems for top participants. 4 5 By the way, solution authors did not necessarily prepare the problems. The solutions were chosen at random. 6 7 **UPD.** Editorials for H and I are ready! Wish you all productive upsolving and high ratings! 8 9 [1553A - Digits Sum](/contest/1553/problem/A) 10 11 Idea: [bthero](/profile/bthero "International Master bthero") Preparation: [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq") 12 13 **Tutorial** 14 15 Tutorial is loading... 16 17 **Solution (kefaa2)** 18 19 ``` 20 #include <bits/stdc++.h> 21 22 using namespace std; 23 typedef long long ll; 24 int main() { 25 //freopen("input.txt", "r", stdin); 26 ios_base::sync_with_stdio(false); 27 int tst; 28 cin >> tst; 29 while (tst--) { 30 int n; 31 cin >> n; 32 cout << (n + 1) / 10 << '\n'; 33 } 34 } 35 ``` 36 37 [1553B - Reverse String](/contest/1553/problem/B) 38 39 Idea: [Errichto](/profile/Errichto "Legendary Grandmaster Errichto") Preparation: Will not be revealed for now because we care for his/their safety. 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution (BledDest)** 46 47 ``` 48 q = int(input()) 49 for i in range(q): 50 s = input() 51 t = input() 52 n = len(s) 53 m = len(t) 54 ans = False 55 for i in range(n): 56 for j in range(0, n - i): 57 k = m - 1 - j 58 if i + j < k: 59 continue 60 l1 = i 61 r = i + j 62 l2 = r - k 63 if s[l1:r+1] + s[l2:r][::-1] == t: 64 ans = True 65 print('YES' if ans else 'NO') 66 ``` 67 68 [1553C - Penalty](/contest/1553/problem/C) 69 70 Idea: [Errichto](/profile/Errichto "Legendary Grandmaster Errichto") Preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 71 72 **Tutorial** 73 74 Tutorial is loading... 75 76 **Solution (BledDest)** 77 78 ``` 79 #include <bits/stdc++.h> 80 81 using namespace std; 82 83 int main() { 84 int t; 85 cin >> t; 86 while (t--) { 87 string s; 88 cin >> s; 89 int ans = 9; 90 91 { 92 int cnt0 = 0, cnt1 = 0; 93 for (int i = 0; i < 10; ++i) { 94 if (i % 2 == 0) cnt0 += s[i] != '0'; 95 else cnt1 += s[i] == '1'; 96 if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i); 97 if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i); 98 } 99 } 100 101 { 102 int cnt0 = 0, cnt1 = 0; 103 for (int i = 0; i < 10; ++i) { 104 if (i % 2 == 0) cnt0 += s[i] == '1'; 105 else cnt1 += s[i] != '0'; 106 if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i); 107 if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i); 108 } 109 } 110 111 cout << ans + 1 << '\n'; 112 } 113 } 114 ``` 115 116 [1553D - Backspace](/contest/1553/problem/D) 117 118 Idea: [Adel_SaadEddin](/profile/Adel_SaadEddin "Candidate Master Adel_SaadEddin"), [Zaher](/profile/Zaher "Master Zaher") Preparation: Will not be revealed for now because we care for his/their safety. 119 120 **Tutorial** 121 122 Tutorial is loading... 123 124 **Solution (Um_nik)** 125 126 ``` 127 #include <iostream> 128 #include <cstdio> 129 #include <cstdlib> 130 #include <algorithm> 131 #include <cmath> 132 #include <vector> 133 #include <set> 134 #include <map> 135 #include <unordered_set> 136 #include <unordered_map> 137 #include <queue> 138 #include <ctime> 139 #include <cassert> 140 #include <complex> 141 #include <string> 142 #include <cstring> 143 #include <chrono> 144 #include <random> 145 #include <bitset> 146 using namespace std; 147 148 #ifdef LOCAL 149 #define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr); 150 #else 151 #define eprintf(...) 42 152 #endif 153 154 using ll = long long; 155 using ld = long double; 156 using uint = unsigned int; 157 using ull = unsigned long long; 158 template<typename T> 159 using pair2 = pair<T, T>; 160 using pii = pair<int, int>; 161 using pli = pair<ll, int>; 162 using pll = pair<ll, ll>; 163 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 164 ll myRand(ll B) { 165 return (ull)rng() % B; 166 } 167 168 #define pb push_back 169 #define mp make_pair 170 #define all(x) (x).begin(),(x).end() 171 #define fi first 172 #define se second 173 174 clock_t startTime; 175 double getCurrentTime() { 176 return (double)(clock() - startTime) / CLOCKS_PER_SEC; 177 } 178 179 const int N = 200200; 180 int n, m; 181 char s[N], t[N]; 182 183 bool solve() { 184 scanf("%s %s", s, t); 185 n = strlen(s); 186 m = strlen(t); 187 if (n < m) return false; 188 int p = (n - m) & 1; 189 int q = 0; 190 int k = 0; 191 for (int i = p; i < n; i++) { 192 if (k == 1) { 193 k = 0; 194 continue; 195 } 196 if (q < m && s[i] == t[q]) { 197 q++; 198 } else { 199 k++; 200 } 201 } 202 return q == m; 203 } 204 205 int main() 206 { 207 startTime = clock(); 208 // freopen("input.txt", "r", stdin); 209 // freopen("output.txt", "w", stdout); 210 211 int T; 212 scanf("%d", &T); 213 while(T--) { 214 if (solve()) 215 printf("YES\n"); 216 else 217 printf("NO\n"); 218 } 219 220 return 0; 221 } 222 ``` 223 224 [1553E - Permutation Shift](/contest/1553/problem/E) 225 226 Idea: [bthero](/profile/bthero "International Master bthero"), [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq") Preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 227 228 **Tutorial** 229 230 Tutorial is loading... 231 232 **Solution (BledDest)** 233 234 ``` 235 #include <bits/stdc++.h> 236 237 using namespace std; 238 239 int cycle_count(vector<int> q, int n) 240 { 241 for(int i = 0; i < n; i++) 242 q[i]--; 243 vector<int> used(n); 244 int ans = 0; 245 for(int i = 0; i < n; i++) 246 { 247 if(used[i] == 1) continue; 248 int j = i; 249 while(used[j] == 0) 250 { 251 used[j] = 1; 252 j = q[j]; 253 } 254 ans++; 255 } 256 return ans; 257 } 258 259 bool check(int n, int m, int k, vector<int> p) 260 { 261 vector<int> q; 262 for(int i = k; i < n; i++) 263 q.push_back(p[i]); 264 for(int i = 0; i < k; i++) 265 q.push_back(p[i]); 266 return n - cycle_count(q, n) <= m; 267 } 268 269 void solve() 270 { 271 int n, m; 272 scanf("%d %d", &n, &m); 273 vector<int> p(n); 274 for(int i = 0; i < n; i++) 275 scanf("%d", &p[i]); 276 vector<int> cnt(n); 277 for(int i = 0; i < n; i++) 278 { 279 int offset = i + 1 - p[i]; 280 if(offset < 0) 281 offset += n; 282 cnt[offset]++; 283 } 284 vector<int> ans; 285 for(int i = 0; i < n; i++) 286 if(cnt[i] + 2 * m >= n && check(n, m, i, p)) 287 ans.push_back(i); 288 printf("%d", ans.size()); 289 for(auto x : ans) printf(" %d", x); 290 puts(""); 291 292 } 293 294 int main() 295 { 296 int t; 297 scanf("%d", &t); 298 for(int i = 0; i < t; i++) 299 { 300 solve(); 301 } 302 } 303 ``` 304 305 [1553F - Pairwise Modulo](/contest/1553/problem/F) 306 307 Idea: [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq"), [Errichto](/profile/Errichto "Legendary Grandmaster Errichto") Preparation: [bthero](/profile/bthero "International Master bthero") 308 309 **Tutorial** 310 311 Tutorial is loading... 312 313 **Solution (bthero)** 314 315 ``` 316 // chrono::system_clock::now().time_since_epoch().count() 317 #include <bits/stdc++.h> 318 319 using namespace std; 320 321 typedef long long ll; 322 323 template<int N> struct Fenw { 324 ll t[N + 1]; 325 326 Fenw() { 327 fill(t + 1, t + N + 1, 0ll); 328 } 329 330 void update(int p, ll x) { 331 for (; p <= N; p |= (p + 1)) { 332 t[p] += x; 333 } 334 } 335 336 ll get(int p) { 337 ll ret = 0; 338 339 for (; p > 0; --p) { 340 ret += t[p]; 341 p &= (p + 1); 342 } 343 344 return ret; 345 } 346 347 ll get(int l, int r) { 348 return get(r) - get(l - 1); 349 } 350 }; 351 352 const int M = (int)3e5; 353 354 void solve() { 355 int n; 356 cin >> n; 357 Fenw<M> A, B; 358 ll pref = 0, ans = 0; 359 360 for (int i = 1; i <= n; ++i) { 361 int x; 362 cin >> x; 363 ans += x * (i - 1ll); 364 ans += A.get(x); 365 ans += pref; 366 pref += x; 367 368 for (int j = x; j <= M; j += x) { 369 int l = j, r = min(M, j + x - 1); 370 ans -= B.get(l, r) * j; 371 A.update(l, -x); 372 } 373 374 B.update(x, 1); 375 cout << ans << " \n"[i == n]; 376 } 377 } 378 379 int main() { 380 ios_base::sync_with_stdio(0); 381 cin.tie(0); 382 cout.tie(0); 383 384 int tt = 1; 385 386 for (int i = 1; i <= tt; ++i) { 387 solve(); 388 } 389 390 return 0; 391 } 392 ``` 393 394 **Segment tree solution (bthero)** 395 396 ``` 397 // chrono::system_clock::now().time_since_epoch().count() 398 #include <bits/stdc++.h> 399 400 #define pb push_back 401 #define eb emplace_back 402 #define mp make_pair 403 #define fi first 404 #define se second 405 #define all(x) (x).begin(), (x).end() 406 #define sz(x) (int)(x).size() 407 #define rep(i, a, b) for (int i = (a); i < (b); ++i) 408 #define debug(x) cerr << #x << " = " << x << endl 409 410 using namespace std; 411 412 typedef long long ll; 413 typedef pair<int, int> pii; 414 typedef vector<int> vi; 415 416 const int M = (int)3e5; 417 418 namespace A { 419 ll t[M * 4]; 420 421 void update(int l, int r, ll x, int v = 1, int tl = 1, int tr = M) { 422 if (l > r || tl > r || tr < l) { 423 return; 424 } 425 426 if (l <= tl && tr <= r) { 427 t[v] += x; 428 return; 429 } 430 431 int mid = (tl + tr) >> 1; 432 int c1 = (v << 1), c2 = (c1 | 1); 433 434 update(l, r, x, c1, tl, mid); 435 update(l, r, x, c2, mid + 1, tr); 436 } 437 438 ll get(int p, int v = 1, int tl = 1, int tr = M) { 439 if (tl == tr) { 440 return t[v]; 441 } 442 443 int mid = (tl + tr) >> 1; 444 int c1 = (v << 1), c2 = (c1 | 1); 445 446 if (p <= mid) { 447 return t[v] + get(p, c1, tl, mid); 448 } 449 else { 450 return t[v] + get(p, c2, mid + 1, tr); 451 } 452 } 453 } 454 455 namespace B { 456 ll t[M * 4]; 457 458 void update(int p, ll x, int v = 1, int tl = 1, int tr = M) { 459 if (tl == tr) { 460 t[v] += x; 461 return; 462 } 463 464 int mid = (tl + tr) >> 1; 465 int c1 = (v << 1), c2 = (c1 | 1); 466 467 if (p <= mid) { 468 update(p, x, c1, tl, mid); 469 } 470 else { 471 update(p, x, c2, mid + 1, tr); 472 } 473 474 t[v] = t[c1] + t[c2]; 475 } 476 477 ll get(int l, int r, int v = 1, int tl = 1, int tr = M) { 478 if (l > r || tl > r || tr < l) { 479 return 0ll; 480 } 481 482 if (l <= tl && tr <= r) { 483 return t[v]; 484 } 485 486 int mid = (tl + tr) >> 1; 487 int c1 = (v << 1), c2 = (c1 | 1); 488 489 return get(l, r, c1, tl, mid) + get(l, r, c2, mid + 1, tr); 490 } 491 } 492 493 int n; 494 495 void solve() { 496 cin >> n; 497 ll pref = 0, ans = 0; 498 499 rep (i, 1, n + 1) { 500 int x; 501 cin >> x; 502 ans += x * (i - 1ll); 503 ans += A::get(x); 504 ans += pref; 505 pref += x; 506 507 for (int j = x; j <= M; j += x) { 508 int l = j, r = min(M, j + x - 1); 509 ans -= x * B::get(l, r) * (j / x); 510 A::update(l, r, -x * (j / x)); 511 } 512 513 B::update(x, 1); 514 cout << ans << " \n"[i == n]; 515 } 516 } 517 518 int main() { 519 ios_base::sync_with_stdio(0); 520 cin.tie(0); 521 cout.tie(0); 522 523 int tt = 1; 524 525 for (int i = 1; i <= tt; ++i) { 526 solve(); 527 } 528 529 return 0; 530 } 531 ``` 532 533 [1553G - Common Divisor Graph](/contest/1553/problem/G) 534 535 Idea: [Adel_SaadEddin](/profile/Adel_SaadEddin "Candidate Master Adel_SaadEddin"), [Zaher](/profile/Zaher "Master Zaher"), [Errichto](/profile/Errichto "Legendary Grandmaster Errichto") Preparation: [Errichto](/profile/Errichto "Legendary Grandmaster Errichto") 536 537 **Tutorial** 538 539 Tutorial is loading... 540 541 **Solution (Errichto)** 542 543 ``` 544 // gcd, AC, O((N+Q) * log^2), by Errichto 545 #include <bits/stdc++.h> 546 using namespace std; 547 #define sim template < class c 548 #define ris return * this 549 #define dor > debug & operator << 550 #define eni(x) sim > typename \ 551 enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { 552 sim > struct rge { c b, e; }; 553 sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } 554 sim > auto dud(c* x) -> decltype(cerr << *x, 0); 555 sim > char dud(...); 556 struct debug { 557 #ifdef LOCAL 558 ~debug() { cerr << endl; } 559 eni(!=) cerr << boolalpha << i; ris; } 560 eni(==) ris << range(begin(i), end(i)); } 561 sim, class b dor(pair < b, c > d) { 562 ris << "(" << d.first << ", " << d.second << ")"; 563 } 564 sim dor(rge<c> d) { 565 *this << "["; 566 for (auto it = d.b; it != d.e; ++it) 567 *this << ", " + 2 * (it == d.b) << *it; 568 ris << "]"; 569 } 570 #else 571 sim dor(const c&) { ris; } 572 #endif 573 }; 574 #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " 575 // debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; } 576 577 struct DSU { 578 vector<int> parent; 579 DSU(int m) { 580 parent.resize(m + 1); 581 for(int i = 0; i <= m; ++i) { 582 parent[i] = i; 583 } 584 } 585 int find(int a) { 586 if(a == parent[a]) { 587 return a; 588 } 589 return parent[a] = find(parent[a]); 590 } 591 void uni(int a, int b) { 592 parent[find(a)] = find(b); 593 } 594 }; 595 596 int main() { 597 // 1) read input 598 int n, q; 599 scanf("%d%d", &n, &q); 600 vector<int> a(n); 601 for(int i = 0; i < n; ++i) { 602 scanf("%d", &a[i]); 603 } 604 int m = *max_element(a.begin(), a.end()); 605 // 2) prime sieve 606 vector<vector<int>> prime_divisors(m + 2); 607 for(int p = 2; p <= m + 1; ++p) { 608 if(prime_divisors[p].empty()) { 609 for(int j = p; j <= m + 1; j += p) { 610 prime_divisors[j].push_back(p); 611 } 612 } 613 } 614 // 3) DSU, find initial connected components 615 DSU dsu(m + 2); 616 for(int x : a) { 617 for(int p : prime_divisors[x]) { 618 dsu.uni(x, p); 619 } 620 } 621 // 4) DSU, find edges of cost 1 622 set<pair<int,int>> edges; 623 for(int x : a) { 624 vector<int> nodes = prime_divisors[x+1]; 625 nodes.push_back(x); 626 for(int& node : nodes) { 627 node = dsu.find(node); 628 } 629 for(int i = 0; i < (int) nodes.size(); ++i) { 630 for(int j = i + 1; j < (int) nodes.size(); ++j) { 631 int one = nodes[i]; 632 int two = nodes[j]; 633 if(one != two) { 634 if(one > two) { 635 swap(one, two); 636 } 637 edges.insert({one, two}); 638 } 639 } 640 } 641 } 642 debug() << imie(edges); 643 cerr << imie(edges.size()) << endl; 644 // 5) answer queries 645 while(q--) { 646 int s, t; 647 scanf("%d%d", &s, &t); 648 --s; 649 --t; 650 s = dsu.find(a[s]); 651 t = dsu.find(a[t]); 652 if(s == t) { 653 puts("0"); 654 } 655 else if(edges.count({min(s, t), max(s, t)})) { 656 puts("1"); 657 } 658 else { 659 puts("2"); 660 } 661 } 662 } 663 ``` 664 665 [1553H - XOR and Distance](/contest/1553/problem/H) 666 667 Idea: [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq") Preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest"), [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr"), [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq") 668 669 **Tutorial** 670 671 Tutorial is loading... 672 673 **Solution (BledDest)** 674 675 ``` 676 #include<bits/stdc++.h> 677 678 using namespace std; 679 680 const int INF = int(1e9); 681 const int K = 20; 682 683 struct node 684 { 685 int max_val, min_val, ans, len; 686 node* left; 687 node* right; 688 689 void recalc() 690 { 691 len = left->len + right->len; 692 max_val = max(left->max_val, right->max_val + left->len); 693 min_val = min(left->min_val, right->min_val + left->len); 694 ans = min(min(left->ans, right->ans), min(INF, right->min_val - left->max_val + left->len)); 695 } 696 697 node(int x) 698 { 699 ans = INF; 700 len = 1; 701 if(x == 1) 702 max_val = min_val = 0; 703 else 704 { 705 max_val = -INF; 706 min_val = INF; 707 } 708 } 709 710 node(node* l, node* r) 711 { 712 left = l; 713 right = r; 714 recalc(); 715 } 716 717 node() {}; 718 }; 719 720 int cnt[1 << K]; 721 node tree[2 << K]; 722 723 int n, k, m; 724 725 void build(int v, int l, int r) 726 { 727 if(l == r - 1) 728 tree[v] = node(cnt[l]); 729 else 730 { 731 int m = (l + r) / 2; 732 build(v * 2 + 1, l, m); 733 build(v * 2 + 2, m, r); 734 tree[v] = node(&tree[v * 2 + 1], &tree[v * 2 + 2]); 735 } 736 //cerr << v << " " << l << " " << r << " " << tree[v].min_val << " " << tree[v].max_val << " " << tree[v].len << " " << tree[v].ans << endl; 737 } 738 739 void swap_segments(node* v, int d) 740 { 741 if(d == 0) 742 { 743 swap(v->left, v->right); 744 v->recalc(); 745 } 746 else 747 { 748 swap_segments(v->left, d - 1); 749 swap_segments(v->right, d - 1); 750 v->recalc(); 751 } 752 //cerr << v->min_val << " " << v->max_val << " " << v->len << " " << v->ans << endl; 753 } 754 755 int res[1 << K]; 756 757 int cur = 0; 758 759 void rec(int x) 760 { 761 if(x == 0) 762 res[cur] = tree[0].ans; 763 else 764 rec(x - 1); 765 swap_segments(&tree[0], x); 766 cur ^= (1 << (k - x - 1)); 767 if(x == 0) 768 res[cur] = tree[0].ans; 769 else 770 rec(x - 1); 771 } 772 773 int main() 774 { 775 scanf("%d %d", &n, &k); 776 for(int i = 0; i < n; i++) 777 { 778 int x; 779 scanf("%d", &x); 780 cnt[x]++; 781 } 782 m = 1 << k; 783 build(0, 0, m); 784 rec(k - 1); 785 for(int i = 0; i < m; i++) 786 printf("%d ", res[i]); 787 puts(""); 788 } 789 ``` 790 791 **Alternative solution (BledDest)** 792 793 ``` 794 #include<bits/stdc++.h> 795 796 using namespace std; 797 798 const int INF = int(1e9); 799 const int K = 20; 800 801 struct node 802 { 803 int max_val, min_val, ans, len; 804 805 node(const node& left, const node& right) 806 { 807 len = left.len + right.len; 808 max_val = max(left.max_val, right.max_val + left.len); 809 min_val = min(left.min_val, right.min_val + left.len); 810 ans = min(min(left.ans, right.ans), min(INF, right.min_val - left.max_val + left.len)); 811 } 812 813 node(int x) 814 { 815 ans = INF; 816 len = 1; 817 if(x == 1) 818 max_val = min_val = 0; 819 else 820 { 821 max_val = -INF; 822 min_val = INF; 823 } 824 } 825 826 node() {}; 827 }; 828 829 int cnt[1 << K]; 830 vector<node> tree[2 << K]; 831 832 void build(int v, int l, int r) 833 { 834 tree[v].resize(r - l); 835 if(l == r - 1) 836 { 837 tree[v][0] = node(cnt[l]); 838 } 839 else 840 { 841 int m = (l + r) / 2; 842 build(v * 2 + 1, l, m); 843 build(v * 2 + 2, m, r); 844 for(int i = 0; i < m - l; i++) 845 { 846 tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]); 847 tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]); 848 } 849 } 850 } 851 852 int main() 853 { 854 int n, k; 855 scanf("%d %d", &n, &k); 856 for(int i = 0; i < n; i++) 857 { 858 int x; 859 scanf("%d", &x); 860 cnt[x]++; 861 } 862 int m = 1 << k; 863 build(0, 0, m); 864 for(int i = 0; i < m; i++) 865 printf("%d ", tree[0][i].ans); 866 puts(""); 867 } 868 ``` 869 870 [1553I - Stairs](/contest/1553/problem/I) 871 872 Idea: [bthero](/profile/bthero "International Master bthero"), [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq"), [BledDest](/profile/BledDest "International Grandmaster BledDest") Preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest"), [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq") 873 874 **Tutorial** 875 876 Tutorial is loading... 877 878 **Solution (BledDest)** 879 880 ``` 881 #include<bits/stdc++.h> 882 883 using namespace std; 884 885 #define forn(i, n) for(int i = 0; i < int(n); i++) 886 #define sz(a) ((int)((a).size())) 887 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 888 889 template<const int &MOD> 890 struct _m_int { 891 int val; 892 893 _m_int(int64_t v = 0) { 894 if (v < 0) v = v % MOD + MOD; 895 if (v >= MOD) v %= MOD; 896 val = int(v); 897 } 898 899 _m_int(uint64_t v) { 900 if (v >= MOD) v %= MOD; 901 val = int(v); 902 } 903 904 _m_int(int v) : _m_int(int64_t(v)) {} 905 _m_int(unsigned v) : _m_int(uint64_t(v)) {} 906 907 static int inv_mod(int a, int m = MOD) { 908 int g = m, r = a, x = 0, y = 1; 909 910 while (r != 0) { 911 int q = g / r; 912 g %= r; swap(g, r); 913 x -= q * y; swap(x, y); 914 } 915 916 return x < 0 ? x + m : x; 917 } 918 919 explicit operator int() const { return val; } 920 explicit operator unsigned() const { return val; } 921 explicit operator int64_t() const { return val; } 922 explicit operator uint64_t() const { return val; } 923 explicit operator double() const { return val; } 924 explicit operator long double() const { return val; } 925 926 _m_int& operator+=(const _m_int &other) { 927 val -= MOD - other.val; 928 if (val < 0) val += MOD; 929 return *this; 930 } 931 932 _m_int& operator-=(const _m_int &other) { 933 val -= other.val; 934 if (val < 0) val += MOD; 935 return *this; 936 } 937 938 static unsigned fast_mod(uint64_t x, unsigned m = MOD) { 939 #if !defined(_WIN32) || defined(_WIN64) 940 return unsigned(x % m); 941 #endif 942 // Optimized mod for Codeforces 32-bit machines. 943 // x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int. 944 unsigned x_high = unsigned(x >> 32), x_low = unsigned(x); 945 unsigned quot, rem; 946 asm("divl %4\n" 947 : "=a" (quot), "=d" (rem) 948 : "d" (x_high), "a" (x_low), "r" (m)); 949 return rem; 950 } 951 952 _m_int& operator*=(const _m_int &other) { 953 val = fast_mod(uint64_t(val) * other.val); 954 return *this; 955 } 956 957 _m_int& operator/=(const _m_int &other) { 958 return *this *= other.inv(); 959 } 960 961 friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; } 962 friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; } 963 friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; } 964 friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; } 965 966 _m_int& operator++() { 967 val = val == MOD - 1 ? 0 : val + 1; 968 return *this; 969 } 970 971 _m_int& operator--() { 972 val = val == 0 ? MOD - 1 : val - 1; 973 return *this; 974 } 975 976 _m_int operator++(int) { _m_int before = *this; ++*this; return before; } 977 _m_int operator--(int) { _m_int before = *this; --*this; return before; } 978 979 _m_int operator-() const { 980 return val == 0 ? 0 : MOD - val; 981 } 982 983 friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; } 984 friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; } 985 friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; } 986 friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; } 987 friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; } 988 friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; } 989 990 _m_int inv() const { 991 return inv_mod(val); 992 } 993 994 _m_int pow(int64_t p) const { 995 if (p < 0) 996 return inv().pow(-p); 997 998 _m_int a = *this, result = 1; 999 1000 while (p > 0) { 1001 if (p & 1) 1002 result *= a; 1003 a *= a; 1004 p >>= 1; 1005 } 1006 1007 return result; 1008 } 1009 1010 friend ostream& operator<<(ostream &os, const _m_int &m) { 1011 return os << m.val; 1012 } 1013 }; 1014 1015 extern const int MOD = 998244353; 1016 using Mint = _m_int<MOD>; 1017 1018 const int LOGN = 19; 1019 const int N = (1 << LOGN); 1020 const int T = 2; 1021 Mint g = 3; 1022 1023 vector<Mint> w[LOGN]; 1024 vector<int> rv[LOGN]; 1025 1026 void precalc() { 1027 Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN)); 1028 forn(st, LOGN - 1) { 1029 w[st].assign(1 << st, 1); 1030 Mint bw = wb.pow(1 << (LOGN - st - 1)); 1031 Mint cw = 1; 1032 forn(k, 1 << st) { 1033 w[st][k] = cw; 1034 cw *= bw; 1035 } 1036 } 1037 forn(st, LOGN) { 1038 rv[st].assign(1 << st, 0); 1039 if (st == 0) { 1040 rv[st][0] = 0; 1041 continue; 1042 } 1043 int h = (1 << (st - 1)); 1044 forn(k, 1 << st) 1045 rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h); 1046 } 1047 } 1048 1049 void ntt(vector<Mint> &a, bool inv) { 1050 int n = sz(a); 1051 int ln = __builtin_ctz(n); 1052 forn(i, n) { 1053 int ni = rv[ln][i]; 1054 if (i < ni) swap(a[i], a[ni]); 1055 } 1056 forn(st, ln) { 1057 int len = 1 << st; 1058 for (int k = 0; k < n; k += (len << 1)) { 1059 fore(pos, k, k + len){ 1060 Mint l = a[pos]; 1061 Mint r = a[pos + len] * w[st][pos - k]; 1062 a[pos] = l + r; 1063 a[pos + len] = l - r; 1064 } 1065 } 1066 } 1067 if (inv) { 1068 Mint rn = Mint(n).inv(); 1069 forn(i, n) a[i] *= rn; 1070 reverse(a.begin() + 1, a.end()); 1071 } 1072 } 1073 1074 vector<Mint> mul(vector<Mint> a, vector<Mint> b) { 1075 int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1)); 1076 a.resize(cnt); 1077 b.resize(cnt); 1078 ntt(a, false); 1079 ntt(b, false); 1080 vector<Mint> c(cnt); 1081 forn(i, cnt) c[i] = a[i] * b[i]; 1082 ntt(c, true); 1083 while(c.size() > 1 && c.back() == 0) 1084 c.pop_back(); 1085 return c; 1086 } 1087 1088 struct dp 1089 { 1090 vector<Mint> val[T][T]; 1091 bool is_unit; 1092 1093 dp() {}; 1094 dp(int len) 1095 { 1096 is_unit = len == 1; 1097 for(int j = 0; j < T; j++) 1098 for(int k = 0; k < T; k++) 1099 val[j][k] = {0}; 1100 if(len == 1) 1101 val[0][0][0] = 1; 1102 else 1103 val[1][1][0] = 2; 1104 } 1105 1106 dp(const dp& a, const dp& b) 1107 { 1108 is_unit = false; 1109 for(int l1 = 0; l1 < T; l1++) 1110 for(int r1 = 0; r1 < T; r1++) 1111 for(int l2 = 0; l2 < T; l2++) 1112 for(int r2 = 0; r2 < T; r2++) 1113 { 1114 vector<Mint> cur = mul(a.val[l1][r1], b.val[l2][r2]); 1115 if(val[l1][r2].size() < cur.size()) 1116 val[l1][r2].resize(cur.size()); 1117 for(int i = 0; i < cur.size(); i++) 1118 val[l1][r2][i] += cur[i]; 1119 Mint merge_coeff = 2; 1120 if(r1 == 1) 1121 merge_coeff /= 2; 1122 if(l2 == 1) 1123 merge_coeff /= 2; 1124 cur.insert(cur.begin(), 0); 1125 for(int i = 0; i < cur.size(); i++) 1126 cur[i] *= merge_coeff; 1127 int L1 = l1; 1128 int R2 = r2; 1129 if(a.is_unit) 1130 L1 = 1; 1131 if(b.is_unit) 1132 R2 = 1; 1133 if(val[L1][R2].size() < cur.size()) 1134 val[L1][R2].resize(cur.size()); 1135 for(int i = 0; i < cur.size(); i++) 1136 { 1137 val[L1][R2][i] += cur[i]; 1138 } 1139 } 1140 } 1141 }; 1142 1143 ostream& operator<<(ostream& out, const dp& a) 1144 { 1145 for(int i = 0; i < T; i++) 1146 for(int j = 0; j < T; j++) 1147 { 1148 out << "[" << i << "][" << j << "]"; 1149 for(auto x : a.val[i][j]) 1150 out << " " << x; 1151 out << endl; 1152 } 1153 return out; 1154 } 1155 1156 int a[N]; 1157 int len[N]; 1158 Mint fact[N]; 1159 int n; 1160 int s; 1161 1162 dp build(int l, int r) 1163 { 1164 if(l == r - 1) 1165 { 1166 dp res(len[l]); 1167 //cerr << l << " " << r << endl; 1168 //cerr << res; 1169 return res; 1170 } 1171 else 1172 { 1173 int m = (l + r) / 2; 1174 dp res(build(l, m), build(m, r)); 1175 //cerr << l << " " << r << endl; 1176 //cerr << res; 1177 return res; 1178 } 1179 } 1180 1181 int main() 1182 { 1183 precalc(); 1184 scanf("%d", &n); 1185 for(int i = 0; i < n; i++) 1186 scanf("%d", &a[i]); 1187 int cur = 0; 1188 while(cur != n) 1189 { 1190 if(cur + a[cur] > n) 1191 { 1192 cout << 0 << endl; 1193 return 0; 1194 } 1195 for(int l = cur; l < cur + a[cur]; l++) 1196 if(a[l] != a[cur]) 1197 { 1198 cout << 0 << endl; 1199 return 0; 1200 } 1201 len[s++] = a[cur]; 1202 cur += a[cur]; 1203 } 1204 1205 fact[0] = 1; 1206 for(int i = 1; i <= s; i++) 1207 fact[i] = i * fact[i - 1]; 1208 1209 dp res = build(0, s); 1210 1211 Mint ans = 0; 1212 for(int i = 0; i < s; i++) 1213 for(int j = 0; j < T; j++) 1214 for(int k = 0; k < T; k++) 1215 if(res.val[j][k].size() > i) 1216 ans += fact[s - i] * res.val[j][k][i] * (i % 2 == 0 ? 1 : MOD - 1); 1217 cout << ans << endl; 1218 } 1219 ```