2084.md (16724B)
1 Source: https://codeforces.com/blog/entry/141155 2 3 Thanks for participation! 4 5 [2084A - Max and Mod](/contest/2084/problem/A) 6 7 Idea: [zltzlt](/profile/zltzlt "International Grandmaster zltzlt") 8 9 **Hint 1** 10 11 By observing the example, we can see that there is no solution when $n$ is even. 12 13 **Solution** 14 15 Tutorial is loading... 16 17 **Implementation** 18 19 ``` 20 #include <bits/stdc++.h> 21 using namespace std; 22 23 int main() { 24 int T, n; 25 cin >> T; 26 while (T--) { 27 cin >> n; 28 if (n & 1) { 29 cout << n << ' '; 30 for (int i = 1; i < n; ++i) { 31 cout << i << " \n"[i == n - 1]; 32 } 33 } else { 34 cout << "-1\n"; 35 } 36 } 37 return 0; 38 } 39 ``` 40 41 [2084B - MIN = GCD](/contest/2084/problem/B) 42 43 Idea: [zltzlt](/profile/zltzlt "International Grandmaster zltzlt") 44 45 **Hint 1** 46 47 Consider the position of the minimum value after rearranging the sequence. 48 49 **Hint 2** 50 51 What kind of numbers should be placed on the $\min$ side, and what kind should be placed on the $\gcd$ side? 52 53 **Solution** 54 55 Tutorial is loading... 56 57 **Implementation** 58 59 ``` 60 #include <bits/stdc++.h> 61 using namespace std; 62 typedef long long ll; 63 64 int main() { 65 ios::sync_with_stdio(0); 66 cin.tie(0); 67 int T, n; 68 cin >> T; 69 while (T--) { 70 cin >> n; 71 vector<ll> a(n); 72 for (ll &x : a) { 73 cin >> x; 74 } 75 int p = min_element(a.begin(), a.end()) - a.begin(); 76 ll g = 0; 77 for (int i = 0; i < n; ++i) { 78 if (i != p && a[i] % a[p] == 0) { 79 g = __gcd(g, a[i]); 80 } 81 } 82 cout << (g == a[p] ? "Yes\n" : "No\n"); 83 } 84 return 0; 85 } 86 ``` 87 88 [2084C - You Soared Afar With Grace](/contest/2084/problem/C) 89 90 Idea: [CharlieV](/profile/CharlieV "International Grandmaster CharlieV") 91 92 **Hint 1** 93 94 Will the $b_i$ corresponding to a given $a_i$ change? 95 96 **Hint 2** 97 98 Individually place each pair corresponding to $(a_i, b_i)$ (i.e., $(b_i, a_i)$) at position $n - i + 1$. 99 100 **Solution** 101 102 Tutorial is loading... 103 104 **Implementation** 105 106 ``` 107 #include <bits/stdc++.h> 108 using namespace std; 109 110 const int maxn = 200100; 111 112 int n, a[maxn], b[maxn], m, p[maxn], ans[maxn][2]; 113 114 inline void work(int x, int y) { 115 if (x == y) { 116 return; 117 } 118 ans[++m][0] = x; 119 ans[m][1] = y; 120 swap(a[x], a[y]); 121 swap(p[a[x]], p[a[y]]); 122 swap(b[x], b[y]); 123 } 124 125 void solve() { 126 cin >> n; 127 for (int i = 1; i <= n; ++i) { 128 cin >> a[i]; 129 p[a[i]] = i; 130 } 131 for (int i = 1; i <= n; ++i) { 132 cin >> b[i]; 133 } 134 m = 0; 135 int x = 0; 136 for (int i = 1; i <= n; ++i) { 137 if (a[i] == b[i]) { 138 if (n % 2 == 0 || x) { 139 cout << "-1\n"; 140 return; 141 } 142 x = i; 143 } else if (b[p[b[i]]] != a[i]) { 144 cout << "-1\n"; 145 return; 146 } 147 } 148 if (n & 1) { 149 work(x, (n + 1) / 2); 150 } 151 for (int i = 1; i <= n / 2; ++i) { 152 work(p[b[i]], n - i + 1); 153 } 154 cout << m << '\n'; 155 for (int i = 1; i <= m; ++i) { 156 cout << ans[i][0] << ' ' << ans[i][1] << '\n'; 157 } 158 } 159 160 int main() { 161 ios::sync_with_stdio(0); 162 cin.tie(0); 163 int T; 164 cin >> T; 165 while (T--) { 166 solve(); 167 } 168 return 0; 169 } 170 ``` 171 172 [2084D - Arcology On Permafrost](/contest/2084/problem/D) 173 174 Idea: [zltzlt](/profile/zltzlt "International Grandmaster zltzlt") 175 176 **Hint 1** 177 178 Treat "at most $m$ operations" as "exactly $m$ operations". 179 180 **Hint 2** 181 182 What is the maximum value of $f(a)$? 183 184 **Hint 3** 185 186 Ensure that the distance between each pair of identical numbers is at least $k$. 187 188 **Solution** 189 190 Tutorial is loading... 191 192 **Implementation** 193 194 ``` 195 #include <bits/stdc++.h> 196 using namespace std; 197 198 int main() { 199 int T; 200 cin >> T; 201 while (T--) { 202 int n, m, k; 203 cin >> n >> m >> k; 204 for (int i = 0; i < n; ++i) { 205 cout << i % (n < (m + 1) * k ? k : n / (m + 1)) << " \n"[i == n - 1]; 206 } 207 } 208 return 0; 209 } 210 ``` 211 212 [2084E - Blossom](/contest/2084/problem/E) 213 214 Idea: [zltzlt](/profile/zltzlt "International Grandmaster zltzlt") 215 216 **Hint 1** 217 218 Transform the calculation method of $\operatorname{mex}$. 219 220 **Hint 2** 221 222 Try to come up with an $O(n^3)$ approach and then optimize it to $O(n^2)$. 223 224 **Solution** 225 226 Tutorial is loading... 227 228 **Implementation** 229 230 ``` 231 #include <bits/stdc++.h> 232 using namespace std; 233 234 const int maxn = 5050; 235 const int mod = 1000000007; 236 237 int n, a[maxn], fac[maxn], C[maxn][maxn], b[maxn], d[maxn][maxn]; 238 bool vis[maxn]; 239 240 void solve() { 241 cin >> n; 242 for (int i = 0; i <= n; ++i) { 243 vis[i] = 0; 244 for (int j = 0; j <= n; ++j) { 245 d[i][j] = 0; 246 } 247 } 248 fac[0] = 1; 249 for (int i = 1; i <= n; ++i) { 250 cin >> a[i]; 251 fac[i] = 1LL * fac[i - 1] * i % mod; 252 b[i] = b[i - 1] + (a[i] == -1); 253 if (a[i] != -1) { 254 vis[a[i]] = 1; 255 } 256 } 257 for (int i = 0; i <= n; ++i) { 258 C[i][0] = C[i][i] = 1; 259 for (int j = 1; j < i; ++j) { 260 C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod; 261 } 262 } 263 int mn1 = n; 264 for (int i = 1; i <= n; ++i) { 265 int mn2 = n; 266 for (int j = n; j >= i; --j) { 267 int x = b[j] - b[i - 1], y = min(mn1, mn2); 268 ++d[x][0]; 269 --d[x][y]; 270 if (a[j] != -1) { 271 mn2 = min(mn2, a[j]); 272 } 273 } 274 if (a[i] != -1) { 275 mn1 = min(mn1, a[i]); 276 } 277 } 278 for (int i = 0; i <= b[n]; ++i) { 279 for (int j = 1; j <= n; ++j) { 280 d[i][j] += d[i][j - 1]; 281 } 282 } 283 int ans = 0, cnt = 0; 284 for (int i = 0; i < n; ++i) { 285 cnt += (!vis[i]); 286 for (int j = cnt; j <= b[n]; ++j) { 287 ans = (ans + 1LL * C[j][cnt] * fac[cnt] % mod * fac[b[n] - cnt] % mod * d[j][i]) % mod; 288 } 289 } 290 cout << ans << '\n'; 291 } 292 293 int main() { 294 int T; 295 cin >> T; 296 while (T--) { 297 solve(); 298 } 299 return 0; 300 } 301 ``` 302 303 [2084F - Skyscape](/contest/2084/problem/F) 304 305 Idea: [zltzlt](/profile/zltzlt "International Grandmaster zltzlt") 306 Developer: [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq") 307 308 **Hint 1** 309 310 What kind of permutation $b$ is good? 311 312 **Hint 2** 313 314 Consider transforming this problem into a classic greedy algorithm problem. 315 316 **Solution** 317 318 Tutorial is loading... 319 320 **Implementation** 321 322 ``` 323 #include <bits/stdc++.h> 324 using namespace std; 325 326 const int maxn = 500100; 327 328 int n, a[maxn], b[maxn], c[maxn], p[maxn], q[maxn]; 329 330 struct node { 331 int r, x; 332 node(int a = 0, int b = 0) : r(a), x(b) {} 333 }; 334 335 inline bool operator < (const node &a, const node &b) { 336 return a.r > b.r || (a.r == b.r && a.x > b.x); 337 } 338 339 vector<node> vc[maxn]; 340 341 struct DS1 { 342 int c[maxn]; 343 344 inline void init() { 345 for (int i = 0; i <= n; ++i) { 346 c[i] = 0; 347 } 348 } 349 350 inline void update(int x, int d) { 351 for (int i = x; i <= n; i += (i & (-i))) { 352 c[i] = max(c[i], d); 353 } 354 } 355 356 inline int query(int x) { 357 int res = 0; 358 for (int i = x; i; i -= (i & (-i))) { 359 res = max(res, c[i]); 360 } 361 return res; 362 } 363 } T1; 364 365 struct DS2 { 366 int c[maxn]; 367 368 inline void init() { 369 for (int i = 0; i <= n; ++i) { 370 c[i] = n + 1; 371 } 372 } 373 374 inline void update(int x, int d) { 375 for (int i = x; i; i -= (i & (-i))) { 376 c[i] = min(c[i], d); 377 } 378 } 379 380 inline int query(int x) { 381 int res = n + 1; 382 for (int i = x; i <= n; i += (i & (-i))) { 383 res = min(res, c[i]); 384 } 385 return res; 386 } 387 } T2; 388 389 void solve() { 390 cin >> n; 391 for (int i = 1; i <= n; ++i) { 392 cin >> a[i]; 393 p[a[i]] = i; 394 q[i] = 0; 395 vector<node>().swap(vc[i]); 396 } 397 for (int i = 1; i <= n; ++i) { 398 cin >> b[i]; 399 if (b[i]) { 400 q[b[i]] = i; 401 } 402 } 403 T1.init(); 404 for (int i = 1; i <= n; ++i) { 405 if (q[i]) { 406 if (T1.query(p[i]) > q[i]) { 407 cout << "-1\n"; 408 return; 409 } 410 T1.update(p[i], q[i]); 411 } 412 } 413 T1.init(); 414 T2.init(); 415 for (int i = 1; i <= n; ++i) { 416 if (q[a[i]]) { 417 T1.update(a[i], q[a[i]]); 418 } else { 419 c[i] = T1.query(a[i]) + 1; 420 } 421 } 422 for (int i = n; i; --i) { 423 if (q[a[i]]) { 424 T2.update(a[i], q[a[i]]); 425 } else { 426 int r = T2.query(a[i]) - 1; 427 if (c[i] > r) { 428 cout << "-1\n"; 429 return; 430 } 431 vc[c[i]].emplace_back(r, a[i]); 432 } 433 } 434 priority_queue<node> pq; 435 for (int i = 1; i <= n; ++i) { 436 for (node u : vc[i]) { 437 pq.push(u); 438 } 439 if (!b[i]) { 440 if (pq.empty() || pq.top().r < i) { 441 cout << "-1\n"; 442 return; 443 } 444 b[i] = pq.top().x; 445 pq.pop(); 446 } 447 } 448 for (int i = 1; i <= n; ++i) { 449 cout << b[i] << " \n"[i == n]; 450 } 451 } 452 453 int main() { 454 ios::sync_with_stdio(0); 455 cin.tie(0); 456 int T; 457 cin >> T; 458 while (T--) { 459 solve(); 460 } 461 return 0; 462 } 463 ``` 464 465 [2084G1 - Wish Upon a Satellite (Easy Version)](/contest/2084/problem/G1) 466 467 Idea: [zltzlt](/profile/zltzlt "International Grandmaster zltzlt") 468 469 **Hint 1** 470 471 What is the value of $f(c)$? 472 473 **Hint 2** 474 475 Try DP. 476 477 **Solution** 478 479 Tutorial is loading... 480 481 **Implementation** 482 483 ``` 484 #include <bits/stdc++.h> 485 using namespace std; 486 typedef long long ll; 487 488 void solve() { 489 int n; 490 cin >> n; 491 vector<int> a(n + 1, -1); 492 vector< vector<ll> > f(n + 1, vector<ll>(n + 1, 1e18)); 493 for (int i = 1, x; i <= n; ++i) { 494 cin >> x; 495 if (x) { 496 a[x] = i & 1; 497 } 498 } 499 if (a[1] != 1) { 500 f[1][0] = 0; 501 } 502 if (a[1] != 0) { 503 f[1][1] = 0; 504 } 505 for (int i = 1; i < n; ++i) { 506 for (int j = 0; j <= i; ++j) { 507 f[i][j] += j * (n / 2 - (i - j)) + (i - j) * ((n + 1) / 2 - j); 508 if (a[i + 1] != 1) { 509 f[i + 1][j] = min(f[i + 1][j], f[i][j]); 510 } 511 if (a[i + 1] != 0) { 512 f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j]); 513 } 514 } 515 } 516 ll ans = -f[n][(n + 1) / 2]; 517 for (int i = 1; i <= n; ++i) { 518 ans += i * i; 519 } 520 cout << ans << '\n'; 521 } 522 523 int main() { 524 int T; 525 cin >> T; 526 while (T--) { 527 solve(); 528 } 529 return 0; 530 } 531 ``` 532 533 [2084G2 - Wish Upon a Satellite (Hard Version)](/contest/2084/problem/G2) 534 535 Idea: [zltzlt](/profile/zltzlt "International Grandmaster zltzlt") 536 537 **Hint 1** 538 539 Optimize the DP in G1. 540 541 **Solution** 542 543 Tutorial is loading... 544 545 **Implementation** 546 547 ``` 548 #include <bits/stdc++.h> 549 using namespace std; 550 typedef long long ll; 551 552 const int maxn = 500100; 553 554 int n, a[maxn]; 555 mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); 556 557 int p[maxn], nt, ls[maxn], rs[maxn], sz[maxn]; 558 bool vis[maxn]; 559 560 struct vec { 561 ll a0, a1, a2; 562 vec(ll a = 0, ll b = 0, ll c = 0) : a0(a), a1(b), a2(c) {} 563 } val[maxn]; 564 565 struct mat { 566 ll a00, a01, a02, a10, a11, a12, a20, a21, a22; 567 mat(ll a = 0, ll b = 0, ll c = 0, ll d = 0, ll e = 0, ll f = 0, ll g = 0, ll h = 0, ll i = 0) : a00(a), a01(b), a02(c), a10(d), a11(e), a12(f), a20(g), a21(h), a22(i) {} 568 } I, tag[maxn]; 569 570 inline vec operator * (const vec &a, const mat &b) { 571 vec res; 572 res.a0 = a.a0 * b.a00 + a.a1 * b.a10 + a.a2 * b.a20; 573 res.a1 = a.a0 * b.a01 + a.a1 * b.a11 + a.a2 * b.a21; 574 res.a2 = a.a0 * b.a02 + a.a1 * b.a12 + a.a2 * b.a22; 575 return res; 576 } 577 578 inline mat operator * (const mat &a, const mat &b) { 579 mat res; 580 res.a00 = a.a00 * b.a00 + a.a01 * b.a10 + a.a02 * b.a20; 581 res.a01 = a.a00 * b.a01 + a.a01 * b.a11 + a.a02 * b.a21; 582 res.a02 = a.a00 * b.a02 + a.a01 * b.a12 + a.a02 * b.a22; 583 res.a10 = a.a10 * b.a00 + a.a11 * b.a10 + a.a12 * b.a20; 584 res.a11 = a.a10 * b.a01 + a.a11 * b.a11 + a.a12 * b.a21; 585 res.a12 = a.a10 * b.a02 + a.a11 * b.a12 + a.a12 * b.a22; 586 res.a20 = a.a20 * b.a00 + a.a21 * b.a10 + a.a22 * b.a20; 587 res.a21 = a.a20 * b.a01 + a.a21 * b.a11 + a.a22 * b.a21; 588 res.a22 = a.a20 * b.a02 + a.a21 * b.a12 + a.a22 * b.a22; 589 return res; 590 } 591 592 inline void init() { 593 for (int i = 0; i <= nt; ++i) { 594 p[i] = ls[i] = rs[i] = sz[i] = 0; 595 val[i] = vec(); 596 tag[i] = I; 597 vis[i] = 0; 598 } 599 nt = 0; 600 } 601 602 inline int newnode(ll x, ll y) { 603 int u = ++nt; 604 p[u] = rnd(); 605 ls[u] = rs[u] = 0; 606 sz[u] = 1; 607 val[u] = vec(x, y, 1); 608 tag[u] = I; 609 vis[u] = 0; 610 return u; 611 } 612 613 inline void pushup(int x) { 614 sz[x] = sz[ls[x]] + sz[rs[x]] + 1; 615 } 616 617 inline void pushtag(int x, const mat &y) { 618 if (!x) { 619 return; 620 } 621 val[x] = val[x] * y; 622 tag[x] = tag[x] * y; 623 vis[x] = 1; 624 } 625 626 inline void pushdown(int x) { 627 if (!vis[x]) { 628 return; 629 } 630 pushtag(ls[x], tag[x]); 631 pushtag(rs[x], tag[x]); 632 vis[x] = 0; 633 tag[x] = I; 634 } 635 636 void split(int u, int &x, int &y) { 637 if (!u) { 638 x = y = 0; 639 return; 640 } 641 pushdown(u); 642 if (val[u].a0 < 0) { 643 x = u; 644 split(rs[u], rs[u], y); 645 } else { 646 y = u; 647 split(ls[u], x, ls[u]); 648 } 649 pushup(u); 650 } 651 652 int merge(int x, int y) { 653 if (!x || !y) { 654 return x | y; 655 } 656 pushdown(x); 657 pushdown(y); 658 if (p[x] < p[y]) { 659 rs[x] = merge(rs[x], y); 660 pushup(x); 661 return x; 662 } else { 663 ls[y] = merge(x, ls[y]); 664 pushup(y); 665 return y; 666 } 667 } 668 669 ll f[maxn], tot; 670 671 void dfs(int u) { 672 if (!u) { 673 return; 674 } 675 pushdown(u); 676 dfs(ls[u]); 677 f[++tot] = val[u].a0; 678 dfs(rs[u]); 679 } 680 681 void solve() { 682 cin >> n; 683 for (int i = 1; i <= n; ++i) { 684 a[i] = -1; 685 } 686 for (int i = 1, x; i <= n; ++i) { 687 cin >> x; 688 if (x) { 689 a[x] = (i & 1); 690 } 691 } 692 init(); 693 int rt = 0; 694 ll l = 0, r = 0, x = 0; 695 if (a[1] == 1) { 696 l = r = 1; 697 } else if (a[1] == -1) { 698 rt = newnode(0, 1); 699 r = 1; 700 } 701 for (ll i = 1; i < n; ++i) { 702 x += l * l * 2 + (-i - i - (n & 1)) * l + i * ((n + 1) / 2); 703 pushtag(rt, mat(1, 0, 0, 4, 1, 0, -i - i - (n & 1) - 2, 0, 1)); 704 if (a[i + 1] == 1) { 705 pushtag(rt, mat(1, 0, 0, 0, 1, 0, 0, 1, 1)); 706 ++l; 707 ++r; 708 } else if (a[i + 1] == -1) { 709 int u, v; 710 split(rt, u, v); 711 pushtag(v, mat(1, 0, 0, 0, 1, 0, 0, 1, 1)); 712 rt = merge(merge(u, newnode(0, l + 1 + sz[u])), v); 713 ++r; 714 } 715 } 716 tot = 0; 717 dfs(rt); 718 ll ans = -x; 719 for (int i = 1; i <= (n + 1) / 2 - l; ++i) { 720 ans -= f[i]; 721 } 722 for (ll i = 1; i <= n; ++i) { 723 ans += i * i; 724 } 725 cout << ans << '\n'; 726 } 727 728 int main() { 729 ios::sync_with_stdio(0); 730 cin.tie(0); 731 I.a00 = I.a11 = I.a22 = 1; 732 int T; 733 cin >> T; 734 while (T--) { 735 solve(); 736 } 737 return 0; 738 } 739 ``` 740 741 [2084H - Turtle and Nediam 2](/contest/2084/problem/H) 742 743 Idea: [zltzlt](/profile/zltzlt "International Grandmaster zltzlt") 744 Developer: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") 745 746 **Hint 1** 747 748 Extract the longest contiguous segments in $s$ where the values remain the same. 749 750 **Hint 2** 751 752 According to greedy matching, an $O(n^2)$ DP can be obtained. 753 754 **Hint 3** 755 756 Optimize the DP from $O(n^2)$ to $O(n)$. 757 758 **Solution** 759 760 Tutorial is loading... 761 762 **Implementation 1** 763 764 ``` 765 #include <bits/stdc++.h> 766 using namespace std; 767 typedef long long ll; 768 769 const int maxn = 2000100; 770 const ll mod = 1000000007; 771 772 int n, a[maxn], m, nxt[maxn], stk[maxn], top; 773 ll f[maxn], d[maxn]; 774 char s[maxn]; 775 776 inline ll calc() { 777 top = 0; 778 for (int i = m; i >= 1; i -= 2) { 779 while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) { 780 --top; 781 } 782 nxt[i] = stk[top]; 783 stk[++top] = i; 784 } 785 top = 0; 786 for (int i = m - 1; i >= 1; i -= 2) { 787 while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) { 788 --top; 789 } 790 nxt[i] = stk[top]; 791 stk[++top] = i; 792 } 793 for (int i = 1; i < m; ++i) { 794 f[i] = d[i] = 0; 795 } 796 f[1] = a[1]; 797 for (int i = 3; i < m; i += 2) { 798 f[i] = 1; 799 } 800 ll ans = 0; 801 for (int i = 1; i < m; ++i) { 802 if (i >= 3) { 803 d[i] = (d[i] + d[i - 2]) % mod; 804 } 805 f[i] = (f[i] + d[i]) % mod; 806 int j = i + 1, x = 0; 807 while (j < m) { 808 int k = (nxt[j] ? nxt[j] : m); 809 f[j] = (f[j] + f[i] * (a[j] - x)) % mod; 810 x = a[j] + (k - j) / 2 - 1; 811 d[j + 2] = (d[j + 2] + f[i]) % mod; 812 d[k] = (d[k] - f[i] + mod) % mod; 813 j = k; 814 } 815 if ((m - i) & 1) { 816 ans = (ans + f[i]) % mod; 817 } 818 } 819 return ans * a[m] % mod; 820 } 821 822 void solve() { 823 cin >> n >> s; 824 m = 0; 825 for (int i = 0, j = 0; i < n; i = (++j)) { 826 while (j + 1 < n && s[j + 1] == s[i]) { 827 ++j; 828 } 829 a[++m] = j - i + 1; 830 } 831 if (m == 1) { 832 cout << n - 1 << '\n'; 833 return; 834 } 835 if (m == 2) { 836 cout << 1LL * a[1] * a[2] % mod << '\n'; 837 return; 838 } 839 ll ans = calc(); 840 --m; 841 for (int i = 1; i <= m; ++i) { 842 a[i] = a[i + 1]; 843 } 844 a[1] = 1; 845 ans = (ans + calc()) % mod; 846 cout << ans << '\n'; 847 } 848 849 int main() { 850 ios::sync_with_stdio(0); 851 cin.tie(0); 852 int T; 853 cin >> T; 854 while (T--) { 855 solve(); 856 } 857 return 0; 858 } 859 ``` 860 861 **Implementation 2** 862 863 ``` 864 #include <bits/stdc++.h> 865 using namespace std; 866 typedef long long ll; 867 868 const int maxn = 2000100; 869 const ll mod = 1000000007; 870 871 int n, a[maxn], m, nxt[maxn], stk[maxn], top; 872 ll f[maxn], g[maxn], d[maxn]; 873 char s[maxn]; 874 875 inline ll calc() { 876 top = 0; 877 for (int i = m; i >= 1; i -= 2) { 878 while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) { 879 --top; 880 } 881 nxt[i] = stk[top]; 882 stk[++top] = i; 883 } 884 top = 0; 885 for (int i = m - 1; i >= 1; i -= 2) { 886 while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) { 887 --top; 888 } 889 nxt[i] = stk[top]; 890 stk[++top] = i; 891 } 892 for (int i = 1; i < m; ++i) { 893 f[i] = g[i] = d[i] = 0; 894 } 895 f[1] = a[1]; 896 for (int i = 3; i < m; i += 2) { 897 f[i] = 1; 898 } 899 ll ans = 0; 900 for (int i = 1; i < m; ++i) { 901 if (i >= 3) { 902 d[i] = (d[i] + d[i - 2]) % mod; 903 } 904 f[i] = (f[i] + d[i]) % mod; 905 g[i + 1] = (g[i + 1] + f[i]) % mod; 906 f[i + 1] = (f[i + 1] + f[i] * a[i + 1]) % mod; 907 d[i + 2] = (d[i + 2] + g[i]) % mod; 908 if (nxt[i]) { 909 g[nxt[i]] = (g[nxt[i]] + g[i]) % mod; 910 f[nxt[i]] = (f[nxt[i]] + g[i] * (a[nxt[i]] - a[i] - (nxt[i] - i) / 2 + 1)) % mod; 911 d[nxt[i]] = (d[nxt[i]] - g[i] + mod) % mod; 912 } 913 if ((m - i) & 1) { 914 ans = (ans + f[i]) % mod; 915 } 916 } 917 return ans * a[m] % mod; 918 } 919 920 void solve() { 921 cin >> n >> s; 922 m = 0; 923 for (int i = 0, j = 0; i < n; i = (++j)) { 924 while (j + 1 < n && s[j + 1] == s[i]) { 925 ++j; 926 } 927 a[++m] = j - i + 1; 928 } 929 if (m == 1) { 930 cout << n - 1 << '\n'; 931 return; 932 } 933 if (m == 2) { 934 cout << 1LL * a[1] * a[2] % mod << '\n'; 935 return; 936 } 937 ll ans = calc(); 938 --m; 939 for (int i = 1; i <= m; ++i) { 940 a[i] = a[i + 1]; 941 } 942 a[1] = 1; 943 ans = (ans + calc()) % mod; 944 cout << ans << '\n'; 945 } 946 947 int main() { 948 ios::sync_with_stdio(0); 949 cin.tie(0); 950 int T; 951 cin >> T; 952 while (T--) { 953 solve(); 954 } 955 return 0; 956 } 957 ```