codeforces-scrape

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

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