codeforces-scrape

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

1781.md (30087B)


      1 Source: https://codeforces.com/blog/entry/111783
      2 
      3 [1782A - Parallel Projection](/contest/1782/problem/A)
      4 
      5 **Explanation**
      6 
      7 Tutorial is loading...
      8 
      9 **Source**
     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 w, d, h;
     21     cin >> w >> d >> h;
     22     int a, b;
     23     cin >> a >> b;
     24     int f, g;
     25     cin >> f >> g;
     26     int ans = b + abs(a - f) + g;
     27     ans = min(ans, a + abs(b - g) + f);
     28     ans = min(ans, (d - b) + abs(a - f) + (d - g));
     29     ans = min(ans, (w - a) + abs(b - g) + (w - f));
     30     cout << ans + h << '\n';
     31   }
     32   return 0;
     33 }
     34 ```
     35 
     36 [1782B - Going to the Cinema](/contest/1782/problem/B)
     37 
     38 **Explanation**
     39 
     40 Tutorial is loading...
     41 
     42 **Source 1**
     43 
     44 ```
     45 #include <bits/stdc++.h>
     46 
     47 using namespace std;
     48 
     49 int main() {
     50   int tt;
     51   cin >> tt;
     52   while (tt--) {
     53     int n;
     54     cin >> n;
     55     vector<int> cnt(n + 1);
     56     for (int i = 0; i < n; i++) {
     57       int a;
     58       cin >> a;
     59       cnt[a] += 1;
     60     }
     61     int ans = 0;
     62     int sum = 0;
     63     for (int k = 0; k <= n; k++) {
     64       if (cnt[k] == 0 && sum == k) {
     65         ans += 1;
     66       }
     67       sum += cnt[k];
     68     }
     69     cout << ans << '\n';
     70   }
     71   return 0;
     72 }
     73 ```
     74 
     75 **Source 2**
     76 
     77 ```
     78 #include <bits/stdc++.h>
     79 
     80 using namespace std;
     81 
     82 int main() {
     83   int tt;
     84   cin >> tt;
     85   while (tt--) {
     86     int n;
     87     cin >> n;
     88     vector<int> a(n);
     89     for (int i = 0; i < n; i++) {
     90       cin >> a[i];
     91     }
     92     sort(a.begin(), a.end());
     93     int ans = 0;
     94     for (int k = 0; k <= n; k++) {
     95       if (k == 0 || a[k - 1] < k) {
     96         if (k == n || a[k] > k) {
     97           ans += 1;
     98         }
     99       }
    100     }
    101     cout << ans << '\n';
    102   }
    103   return 0;
    104 }
    105 ```
    106 
    107 [1782C - Equal Frequencies](/contest/1782/problem/C)
    108 
    109 **Explanation**
    110 
    111 Tutorial is loading...
    112 
    113 **Source**
    114 
    115 ```
    116 #include <bits/stdc++.h>
    117 
    118 using namespace std;
    119 
    120 int main() {
    121   int tt;
    122   cin >> tt;
    123   while (tt--) {
    124     int n;
    125     cin >> n;
    126     string s;
    127     cin >> s;
    128     vector<vector<int>> at(26);
    129     for (int i = 0; i < n; i++) {
    130       at[(int) (s[i] - 'a')].push_back(i);
    131     }
    132     vector<int> order(26);
    133     iota(order.begin(), order.end(), 0);
    134     sort(order.begin(), order.end(), [&](int i, int j) {
    135       return at[i].size() > at[j].size();
    136     });
    137     string res = "";
    138     int best = -1;
    139     for (int cnt = 1; cnt <= 26; cnt++) {
    140       if (n % cnt == 0) {
    141         int cur = 0;
    142         for (int i = 0; i < cnt; i++) {
    143           cur += min(n / cnt, (int) at[order[i]].size());
    144         }
    145         if (cur > best) {
    146           best = cur;
    147           res = string(n, ' ');
    148           vector<char> extra;
    149           for (int it = 0; it < cnt; it++) {
    150             int i = order[it];
    151             for (int j = 0; j < n / cnt; j++) {
    152               if (j < (int) at[i].size()) {
    153                 res[at[i][j]] = (char) ('a' + i);
    154               } else {
    155                 extra.push_back((char) ('a' + i));
    156               }
    157             }
    158           }
    159           for (char& c : res) {
    160             if (c == ' ') {
    161               c = extra.back();
    162               extra.pop_back();
    163             }
    164           }
    165         }
    166       }
    167     }
    168     cout << n - best << '\n';
    169     cout << res << '\n';
    170   }
    171   return 0;
    172 }
    173 ```
    174 
    175 [1782D - Many Perfect Squares](/contest/1782/problem/D)
    176 
    177 **Explanation**
    178 
    179 Tutorial is loading...
    180 
    181 **Source**
    182 
    183 ```
    184 #include <bits/stdc++.h>
    185 
    186 using namespace std;
    187 
    188 int main() {
    189   int tt;
    190   cin >> tt;
    191   while (tt--) {
    192     int n;
    193     cin >> n;
    194     vector<int> a(n);
    195     for (int i = 0; i < n; i++) {
    196       cin >> a[i];
    197     }
    198     int ans = 1;
    199     auto Test = [&](long long x) {
    200       int cnt = 0;
    201       for (int v : a) {
    202         long long u = llround(sqrtl(v + x));
    203         if (u * u == v + x) {
    204           cnt += 1;
    205         }
    206       }
    207       ans = max(ans, cnt);
    208     };
    209     for (int i = 0; i < n; i++) {
    210       for (int j = i + 1; j < n; j++) {
    211         int diff = a[j] - a[i];
    212         for (int k = 1; k * k <= diff; k++) {
    213           if (diff % k == 0) {
    214             long long q = k + diff / k;
    215             if (q % 2 == 0) {
    216               q /= 2;
    217               if (q * q >= a[j]) {
    218                 Test(q * q - a[j]);
    219               }
    220             }
    221           }
    222         }
    223       }
    224     }
    225     cout << ans << '\n';
    226   }
    227   return 0;
    228 }
    229 ```
    230 
    231 [1782E - Rectangle Shrinking](/contest/1782/problem/E)
    232 
    233 **Explanation**
    234 
    235 Tutorial is loading...
    236 
    237 **Source**
    238 
    239 ```
    240 #include <bits/stdc++.h>
    241 
    242 using namespace std;
    243 
    244 int main() {
    245   ios::sync_with_stdio(false);
    246   cin.tie(0);
    247   int tt;
    248   cin >> tt;
    249   while (tt--) {
    250     int n;
    251     cin >> n;
    252     vector<int> r1(n), c1(n), r2(n), c2(n);
    253     for (int i = 0; i < n; i++) {
    254       cin >> r1[i] >> c1[i] >> r2[i] >> c2[i];
    255       assert(1 <= r1[i] && r1[i] <= r2[i] && r2[i] <= 2 && c1[i] <= c2[i]);
    256       --c1[i];
    257     }
    258     vector<int> order(n);
    259     iota(order.begin(), order.end(), 0);
    260     sort(order.begin(), order.end(), [&](int i, int j) {
    261       return c1[i] < c1[j];
    262     });
    263     set<pair<int, int>> s;
    264     int ans = 0;
    265     int p1 = -1;
    266     int p2 = -1;
    267     for (int i : order) {
    268       if (r1[i] == 1 && r2[i] == 2) {
    269         if (p1 >= c2[i]) {
    270           r1[i] = 2;
    271         }
    272         if (p2 >= c2[i]) {
    273           r2[i] = 1;
    274         }
    275         if (r1[i] > r2[i]) {
    276           continue;
    277         }
    278       }
    279       if (r1[i] == 1 && r2[i] == 2) {
    280         while (!s.empty()) {
    281           auto it = prev(s.end());
    282           if (it->first >= c1[i]) {
    283             c2[it->second] = c1[i];
    284             s.erase(it);
    285           } else {
    286             break;
    287           }
    288         }
    289         ans += (c2[i] - max(c1[i], p1)) + (c2[i] - max(c1[i], p2));
    290         p1 = p2 = c2[i];
    291         s.emplace(c2[i], i);
    292         continue;
    293       }
    294       assert(r1[i] == r2[i]);
    295       if (r1[i] == 1) {
    296         c1[i] = max(c1[i], p1);
    297         p1 = max(p1, c2[i]);
    298       } else {
    299         c1[i] = max(c1[i], p2);
    300         p2 = max(p2, c2[i]);
    301       }
    302       if (c1[i] < c2[i]) {
    303         ans += c2[i] - c1[i];
    304         s.emplace(c2[i], i);
    305       }
    306     }
    307     cout << ans << '\n';
    308     for (int i = 0; i < n; i++) {
    309       ++c1[i];
    310       if (r1[i] <= r2[i] && c1[i] <= c2[i]) {
    311         cout << r1[i] << " " << c1[i] << " " << r2[i] << " " << c2[i] << '\n';
    312       } else {
    313         cout << "0 0 0 0" << '\n';
    314       }
    315     }
    316   }
    317   return 0;
    318 }
    319 ```
    320 
    321 [1782F - Bracket Insertion](/contest/1782/problem/F)
    322 
    323 **Explanation**
    324 
    325 Tutorial is loading...
    326 
    327 **Source**
    328 
    329 ```
    330 #include <bits/stdc++.h>
    331 
    332 using namespace std;
    333 
    334 template <typename T>
    335 T inverse(T a, T m) {
    336   T u = 0, v = 1;
    337   while (a != 0) {
    338     T t = m / a;
    339     m -= t * a; swap(a, m);
    340     u -= t * v; swap(u, v);
    341   }
    342   assert(m == 1);
    343   return u;
    344 }
    345 
    346 template <typename T>
    347 class Modular {
    348  public:
    349   using Type = typename decay<decltype(T::value)>::type;
    350 
    351   constexpr Modular() : value() {}
    352   template <typename U>
    353   Modular(const U& x) {
    354     value = normalize(x);
    355   }
    356 
    357   template <typename U>
    358   static Type normalize(const U& x) {
    359     Type v;
    360     if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    361     else v = static_cast<Type>(x % mod());
    362     if (v < 0) v += mod();
    363     return v;
    364   }
    365 
    366   const Type& operator()() const { return value; }
    367   template <typename U>
    368   explicit operator U() const { return static_cast<U>(value); }
    369   constexpr static Type mod() { return T::value; }
    370 
    371   Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
    372   Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
    373   template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
    374   template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
    375   Modular operator-() const { return Modular(-value); }
    376 
    377   template <typename U = T>
    378   typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    379     value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    380     return *this;
    381   }
    382 
    383   Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
    384 
    385   template <typename V, typename U>
    386   friend V& operator>>(V& stream, Modular<U>& number);
    387 
    388  private:
    389   Type value;
    390 };
    391 
    392 template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
    393 template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
    394 template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
    395 
    396 template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
    397 template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
    398 template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
    399 
    400 template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
    401 
    402 template <typename U, typename T>
    403 U& operator<<(U& stream, const Modular<T>& number) {
    404   return stream << number();
    405 }
    406 
    407 template <typename U, typename T>
    408 U& operator>>(U& stream, Modular<T>& number) {
    409   typename common_type<typename Modular<T>::Type, long long>::type x;
    410   stream >> x;
    411   number.value = Modular<T>::normalize(x);
    412   return stream;
    413 }
    414 
    415 constexpr int md = 998244353;
    416 using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
    417 
    418 int main() {
    419   ios::sync_with_stdio(false);
    420   cin.tie(0);
    421   int n;
    422   Mint p;
    423   cin >> n >> p;
    424   p /= 10000;
    425   vector<vector<Mint>> C(n + 1, vector<Mint>(n + 1));
    426   for (int i = 0; i <= n; i++) {
    427     C[i][0] = 1;
    428     for (int j = 1; j <= i; j++) {
    429       C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    430     }
    431   }
    432   vector<vector<Mint>> dp(n + 1, vector<Mint>(n + 1));
    433   vector<vector<Mint>> aux(n + 1, vector<Mint>(n + 1));
    434   for (int b = 0; b <= n; b++) {
    435     dp[0][b] = aux[0][b] = 1;
    436   }
    437   for (int i = 1; i <= n; i++) {
    438     for (int b = 0; b <= n - i; b++) {
    439       for (int y = 0; y <= i - 1; y++) {
    440         dp[i][b] += C[i - 1][y] * aux[i - 1 - y][b] * (dp[y][b + 1] * p + (b == 0 ? 0 : dp[y][b - 1] * (1 - p)));
    441       }
    442       for (int j = 0; j <= i; j++) {
    443         aux[i][b] += dp[j][b] * dp[i - j][b] * C[i][j];
    444       }
    445     }
    446   }
    447   auto ans = dp[n][0];
    448   for (int i = 1; i <= 2 * n; i += 2) {
    449     ans /= i;
    450   }
    451   cout << ans << '\n';
    452   return 0;
    453 }
    454 ```
    455 
    456 [1782G - Diverse Coloring](/contest/1782/problem/G)
    457 
    458 **Explanation**
    459 
    460 Tutorial is loading...
    461 
    462 **Source (2nd approach)**
    463 
    464 ```
    465 #include <bits/stdc++.h>
    466 
    467 using namespace std;
    468 
    469 int main() {
    470   ios::sync_with_stdio(false);
    471   cin.tie(0);
    472   int tt;
    473   cin >> tt;
    474   while (tt--) {
    475     int n;
    476     cin >> n;
    477     vector<int> p(n);
    478     for (int i = 1; i < n; i++) {
    479       cin >> p[i];
    480       --p[i];
    481     }
    482     for (int i = 2; i <= n; i++) {
    483       if (i == 4 && p[1] == 0 && p[2] == 1 && p[3] == 1) {
    484         cout << 2 << '\n';
    485       } else {
    486         cout << i % 2 << '\n';
    487       }
    488     }
    489     vector<vector<int>> g(n);
    490     for (int i = 1; i < n; i++) {
    491       g[p[i]].push_back(i);
    492     }
    493     string res = "";
    494     auto Solve = [&](int nn) {
    495       vector<vector<vector<bool>>> good(nn);
    496       vector<vector<vector<vector<int>>>> prevs(nn);
    497       vector<int> sz(nn);
    498       vector<int> L(nn);
    499       vector<int> R(nn);
    500       function<void(int)> Dfs = [&](int v) {
    501         sz[v] += 1;
    502         for (int u : g[v]) {
    503           Dfs(u);
    504           sz[v] += sz[u];
    505         }
    506         L[v] = sz[v] / 2;
    507         R[v] = L[v] + 1;
    508         good[v].assign(2, vector<bool>(R[v] - L[v] + 1, false));
    509         prevs[v].assign(2, vector<vector<int>>(R[v] - L[v] + 1));
    510         auto Set = [&](int c, int k, vector<int> pr) {
    511           if (k >= L[v] && k <= R[v]) {
    512             good[v][c][k - L[v]] = true;
    513             prevs[v][c][k - L[v]] = pr;
    514           }
    515         };
    516         if (g[v].size() == 0) {
    517           Set(0, 1, {});
    518         }
    519         if (g[v].size() == 1) {
    520           int u = g[v][0];
    521           for (int cu = 0; cu < 2; cu++) {
    522             for (int ku = L[u]; ku <= R[u]; ku++) {
    523               if (good[u][cu][ku - L[u]]) {
    524                 Set(1, 1 + (sz[u] - ku), {cu, ku, 1});
    525                 if (cu == 1) {
    526                   Set(0, 1 + ku, {cu, ku, 0});
    527                 }
    528               }
    529             }
    530           }
    531         }
    532         if (g[v].size() == 2) {
    533           int u = g[v][0];
    534           int w = g[v][1];
    535           for (int cu = 0; cu < 2; cu++) {
    536             for (int ku = L[u]; ku <= R[u]; ku++) {
    537               if (good[u][cu][ku - L[u]]) {
    538                 for (int cw = 0; cw < 2; cw++) {
    539                   for (int kw = L[w]; kw <= R[w]; kw++) {
    540                     if (good[w][cw][kw - L[w]]) {
    541                       Set(1, 1 + (sz[u] - ku) + (sz[w] - kw), {cu, ku, 1, cw, kw, 1});
    542                       if (cu == 1) {
    543                         Set(1, 1 + ku + (sz[w] - kw), {cu, ku, 0, cw, kw, 1});
    544                       }
    545                       if (cw == 1) {
    546                         Set(1, 1 + (sz[u] - ku) + kw, {cu, ku, 1, cw, kw, 0});
    547                       }
    548                       if (cu == 1 && cw == 1) {
    549                         Set(0, 1 + ku + kw, {cu, ku, 0, cw, kw, 0});
    550                       }
    551                     }
    552                   }
    553                 }
    554               }
    555             }
    556           }
    557         }
    558       };
    559       Dfs(0);
    560       int best = nn + 1;
    561       int best_k = -1;
    562       for (int k = L[0]; k <= R[0]; k++) {
    563         if (good[0][1][k - L[0]]) {
    564           int val = abs(k - (nn - k));
    565           if (val < best) {
    566             best = val;
    567             best_k = k;
    568           }
    569         }
    570       }
    571       assert(best <= nn);
    572       res = string(nn, '.');
    573       function<void(int, int, int)> Restore = [&](int v, int c, int k) {
    574         int ptr = 0;
    575         for (int u : g[v]) {
    576           res[u] = (prevs[v][c][k - L[v]][ptr + 2] == 0 ? res[v] : (char) ('w' ^ 'b' ^ res[v]));
    577           Restore(u, prevs[v][c][k - L[v]][ptr], prevs[v][c][k - L[v]][ptr + 1]);
    578           ptr += 3;
    579         }
    580       };
    581       res[0] = 'w';
    582       Restore(0, 1, best_k);
    583       return best;
    584     };
    585     Solve(n);
    586     cout << res << '\n';
    587   }
    588   return 0;
    589 }
    590 ```
    591 
    592 [1782H1 - Window Signals (easy version)](/contest/1782/problem/H1)
    593 
    594 **Explanation**
    595 
    596 Tutorial is loading...
    597 
    598 **Source for easy version**
    599 
    600 ```
    601 #include <bits/stdc++.h>
    602 
    603 using namespace std;
    604 
    605 template <typename T>
    606 T inverse(T a, T m) {
    607   T u = 0, v = 1;
    608   while (a != 0) {
    609     T t = m / a;
    610     m -= t * a; swap(a, m);
    611     u -= t * v; swap(u, v);
    612   }
    613   assert(m == 1);
    614   return u;
    615 }
    616 
    617 template <typename T>
    618 class Modular {
    619  public:
    620   using Type = typename decay<decltype(T::value)>::type;
    621 
    622   constexpr Modular() : value() {}
    623   template <typename U>
    624   Modular(const U& x) {
    625     value = normalize(x);
    626   }
    627 
    628   template <typename U>
    629   static Type normalize(const U& x) {
    630     Type v;
    631     if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    632     else v = static_cast<Type>(x % mod());
    633     if (v < 0) v += mod();
    634     return v;
    635   }
    636 
    637   const Type& operator()() const { return value; }
    638   template <typename U>
    639   explicit operator U() const { return static_cast<U>(value); }
    640   constexpr static Type mod() { return T::value; }
    641 
    642   Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
    643   Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
    644   template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
    645   template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
    646   Modular operator-() const { return Modular(-value); }
    647 
    648   template <typename U = T>
    649   typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    650     value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    651     return *this;
    652   }
    653 
    654   Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
    655 
    656   template <typename V, typename U>
    657   friend V& operator>>(V& stream, Modular<U>& number);
    658 
    659  private:
    660   Type value;
    661 };
    662 
    663 template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
    664 template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
    665 template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
    666 
    667 template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
    668 template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
    669 template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
    670 
    671 template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
    672 template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
    673 template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
    674 
    675 template<typename T, typename U>
    676 Modular<T> power(const Modular<T>& a, const U& b) {
    677   assert(b >= 0);
    678   Modular<T> x = a, res = 1;
    679   U p = b;
    680   while (p > 0) {
    681     if (p & 1) res *= x;
    682     x *= x;
    683     p >>= 1;
    684   }
    685   return res;
    686 }
    687 
    688 template <typename U, typename T>
    689 U& operator<<(U& stream, const Modular<T>& number) {
    690   return stream << number();
    691 }
    692 
    693 template <typename U, typename T>
    694 U& operator>>(U& stream, Modular<T>& number) {
    695   typename common_type<typename Modular<T>::Type, long long>::type x;
    696   stream >> x;
    697   number.value = Modular<T>::normalize(x);
    698   return stream;
    699 }
    700 
    701 constexpr int md = 998244353;
    702 using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
    703 
    704 int main() {
    705   int tt;
    706   cin >> tt;
    707   while (tt--) {
    708     int h, w, k;
    709     cin >> h >> w >> k;
    710     vector<Mint> fib(h * w + 1);
    711     fib[0] = 1;
    712     fib[1] = 2;
    713     for (int i = 2; i <= h * w; i++) {
    714       fib[i] = fib[i - 1] + fib[i - 2];
    715     }
    716     vector<pair<int, int>> p(k);
    717     for (int i = 0; i < k; i++) {
    718       cin >> p[i].first >> p[i].second;
    719       --p[i].first; --p[i].second;
    720     }
    721     long long Q = 0;
    722     Mint ans = 0;
    723     for (int ww = 1; ww <= w; ww++) {
    724       for (int hh = 1; hh <= h; hh++) {
    725         for (int top = 0; top < 2; top++) {
    726           for (int bottom = 0; bottom < 2; bottom++) {
    727             for (int left = 0; left < 2; left++) {
    728               for (int right = 0; right < 2; right++) {
    729                 int sign = ((top + bottom + left + right) % 2 == 0 ? 1 : -1);
    730                 int rh = max(0, hh - top - bottom);
    731                 int rw = max(0, ww - left - right);
    732                 Q += rh * rw + (h - hh) * (w - ww);
    733                 ans += sign * power(Mint(2), rh * rw);
    734                 vector<vector<int>> g(hh * ww);
    735                 vector<bool> must(hh * ww, false);
    736                 bool any = false;
    737                 for (int i = 0; i <= h - hh; i++) {
    738                   for (int j = 0; j <= w - ww; j++) {
    739                     vector<pair<int, int>> here;
    740                     for (auto& c : p) {
    741                       if (c.first >= i + top && c.first < i + hh - bottom && c.second >= j + left && c.second < j + ww - right) {
    742                         here.emplace_back(c.first - i - top, c.second - j - left);
    743                       }
    744                     }
    745                     if (here.size() == 0) {
    746                       any = true;
    747                     }
    748                     if (here.size() == 1) {
    749                       int x = here[0].first * rw + here[0].second;
    750                       must[x] = true;
    751                     }
    752                     if (here.size() == 2) {
    753                       int x = here[0].first * rw + here[0].second;
    754                       int y = here[1].first * rw + here[1].second;
    755                       g[x].push_back(y);
    756                       g[y].push_back(x);
    757                     }
    758                   }
    759                 }
    760                 if (!any) {
    761                   Mint ways = 1;
    762                   vector<bool> was(rh * rw, false);
    763                   for (int i = 0; i < rh * rw; i++) {
    764                     if (!was[i] && g[i].empty()) {
    765                       was[i] = true;
    766                       if (!must[i]) {
    767                         ways *= 2;
    768                       }
    769                     }
    770                   }
    771                   for (int i = 0; i < rh * rw; i++) {
    772                     if (!was[i] && g[i].size() == 1) {
    773                       vector<bool> seq;
    774                       int x = i;
    775                       while (true) {
    776                         was[x] = true;
    777                         seq.push_back(must[x]);
    778                         int to = -1;
    779                         for (int y : g[x]) {
    780                           if (!was[y]) {
    781                             to = y;
    782                             break;
    783                           }
    784                         }
    785                         if (to == -1) {
    786                           break;
    787                         }
    788                         x = to;
    789                       }
    790                       int sz = (int) seq.size();
    791                       int beg = 0;
    792                       while (beg < sz) {
    793                         if (seq[beg]) {
    794                           beg += 1;
    795                           continue;
    796                         }
    797                         int end = beg;
    798                         while (end + 1 < sz && !seq[end + 1]) {
    799                           end += 1;
    800                         }
    801                         int len = end - beg + 1;
    802                         ways *= fib[len];
    803                         beg = end + 1;
    804                       }
    805                     }
    806                   }
    807                   assert(was == vector<bool>(rh * rw, true));
    808                   ans -= sign * ways;
    809                 }
    810               }
    811             }
    812           }
    813         }
    814       }
    815     }
    816     cout << ans << '\n';
    817   }
    818   return 0;
    819 }
    820 ```
    821 
    822 **Source for hard version**
    823 
    824 ```
    825 #include <bits/stdc++.h>
    826 
    827 using namespace std;
    828 
    829 template <typename T>
    830 T inverse(T a, T m) {
    831   T u = 0, v = 1;
    832   while (a != 0) {
    833     T t = m / a;
    834     m -= t * a; swap(a, m);
    835     u -= t * v; swap(u, v);
    836   }
    837   assert(m == 1);
    838   return u;
    839 }
    840 
    841 template <typename T>
    842 class Modular {
    843  public:
    844   using Type = typename decay<decltype(T::value)>::type;
    845 
    846   constexpr Modular() : value() {}
    847   template <typename U>
    848   Modular(const U& x) {
    849     value = normalize(x);
    850   }
    851 
    852   template <typename U>
    853   static Type normalize(const U& x) {
    854     Type v;
    855     if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    856     else v = static_cast<Type>(x % mod());
    857     if (v < 0) v += mod();
    858     return v;
    859   }
    860 
    861   const Type& operator()() const { return value; }
    862   template <typename U>
    863   explicit operator U() const { return static_cast<U>(value); }
    864   constexpr static Type mod() { return T::value; }
    865 
    866   Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
    867   Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
    868   template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
    869   template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
    870   Modular operator-() const { return Modular(-value); }
    871 
    872   template <typename U = T>
    873   typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    874     value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    875     return *this;
    876   }
    877 
    878   Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
    879 
    880   template <typename V, typename U>
    881   friend V& operator>>(V& stream, Modular<U>& number);
    882 
    883  private:
    884   Type value;
    885 };
    886 
    887 template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
    888 template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
    889 template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
    890 
    891 template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
    892 template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
    893 template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
    894 
    895 template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
    896 template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
    897 template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
    898 
    899 template<typename T, typename U>
    900 Modular<T> power(const Modular<T>& a, const U& b) {
    901   assert(b >= 0);
    902   Modular<T> x = a, res = 1;
    903   U p = b;
    904   while (p > 0) {
    905     if (p & 1) res *= x;
    906     x *= x;
    907     p >>= 1;
    908   }
    909   return res;
    910 }
    911 
    912 template <typename U, typename T>
    913 U& operator<<(U& stream, const Modular<T>& number) {
    914   return stream << number();
    915 }
    916 
    917 template <typename U, typename T>
    918 U& operator>>(U& stream, Modular<T>& number) {
    919   typename common_type<typename Modular<T>::Type, long long>::type x;
    920   stream >> x;
    921   number.value = Modular<T>::normalize(x);
    922   return stream;
    923 }
    924 
    925 constexpr int md = 998244353;
    926 using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
    927 
    928 class dsu {
    929  public:
    930   vector<int> p;
    931   vector<int> sz;
    932   int n;
    933 
    934   dsu(int _n) : n(_n) {
    935     p.resize(n);
    936     iota(p.begin(), p.end(), 0);
    937     sz.assign(n, 1);
    938   }
    939 
    940   inline int get(int x) {
    941     return (x == p[x] ? x : (p[x] = get(p[x])));
    942   }
    943 
    944   inline bool unite(int x, int y) {
    945     x = get(x);
    946     y = get(y);
    947     if (x != y) {
    948       p[x] = y;
    949       sz[y] += sz[x];
    950       return true;
    951     }
    952     return false;
    953   }
    954 };
    955 
    956 int main() {
    957   int tt;
    958   cin >> tt;
    959   while (tt--) {
    960     int h, w, k;
    961     cin >> h >> w >> k;
    962     vector<Mint> fib(h * w + 1);
    963     fib[0] = 1;
    964     fib[1] = 2;
    965     for (int i = 2; i <= h * w; i++) {
    966       fib[i] = fib[i - 1] + fib[i - 2];
    967     }
    968     vector<pair<int, int>> p(k);
    969     for (int i = 0; i < k; i++) {
    970       cin >> p[i].first >> p[i].second;
    971       --p[i].first; --p[i].second;
    972     }
    973     Mint ans = 0;
    974     for (int ww = 1; ww <= w; ww++) {
    975       for (int top = 0; top < 2; top++) {
    976         for (int left = 0; left < 2; left++) {
    977           for (int right = 0; right < 2; right++) {
    978             if (ww == 1 && left + right > 0) {
    979               continue;
    980             }
    981             int sign = ((top + left + right) % 2 == 0 ? 1 : -1);
    982             dsu d(h * ww);
    983             vector<vector<int>> g(h * ww);
    984             vector<bool> must(h * ww);
    985             bool done = false;
    986             Mint prod = power(Mint(2), (h - top) * (ww - left - right));
    987             for (int i = 0; i < h; i++) {
    988               for (int j = 0; j <= w - ww; j++) {
    989                 vector<pair<int, int>> here;
    990                 for (auto& c : p) {
    991                   if (c.first >= i + top && c.second >= j + left && c.second < j + ww - right) {
    992                     here.emplace_back(c.first - i, c.second - j);
    993                   }
    994                 }
    995                 if (here.size() == 0) {
    996                   ans += sign * prod;
    997                   done = true;
    998                   break;
    999                 }
   1000                 if (here.size() == 1) {
   1001                   int x = here[0].first * ww + here[0].second;
   1002                   if (!must[x]) {
   1003                     must[x] = true;
   1004                     int px = d.get(x);
   1005                     prod /= fib[d.sz[px]];
   1006                     d.sz[px] -= 1;
   1007                     int sub = 0;
   1008                     for (int y : g[x]) {
   1009                       if (!must[y]) {
   1010                         sub += 1;
   1011                       }
   1012                     }
   1013                     ans += sign * prod * fib[d.sz[px] - sub];
   1014                     prod *= fib[d.sz[px]];
   1015                   }
   1016                 }
   1017                 if (here.size() == 2) {
   1018                   int x = here[0].first * ww + here[0].second;
   1019                   int y = here[1].first * ww + here[1].second;
   1020                   int px = d.get(x);
   1021                   int py = d.get(y);
   1022                   assert(px != py);
   1023                   prod /= fib[d.sz[px]];
   1024                   prod /= fib[d.sz[py]];
   1025                   if (!must[x] && !must[y]) {
   1026                     int subx = 1;
   1027                     for (int t : g[x]) {
   1028                       if (!must[t]) {
   1029                         subx += 1;
   1030                       }
   1031                     }
   1032                     int suby = 1;
   1033                     for (int t : g[y]) {
   1034                       if (!must[t]) {
   1035                         suby += 1;
   1036                       }
   1037                     }
   1038                     ans += sign * prod * fib[d.sz[px] - subx] * fib[d.sz[py] - suby];
   1039                     g[x].push_back(y);
   1040                     g[y].push_back(x);
   1041                   }
   1042                   d.unite(px, py);
   1043                   prod *= fib[d.sz[py]];
   1044                 }
   1045               }
   1046               if (done) {
   1047                 break;
   1048               }
   1049               for (int j = left; j < ww - right; j++) {
   1050                 int x = (h - 1 - i) * ww + j;
   1051                 if (must[x]) {
   1052                   done = true;
   1053                   break;
   1054                 }
   1055                 int px = d.get(x);
   1056                 prod /= fib[d.sz[px]];
   1057                 d.sz[px] -= 1;
   1058                 prod *= fib[d.sz[px]];
   1059                 for (int y : g[x]) {
   1060                   if (!must[y]) {
   1061                     must[y] = true;
   1062                     int py = d.get(y);
   1063                     prod /= fib[d.sz[py]];
   1064                     d.sz[py] -= 1;
   1065                     prod *= fib[d.sz[py]];
   1066                   }
   1067                 }
   1068               }
   1069               if (done) {
   1070                 break;
   1071               }
   1072             }
   1073           }
   1074         }
   1075       }
   1076     }
   1077     cout << ans << '\n';
   1078   }
   1079   return 0;
   1080 }
   1081 ```