codeforces-scrape

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

1786.md (19442B)


      1 Source: https://codeforces.com/blog/entry/112875
      2 
      3 [1786A2 - Alternating Deck (hard version)](/contest/1786/problem/A2 "Codeforces Round 850 (Div. 2, based on VK Cup 2022 - Final Round)")
      4 
      5 Problem author: [KAN](/profile/KAN "Legendary Grandmaster KAN")
      6 
      7 **Explanation**
      8 
      9 Tutorial is loading...
     10 
     11 **Code by KAN**
     12 
     13 ```
     14 NT = int(input())
     15  
     16 for T in range(NT):
     17 	n = int(input())
     18 	answer = [0, 0, 0, 0]
     19 	first_card = 1
     20 	for it in range(1, 20000):
     21 		who = 0 if it % 4 == 1 or it % 4 == 0 else 1
     22 		cnt = it
     23 		if n < cnt:
     24 			cnt = n
     25 		cnt_white = (cnt + first_card % 2) // 2
     26 		cnt_black = cnt - cnt_white
     27 		answer[who * 2 + 0] += cnt_white
     28 		answer[who * 2 + 1] += cnt_black
     29 		first_card += cnt
     30 		n -= cnt
     31 		if n == 0:
     32 			break
     33 	assert(n == 0)
     34 	print(*answer)
     35 ```
     36 
     37 [1786B - Cake Assembly Line](/contest/1786/problem/B "Codeforces Round 850 (Div. 2, based on VK Cup 2022 - Final Round)")
     38 
     39 Problem author: [KAN](/profile/KAN "Legendary Grandmaster KAN")
     40 
     41 **Explanation**
     42 
     43 Tutorial is loading...
     44 
     45 **Code by KAN**
     46 
     47 ```
     48 #include <bits/stdc++.h>
     49 
     50 using namespace std;
     51 
     52 const int inf = 1000000000;
     53 
     54 int main() {
     55   int tt;
     56   cin >> tt;
     57   while (tt--) {
     58     int n, w, h;
     59     cin >> n >> w >> h;
     60     vector<int> a(n);
     61     for (int i = 0; i < n; i++) {
     62       cin >> a[i];
     63     }
     64     vector<int> b(n);
     65     for (int i = 0; i < n; i++) {
     66       cin >> b[i];
     67     }
     68     int minshift = -inf;
     69     int maxshift = inf;
     70     for (int i = 0; i < n; i++) {
     71       minshift = max(minshift, (b[i] + h) - (a[i] + w));
     72       maxshift = min(maxshift, (b[i] - h) - (a[i] - w));
     73     }
     74     if (minshift <= maxshift) {
     75       cout << "YES" << '\n';
     76     } else {
     77       cout << "NO" << '\n';
     78     }
     79   }
     80   return 0;
     81 }
     82 ```
     83 
     84 [1785A - Monsters (easy version)](/contest/1785/problem/A "Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round)")
     85 
     86 Problem author: [tourist](/profile/tourist "Legendary Grandmaster tourist")
     87 
     88 **Explanation**
     89 
     90 Tutorial is loading...
     91 
     92 **Code by tourist**
     93 
     94 ```
     95 #include <bits/stdc++.h>
     96 
     97 using namespace std;
     98 
     99 int main() {
    100   int tt;
    101   cin >> tt;
    102   while (tt--) {
    103     int n;
    104     cin >> n;
    105     vector<int> a(n);
    106     for (int i = 0; i < n; i++) {
    107       cin >> a[i];
    108     }
    109     sort(a.begin(), a.end());
    110     vector<int> b(n);
    111     b[0] = 1;
    112     for (int i = 1; i < n; i++) {
    113       b[i] = min(b[i - 1] + 1, a[i]);
    114     }
    115     long long ans = 0;
    116     for (int i = 0; i < n; i++) {
    117       ans += a[i] - b[i];
    118     }
    119     cout << ans << '\n';
    120   }
    121   return 0;
    122 }
    123 ```
    124 
    125 [1785B - Letter Exchange](/contest/1785/problem/B "Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round)")
    126 
    127 Problem author: [tourist](/profile/tourist "Legendary Grandmaster tourist")
    128 
    129 **Explanation**
    130 
    131 Tutorial is loading...
    132 
    133 **Code by PavelKunyavskiy**
    134 
    135 ```
    136 private fun IntArray.countOf(value: Int) = count { it == value }
    137 
    138 private fun solve() {
    139     val s = "win"
    140     fun IntArray.bad() = (0 until 3).singleOrNull { c -> count { it == c } > 1 }
    141     val data = List(readInt()) { readLn().map { s.indexOf(it) }.toIntArray() }
    142     val ans = mutableListOf<String>()
    143     fun exchange(c1: Int, c2: Int, i1: Int, i2: Int) {
    144         ans.add("${i1+1} ${s[c1]} ${i2+1} ${s[c2]}")
    145         val index1 = data[i1].indexOf(c1)
    146         val index2 = data[i2].indexOf(c2)
    147         data[i1][index1] = c2
    148         data[i2][index2] = c1
    149     }
    150     val todo = List(3) { List(3) { mutableListOf<Int> () } }
    151     for (i in data.indices) {
    152         val bad = data[i].bad() ?: continue
    153         for (j in 0 until 3) {
    154             if (data[i].countOf(j) == 0) {
    155                 todo[bad][j].add(i)
    156             }
    157         }
    158     }
    159 
    160     for (i in 0 until 3) {
    161         for (j in 0 until 3) {
    162             if (i != j) {
    163                 while (todo[i][j].isNotEmpty() && todo[j][i].isNotEmpty()) {
    164                     exchange(i, j, todo[i][j].removeLast(), todo[j][i].removeLast())
    165                 }
    166             }
    167         }
    168     }
    169     while (todo[0][1].isNotEmpty() && todo[1][2].isNotEmpty() && todo[2][0].isNotEmpty()) {
    170         val a = todo[0][1].removeLast()
    171         val b = todo[1][2].removeLast()
    172         val c = todo[2][0].removeLast()
    173         exchange(0, 1, a, b)
    174         exchange(0, 2, b, c)
    175     }
    176     while (todo[1][0].isNotEmpty() && todo[2][1].isNotEmpty() && todo[0][2].isNotEmpty()) {
    177         val a = todo[1][0].removeLast()
    178         val b = todo[2][1].removeLast()
    179         val c = todo[0][2].removeLast()
    180         exchange(1, 0, a, c)
    181         exchange(2, 1, b, c)
    182     }
    183     println(ans.size)
    184     println(ans.joinToString("\n"))
    185 }
    186 
    187 fun main() {
    188     repeat(readInt()) {
    189         solve()
    190     }
    191 }
    192 
    193 private fun readLn() = readLine()!!
    194 private fun readInt() = readLn().toInt()
    195 ```
    196 
    197 [1785C - Monsters (hard version)](/contest/1785/problem/C "Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round)")
    198 
    199 Problem author: [tourist](/profile/tourist "Legendary Grandmaster tourist")
    200 
    201 **Explanation**
    202 
    203 Tutorial is loading...
    204 
    205 **Code by tourist**
    206 
    207 ```
    208 #include <bits/stdc++.h>
    209 
    210 using namespace std;
    211 
    212 int main() {
    213   int tt;
    214   cin >> tt;
    215   while (tt--) {
    216     int n;
    217     cin >> n;
    218     vector<int> a(n);
    219     for (int i = 0; i < n; i++) {
    220       cin >> a[i];
    221     }
    222     vector<int> mn(2 * n - 1);
    223     vector<int> add(2 * n - 1, 0);
    224     vector<int> pos(2 * n - 1);
    225     auto Pull = [&](int x, int z) {
    226       mn[x] = min(mn[x + 1], mn[z]) + add[x];
    227       pos[x] = (mn[x + 1] <= mn[z] ? pos[x + 1] : pos[z]);
    228     };
    229     function<void(int, int, int, int, int, int)> Modify = [&](int x, int l, int r, int ll, int rr, int v) {
    230       if (ll <= l && r <= rr) {
    231         mn[x] += v;
    232         add[x] += v;
    233         return;
    234       }
    235       int y = (l + r) >> 1;
    236       int z = x + 2 * (y - l + 1);
    237       if (ll <= y) {
    238         Modify(x + 1, l, y, ll, rr, v);
    239       }
    240       if (rr > y) {
    241         Modify(z, y + 1, r, ll, rr, v);
    242       }
    243       Pull(x, z);
    244     };
    245     function<void(int, int, int)> Build = [&](int x, int l, int r) {
    246       if (l == r) {
    247         mn[x] = l;
    248         pos[x] = l;
    249         return;
    250       }
    251       int y = (l + r) >> 1;
    252       int z = x + 2 * (y - l + 1);
    253       Build(x + 1, l, y);
    254       Build(z, y + 1, r);
    255       Pull(x, z);
    256     };
    257     Build(0, 1, n);
    258     long long s = 0;
    259     long long m = 0;
    260     for (int i = 0; i < n; i++) {
    261       s += a[i];
    262       m += 1;
    263       Modify(0, 1, n, a[i], n, -1);
    264       if (mn[0] < 0) {
    265         s -= pos[0];
    266         m -= 1;
    267         Modify(0, 1, n, pos[0], n, +1);
    268       }
    269       cout << s - m * (m + 1) / 2 << " \n"[i == n - 1];
    270     }
    271   }
    272   return 0;
    273 }
    274 ```
    275 
    276 [1785D - Wooden Spoon](/contest/1785/problem/D "Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round)")
    277 
    278 Problem author: [tourist](/profile/tourist "Legendary Grandmaster tourist")
    279 
    280 **Explanation**
    281 
    282 Tutorial is loading...
    283 
    284 **Code by tourist**
    285 
    286 ```
    287 #include <bits/stdc++.h>
    288 
    289 using namespace std;
    290 
    291 template <typename T>
    292 T inverse(T a, T m) {
    293   T u = 0, v = 1;
    294   while (a != 0) {
    295     T t = m / a;
    296     m -= t * a; swap(a, m);
    297     u -= t * v; swap(u, v);
    298   }
    299   assert(m == 1);
    300   return u;
    301 }
    302 
    303 template <typename T>
    304 class Modular {
    305  public:
    306   using Type = typename decay<decltype(T::value)>::type;
    307 
    308   constexpr Modular() : value() {}
    309   template <typename U>
    310   Modular(const U& x) {
    311     value = normalize(x);
    312   }
    313 
    314   template <typename U>
    315   static Type normalize(const U& x) {
    316     Type v;
    317     if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    318     else v = static_cast<Type>(x % mod());
    319     if (v < 0) v += mod();
    320     return v;
    321   }
    322 
    323   const Type& operator()() const { return value; }
    324   template <typename U>
    325   explicit operator U() const { return static_cast<U>(value); }
    326   constexpr static Type mod() { return T::value; }
    327 
    328   Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
    329   Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
    330 
    331   template <typename U = T>
    332   typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    333     value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    334     return *this;
    335   }
    336 
    337  private:
    338   Type value;
    339 };
    340 
    341 template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
    342 template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
    343 template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
    344 template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
    345 
    346 constexpr int md = 998244353;
    347 using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
    348 
    349 vector<Mint> fact(1, 1);
    350 vector<Mint> inv_fact(1, 1);
    351 
    352 Mint C(int n, int k) {
    353   if (k < 0 || k > n) {
    354     return 0;
    355   }
    356   while ((int) fact.size() < n + 1) {
    357     fact.push_back(fact.back() * (int) fact.size());
    358     inv_fact.push_back(1 / fact.back());
    359   }
    360   return fact[n] * inv_fact[k] * inv_fact[n - k];
    361 }
    362 
    363 int main() {
    364   ios::sync_with_stdio(false);
    365   cin.tie(0);
    366   int n;
    367   cin >> n;
    368   C(1 << n, 0);
    369   vector<Mint> dp(1 << n);
    370   dp[0] = (1 << n) * fact[1 << (n - 1)];
    371   for (int rd = n - 2; rd >= 0; rd--) {
    372     vector<Mint> new_dp(1 << n);
    373     Mint sum = 0;
    374     for (int i = 0; i < (1 << n); i++) {
    375       new_dp[i] = sum * C((1 << n) - 1 - i - (1 << rd), (1 << rd) - 1) * fact[1 << rd];
    376       sum += dp[i];
    377     }
    378     swap(dp, new_dp);
    379   }
    380   Mint sum = 0;
    381   for (int i = 0; i < (1 << n); i++) {
    382     cout << sum() << '\n';
    383     sum += dp[i];
    384   }
    385   return 0;
    386 }
    387 ```
    388 
    389 [1785E - Infinite Game](/contest/1785/problem/E "Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round)")
    390 
    391 Problem author: [tourist](/profile/tourist "Legendary Grandmaster tourist")
    392 
    393 **Explanation**
    394 
    395 Tutorial is loading...
    396 
    397 **Code by tourist**
    398 
    399 ```
    400 #include <bits/stdc++.h>
    401 
    402 using namespace std;
    403 
    404 template <typename T>
    405 class Modular {
    406  public:
    407   using Type = typename decay<decltype(T::value)>::type;
    408 
    409   constexpr Modular() : value() {}
    410   template <typename U>
    411   Modular(const U& x) {
    412     value = normalize(x);
    413   }
    414 
    415   template <typename U>
    416   static Type normalize(const U& x) {
    417     Type v;
    418     if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    419     else v = static_cast<Type>(x % mod());
    420     if (v < 0) v += mod();
    421     return v;
    422   }
    423 
    424   const Type& operator()() const { return value; }
    425   template <typename U>
    426   explicit operator U() const { return static_cast<U>(value); }
    427   constexpr static Type mod() { return T::value; }
    428 
    429   Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
    430   template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
    431 
    432   template <typename U>
    433   friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
    434 
    435  private:
    436   Type value;
    437 };
    438 
    439 template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
    440 template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
    441 
    442 constexpr int md = 998244353;
    443 using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
    444 
    445 int main() {
    446   ios::sync_with_stdio(false);
    447   cin.tie(0);
    448   string s;
    449   cin >> s;
    450   int len = (int) s.size();
    451   vector<Mint> ans(3);
    452   for (int use = 1; use < (1 << 4); use++) {
    453     int pw = 1 << 8;
    454     int init = 0;
    455     for (int i = 0; i < 4; i++) {
    456       init += i << (2 * i);
    457     }
    458     vector<vector<int>> go_state(pw, vector<int>(2));
    459     vector<vector<int>> go_diff(pw, vector<int>(2));
    460     for (int state = 0; state < pw; state++) {
    461       for (int put = 0; put < 2; put++) {
    462         int new_diff = 0;
    463         int new_state = 0;
    464         for (int i = 0; i < 4; i++) {
    465           int to = (state >> (2 * i)) & 3;
    466           if (put == 0) {
    467             if (to & 1) {
    468               if (use & (1 << i)) {
    469                 new_diff += 1;
    470               }
    471               to = 0;
    472             } else {
    473               to |= 1;
    474             }
    475           } else {
    476             if (to & 2) {
    477               if (use & (1 << i)) {
    478                 new_diff -= 1;
    479               }
    480               to = 0;
    481             } else {
    482               to |= 2;
    483             }
    484           }
    485           new_state += to << (2 * i);
    486         }
    487         go_state[state][put] = new_state;
    488         go_diff[state][put] = new_diff;
    489       }
    490     }
    491     int limit = (len + 1) / 2 * 2 * __builtin_popcount(use);
    492     vector<vector<Mint>> dp(2 * limit + 1, vector<Mint>(pw));
    493     dp[limit][init] = 1;
    494     for (char c : s) {
    495       vector<vector<Mint>> new_dp(2 * limit + 1, vector<Mint>(pw));
    496       for (int sum = 0; sum < (int) dp.size(); sum++) {
    497         for (int state = 0; state < pw; state++) {
    498           if (dp[sum][state] == 0) {
    499             continue;
    500           }
    501           for (int put = 0; put < 2; put++) {
    502             if ((put == 0 && c == 'b') || (put == 1 && c == 'a')) {
    503               continue;
    504             }
    505             int new_sum = sum + go_diff[state][put];
    506             int new_state = go_state[state][put];
    507             new_dp[new_sum][new_state] += dp[sum][state];
    508           }
    509         }
    510       }
    511       swap(dp, new_dp);
    512     }
    513     for (int sum = 0; sum < (int) dp.size(); sum++) {
    514       for (int state = 0; state < pw; state++) {
    515         if (dp[sum][state] == 0) {
    516           continue;
    517         }
    518         vector<int> to(4);
    519         for (int i = 0; i < 4; i++) {
    520           to[i] = (state >> (2 * i)) & 3;
    521         }
    522         vector<int> seq(1, 0);
    523         while (true) {
    524           int nxt = to[seq.back()];
    525           bool done = false;
    526           for (int i = 0; i < (int) seq.size(); i++) {
    527             if (seq[i] == nxt) {
    528               done = true;
    529               seq.erase(seq.begin(), seq.begin() + i);
    530               break;
    531             }
    532           }
    533           if (done) {
    534             break;
    535           }
    536           seq.push_back(nxt);
    537         }
    538         int real_use = 0;
    539         for (int x : seq) {
    540           real_use |= (1 << x);
    541         }
    542         if (use == real_use) {
    543           ans[sum > limit ? 0 : (sum < limit ? 2 : 1)] += dp[sum][state];
    544         }
    545       }
    546     }
    547   }
    548   for (int i = 0; i < 3; i++) {
    549     cout << ans[i]() << '\n';
    550   }
    551   return 0;
    552 }
    553 ```
    554 
    555 [1785F - Minimums or Medians](/contest/1785/problem/F "Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round)")
    556 
    557 Problem author: [tourist](/profile/tourist "Legendary Grandmaster tourist")
    558 
    559 **Explanation**
    560 
    561 Tutorial is loading...
    562 
    563 **Code by tourist, O(n^2)**
    564 
    565 ```
    566 #include <bits/stdc++.h>
    567 
    568 using namespace std;
    569 
    570 template <typename T>
    571 T inverse(T a, T m) {
    572   T u = 0, v = 1;
    573   while (a != 0) {
    574     T t = m / a;
    575     m -= t * a; swap(a, m);
    576     u -= t * v; swap(u, v);
    577   }
    578   assert(m == 1);
    579   return u;
    580 }
    581 
    582 template <typename T>
    583 class Modular {
    584  public:
    585   using Type = typename decay<decltype(T::value)>::type;
    586 
    587   constexpr Modular() : value() {}
    588   template <typename U>
    589   Modular(const U& x) {
    590     value = normalize(x);
    591   }
    592 
    593   template <typename U>
    594   static Type normalize(const U& x) {
    595     Type v;
    596     if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    597     else v = static_cast<Type>(x % mod());
    598     if (v < 0) v += mod();
    599     return v;
    600   }
    601 
    602   const Type& operator()() const { return value; }
    603   template <typename U>
    604   explicit operator U() const { return static_cast<U>(value); }
    605   constexpr static Type mod() { return T::value; }
    606 
    607   Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
    608   Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
    609 
    610   template <typename U = T>
    611   typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    612     value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    613     return *this;
    614   }
    615 
    616  private:
    617   Type value;
    618 };
    619 
    620 template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
    621 template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
    622 
    623 constexpr int md = 998244353;
    624 using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
    625 
    626 vector<Mint> fact(1, 1);
    627 vector<Mint> inv_fact(1, 1);
    628 
    629 Mint C(int n, int k) {
    630   if (k < 0 || k > n) {
    631     return 0;
    632   }
    633   while ((int) fact.size() < n + 1) {
    634     fact.push_back(fact.back() * (int) fact.size());
    635     inv_fact.push_back(1 / fact.back());
    636   }
    637   return fact[n] * inv_fact[k] * inv_fact[n - k];
    638 }
    639 
    640 int main() {
    641   ios::sync_with_stdio(false);
    642   cin.tie(0);
    643   int n, k;
    644   cin >> n >> k;
    645   Mint ans = 1;
    646   for (int p = 1; p <= k; p++) {
    647     for (int q = 0; q <= max(0, k - 1 - p); q++) {
    648       if (2 * (k - p - q) + 1 <= n - p) {
    649         ans += (q == 0 ? 1 : C((k - 1 - p) - (q - 1), q));
    650       }
    651     }
    652   }
    653   for (int q = 1; q <= k - 1; q++) {
    654     int pos = 2 * (k - q) + 2;
    655     int shifts = max(1, pos - n);
    656     int left = k - shifts;
    657     ans += C(left - (q - 1), q);
    658   }
    659   cout << ans() << '\n';
    660   return 0;
    661 }
    662 ```
    663 
    664 **Code by tourist, O(n)**
    665 
    666 ```
    667 #include <bits/stdc++.h>
    668 
    669 using namespace std;
    670 
    671 template <typename T>
    672 T inverse(T a, T m) {
    673   T u = 0, v = 1;
    674   while (a != 0) {
    675     T t = m / a;
    676     m -= t * a; swap(a, m);
    677     u -= t * v; swap(u, v);
    678   }
    679   assert(m == 1);
    680   return u;
    681 }
    682 
    683 template <typename T>
    684 class Modular {
    685  public:
    686   using Type = typename decay<decltype(T::value)>::type;
    687 
    688   constexpr Modular() : value() {}
    689   template <typename U>
    690   Modular(const U& x) {
    691     value = normalize(x);
    692   }
    693 
    694   template <typename U>
    695   static Type normalize(const U& x) {
    696     Type v;
    697     if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    698     else v = static_cast<Type>(x % mod());
    699     if (v < 0) v += mod();
    700     return v;
    701   }
    702 
    703   const Type& operator()() const { return value; }
    704   template <typename U>
    705   explicit operator U() const { return static_cast<U>(value); }
    706   constexpr static Type mod() { return T::value; }
    707 
    708   Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
    709   Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
    710 
    711   template <typename U = T>
    712   typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    713     value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    714     return *this;
    715   }
    716 
    717  private:
    718   Type value;
    719 };
    720 
    721 template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
    722 template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
    723 
    724 constexpr int md = 998244353;
    725 using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
    726 
    727 vector<Mint> fact(1, 1);
    728 vector<Mint> inv_fact(1, 1);
    729 
    730 Mint C(int n, int k) {
    731   if (k < 0 || k > n) {
    732     return 0;
    733   }
    734   while ((int) fact.size() < n + 1) {
    735     fact.push_back(fact.back() * (int) fact.size());
    736     inv_fact.push_back(1 / fact.back());
    737   }
    738   return fact[n] * inv_fact[k] * inv_fact[n - k];
    739 }
    740 
    741 int main() {
    742   ios::sync_with_stdio(false);
    743   cin.tie(0);
    744   int n, k;
    745   cin >> n >> k;
    746   Mint ans = 1;
    747   for (int q = 0; q <= k - 1; q++) {
    748     int bound = k - q - max(1, 2 * (k - q) - n + 1);
    749     ans += C(bound + 1, q + 1);
    750   }
    751   for (int q = 1; q <= k - 1; q++) {
    752     int pos = 2 * (k - q) + 2;
    753     int shifts = max(1, pos - n);
    754     int left = k - shifts;
    755     ans += C(left - (q - 1), q);
    756   }
    757   cout << ans() << '\n';
    758   return 0;
    759 }
    760 ```