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