codeforces-scrape

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

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