codeforces-scrape

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

2053.md (56890B)


      1 Source: https://codeforces.com/blog/entry/136455
      2 
      3 Thank you for participating in this round! Problems A and G are authored by [Cocoly1990](/profile/Cocoly1990 "Grandmaster Cocoly1990") and the rest by me.
      4 
      5 Currently, I'm not sure if the editorials are fine enough. Please feel free to tell me where I can improve.
      6 
      7 **Rating Predictions**
      8 
      9 |  | A | B | C | D | E | F | G | H | I |
     10 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
     11 | [_istil](/profile/_istil "International Grandmaster _istil") | 800 | 1200 | 1400 | 1700 | 1900 | 2500 | [2800, 3300] | 3200 | [800, 3000] |
     12 | [Cocoly1990](/profile/Cocoly1990 "Grandmaster Cocoly1990") | 800 | 1300 |  |  |  |  | 3000 |  |  |
     13 | [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") | 800 | 1200 | ? | 1800 |  | 2500 | 3000 | 3000 | 3500 |
     14 | [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225") | 800 | 1300 | 1600 | 1900 | 2100 | 2400 | 2800 | 2900 | [2500, 3200] |
     15 | [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") | 900 | 1200 | 1400 | 2000 | 2100 | 2500 | 3000 |  | 3200 |
     16 | [Caylex](/profile/Caylex "International Master Caylex") | 800 | 1300 | 1500 | 1900 | 2200 | 2600 | [2500, 3100] |  |  |
     17 | [tzl_Dedicatus545](/profile/tzl_Dedicatus545 "Master tzl_Dedicatus545") | 800 | 1000 | 1100 | 1400 |  | 2300 |  |  |  |
     18 | [PaciukZvichainyi](/profile/PaciukZvichainyi "Candidate Master PaciukZvichainyi") | 800 | 1200 | 1500 | 1800 | 2100 | 2500 |  |  |  |
     19 | [doujinshi_master](/profile/doujinshi_master "Candidate Master doujinshi_master") | 800 | 1200 | 1500 | 1800 |  |  |  |  |  |
     20 | [juan_123](/profile/juan_123 "International Master juan_123") | 800 | [800, 1100] | 1000 | 1700 |  | 2400 | 2800 |  | [2700, 3500] |
     21 | [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") | 800 | 1300 | 1400 | 1700 |  | 2500 | 3100 | 2700 |  |
     22 | [SkyWave2022](/profile/SkyWave2022 "Specialist SkyWave2022") | 800 | 1200 | 1600 | [1600, 1900] |  |  |  |  |  |
     23 | [fossil823656](/profile/fossil823656 "Master fossil823656") | 800 | 1200 | 1500 | 1800 | 2100 |  |  |  |  |
     24 | [FFTotoro](/profile/FFTotoro "Candidate Master FFTotoro") | 800 | 1200 | 1400 | 1900 | 1900 | 2400 | 2900 |  |
     25 
     26 [2053A - Tender Carpenter](/contest/2053/problem/A "Good Bye 2024: 2025 is NEAR")
     27 
     28 **Hint 1**
     29 
     30 Can you find a partition that is always valid?
     31 
     32 **Hint 2**
     33 
     34 Suppose you are given a set $S$. How do you judge whether $S$ is *stable* in $\mathcal O(\lvert S\rvert)$?
     35 
     36 **Hint 3**
     37 
     38 Are sets that are very large really necessary?
     39 
     40 **Solution**
     41 
     42 Note that: we always have a partition like $[a_1], [a_2], \dots, [a_n]$, since $(x, x, x)$ always forms a non-degenerate (equilateral) triangle.
     43 
     44 We focus on the second partition scheme in which not all continuous subsegments have a length of $1$. One can also note that if a set $S$ is *stable* then for all $T \subsetneq S$ ($T \neq \varnothing$), $T$ is also *stable*.
     45 
     46 * Short proof: If $\exists u, v, w \in T$ such that $(u, v, w)$ doesn't form a non-degenerate triangle, therefore $u, v, w \in S$ so it is concluded that $S$ is not *stable*. Contradiction!
     47 
     48 If such a partition exists, we can always split long continuous subsegments into shorter parts, while the partition remains valid. Therefore, it's enough to check the case in which there is one subsegment of length $2$ and the rest of length $1$. So, we should output `NO` if and only if for all $1 \leq i \lt n$, $2\min(a_i, a_{i+1}) \leq \max(a_i, a_{i+1})$.
     49 
     50 **Code (C++)**
     51 
     52 ```
     53 #include <bits/stdc++.h>
     54  
     55 #define MAXN 1001
     56 int a[MAXN];
     57 void solve() {
     58 	int n; std::cin >> n;
     59 	for (int i = 1; i <= n; ++i) std::cin >> a[i];
     60 	for (int i = 1; i < n; ++i) if (2 * std::min(a[i], a[i + 1]) > std::max(a[i], a[i + 1])) 
     61 		{ std::cout << "YES\n"; return; }
     62 	std::cout << "NO\n";
     63 }
     64  
     65 int main() {
     66 	std::ios::sync_with_stdio(false);
     67 	std::cin.tie(nullptr), std::cout.tie(nullptr);
     68 	int t; std::cin >> t; while (t--) solve(); return 0;
     69 }
     70 ```
     71 
     72 **Rate the Problem**
     73 
     74 * Amazing problem:
     75 * Good problem:
     76 * Average problem:
     77 * Bad problem:
     78 * Didn't solve:
     79 
     80 [2053B - Outstanding Impressionist](/contest/2053/problem/B "Good Bye 2024: 2025 is NEAR")
     81 
     82 **Hint 1**
     83 
     84 What if for all $1 \leq i \leq n$, $l_i \ne r_i$ holds? How do you prove it?
     85 
     86 **Hint 2**
     87 
     88 Use prefix sums or similar to optimize your solution.
     89 
     90 **Solution**
     91 
     92 For each $1 \leq i \leq n$, for each $l_i \leq x \leq r_i$, we want to check if it is okay for impression $i$ being *unique* at the value of $x$. Note that: for each $j \neq i$, we can always switch $w_j$ to a value different from $x$ if $l_j \neq r_j$, since there are at least two options. Therefore, it is impossible if and only if there exists a $1 \leq j \leq n$ with $j \neq i$ such that $l_j = r_j = x$.
     93 
     94 Let's record $a_i$ as the number of different $k$ satisfying $1 \leq k \leq n$ and $l_k = r_k = i$. If $l_i \neq r_i$, then we say impression $i$ **cannot** be made *unique* if and only if for all $l_i \leq k \leq r_i$, $a_k \geq 1$; otherwise ($l_i = r_i$), it cannot be *unique* if and only if $a_{l_i} \geq 2$.
     95 
     96 This can all be checked quickly within a prefix sum, so the overall time complexity is $\mathcal O(\sum n)$.
     97 
     98 **Code (C++)**
     99 
    100 ```
    101 #include <bits/stdc++.h>
    102  
    103 #define MAXN 400001
    104 int l[MAXN], r[MAXN], sum[MAXN], cnt[MAXN];
    105 void solve() {
    106 	int n; std::cin >> n;
    107 	for (int i = 1; i <= 2 * n; ++i) sum[i] = cnt[i] = 0;
    108 	for (int i = 1; i <= n; ++i) {
    109 		std::cin >> l[i] >> r[i];
    110 		if (l[i] == r[i]) sum[l[i]] = 1, ++cnt[l[i]];
    111 	}
    112 	for (int i = 2; i <= 2 * n; ++i) sum[i] += sum[i - 1];
    113 	for (int i = 1; i <= n; ++i) 
    114 		std::cout << ((l[i] == r[i] ? cnt[l[i]] <= 1 : sum[r[i]] - sum[l[i] - 1] < r[i] - l[i] + 1) ? "1" : "0");
    115 	std::cout << '\n';
    116 }
    117 int main() {
    118 	std::ios::sync_with_stdio(false);
    119 	std::cin.tie(nullptr), std::cout.tie(nullptr);
    120 	int t; std::cin >> t; while (t--) solve(); return 0;
    121 }
    122 ```
    123 
    124 **Rate the Problem**
    125 
    126 * Amazing problem:
    127 * Good problem:
    128 * Average problem:
    129 * Bad problem:
    130 * Didn't solve:
    131 
    132 [2053C - Bewitching Stargazer](/contest/2053/problem/C "Good Bye 2024: 2025 is NEAR")
    133 
    134 **Hint 1**
    135 
    136 Process many segments simultaneously. What kind of segments do we process at a time?
    137 
    138 **Hint 2**
    139 
    140 The length.
    141 
    142 **Solution**
    143 
    144 The point that must be noted is: that if we call the process of splitting a large segment into two smaller segments a round, then all segments are of the same length when the $i$-th round of the observation is conducted; and, the number of rounds does not exceed $\mathcal O(\log n)$. The $k$ restriction is equivalent to specifying that only a certain prefix of rounds is computed.
    145 
    146 Here are some different approaches:
    147 
    148 * (Most succinctly) Note that the distribution of segments after round 1 is centrally symmetric; Also, $x$ and $y$ being centrally symmetric implies that $x + y = n + 1$, so it is simple to calculate by simulating the number of segments and the length directly.
    149 * If a segment $[l, r]$ is split into $[l, m - 1]$ and $[m + 1, r]$, its left endpoint sum changes from $l$ to $2l + \frac{r - l}{2} + 1$, and since $(r - l)$ is fixed, the sum of the left endpoints of all segments can be maintained similarly.
    150 * The following recursive method also works: the answer to $n$ can be recovered by the answer to $\lfloor \frac{n}{2} \rfloor$. The time complexity is $\mathcal O(t\log n)$.
    151 
    152 **Code (C++)**
    153 
    154 This is written by [_TernaryTree_](/profile/_TernaryTree_ "Candidate Master _TernaryTree_").
    155 
    156 ```
    157 #include <bits/stdc++.h>
    158 #define int long long
    159  
    160 using namespace std;
    161  
    162 int T;
    163 int n, k;
    164  
    165 signed main() {
    166 	cin >> T;
    167 	while (T--) {
    168 		cin >> n >> k;
    169 		int mul = n + 1, sum = 0, cur = 1;
    170 		while (n >= k) {
    171 			if (n & 1) sum += cur;
    172 			n >>= 1;
    173 			cur <<= 1;
    174 		}
    175 		cout << mul * sum / 2 << endl;
    176 	}
    177 	return 0;
    178 }
    179 ```
    180 
    181 **Rate the Problem**
    182 
    183 * Amazing problem:
    184 * Good problem:
    185 * Average problem:
    186 * Bad problem:
    187 * Didn't solve:
    188 
    189 [2053D - Refined Product Optimality](/contest/2053/problem/D "Good Bye 2024: 2025 is NEAR")
    190 
    191 **Hint 1**
    192 
    193 What if $q = 0$?
    194 
    195 **Hint 2**
    196 
    197 How do you keep the array sorted?
    198 
    199 **Solution**
    200 
    201 The problem makes no difference when both $a$ and $b$ can be rearranged. Let the rearranged arrays of $a$ and $b$ be $c$ and $d$ respectively.
    202 
    203 If $q = 0$, we can write $c$ as $\operatorname{SORTED}(a_1, a_2 \ldots, a_n)$ and $d$ as $\operatorname{SORTED}(b_1, b_2 \ldots, b_n)$. It can be proved that this reaches the maximum value: if not so, then
    204 
    205 * There must be some pair $(i, j)$ such that $c_i \lt c_j, d_i \gt d_j$.
    206 * Since $\min(c_i, d_i) \cdot \min(c_j, d_j) = c_i \cdot \min(c_j, d_j) \leq c_i \cdot \min(c_j, d_i) = \min(c_i, d_j) \cdot \min(c_j, d_i)$, we can swap $d_i$ and $d_j$, and the product does not decrease.
    207 
    208 Consider the modification, which is a single element increment by $1$. Without loss of generality, let $c_x$ be increased by $1$ (and the processing method for $d$ is the same). If $c_x \lt c_{x+1}$, then after the modification $c_x \leq c_{x+1}$, which would be fine. Otherwise, we can modify the array $c$ in the form of a single round of "Insertion Sort": We continuously swap $c_x$ and $c_{x+1}$, $x \gets x + 1$, until $c_x \lt c_{x+1}$ (or $x = n$), and thus the array remains sorted after the increment.
    209 
    210 In fact, the swap operation does nothing in the above process: in these cases, $c_x = c_{x+1}$ holds! So we can just set $x'$ as the maximum $k$ such that $c_k = c_x$, and then increase $c_{x'}$ by $1$, after which $c$ is still sorted. The $k$ can be found with a naive binary search, so the problem is solved in $\mathcal O(n\log n + q(\log p + \log n))$ per test case.
    211 
    212 **Code (C++)**
    213 
    214 ```
    215 #include <bits/stdc++.h>
    216  
    217 constexpr int MOD = 998244353;
    218 int qpow(int a, int x = MOD - 2) {
    219 	int res = 1;
    220 	for (; x; x >>= 1, a = 1ll * a * a % MOD) if (x & 1) res = 1ll * res * a % MOD;
    221 	return res;
    222 }
    223  
    224 #define MAXN 200001
    225 int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
    226 void solve() {
    227 	int n, q, res = 1; std::cin >> n >> q;
    228 	for (int i = 1; i <= n; ++i) std::cin >> a[i], c[i] = a[i];
    229 	for (int i = 1; i <= n; ++i) std::cin >> b[i], d[i] = b[i];
    230 	std::sort(c + 1, c + n + 1), std::sort(d + 1, d + n + 1);
    231 	for (int i = 1; i <= n; ++i) res = 1ll * res * std::min(c[i], d[i]) % MOD;
    232 	std::cout << res << " \n"[q == 0];
    233 	for (int i = 1, op, x; i <= q; ++i) {
    234 		std::cin >> op >> x;
    235 		if (op == 1) {
    236 			int p = std::upper_bound(c + 1, c + n + 1, a[x]) - c - 1;
    237 			if (c[p] < d[p]) res = 1ll * res * qpow(c[p]) % MOD * (c[p] + 1) % MOD;
    238 			++a[x], ++c[p];
    239 		} else {
    240 			int p = std::upper_bound(d + 1, d + n + 1, b[x]) - d - 1;
    241 			if (d[p] < c[p]) res = 1ll * res * qpow(d[p]) % MOD * (d[p] + 1) % MOD;
    242 			++b[x], ++d[p];
    243 		}
    244 		std::cout << res << " \n"[i == q];
    245 	}
    246 }
    247  
    248 int main() {
    249 	std::ios::sync_with_stdio(false);
    250 	std::cin.tie(nullptr), std::cout.tie(nullptr);
    251 	int t; std::cin >> t; while (t--) solve(); return 0;
    252 }
    253 ```
    254 
    255 **Rate the Problem**
    256 
    257 * Amazing problem:
    258 * Good problem:
    259 * Average problem:
    260 * Bad problem:
    261 * Didn't solve:
    262 
    263 [2053E - Resourceful Caterpillar Sequence](/contest/2053/problem/E "Good Bye 2024: 2025 is NEAR")
    264 
    265 **Hint 1**
    266 
    267 Suppose somebody wins. In which round does he or she win?
    268 
    269 **Hint 2**
    270 
    271 A player can always undo what his opponent did in the previous turn.
    272 
    273 **Hint 3**
    274 
    275 Can you find the necessary and sufficient condition for $(p, q)$ to be a caterpillar that makes Aron win?
    276 
    277 **Solution**
    278 
    279 Denote Nora's first move as round $1$, Aron's first move as round $2$, and so on. Suppose a player does not have a winning strategy in the $k$-th round, but he or she has a winning strategy in the $(k + 2)$-th round — it can be shown impossible because the other player can always withdraw the last move of another player so that the status is the same as it was before the $k$-th round.
    280 
    281 Therefore: if a player wins in the $k$-th round, we claim that $k \leq 2$.
    282 
    283 Given $p, q$, let's determine who will eventually win the game.
    284 
    285 1. If both $p$ and $q$ are leaves, the result is a tie.
    286 2. If $p$ is a leaf while $q$ is not, Nora wins.
    287 3. If $q$ is a leaf while $p$ is not, Aron wins.
    288 4. If neither $p$ nor $q$ is a leaf:
    289    * Can $k = 1$? Nora wins if and only if $p$ is adjacent to a leaf.
    290    * Can $k = 2$? Aron wins if and only if $p$ is not adjacent to a leaf, and $f(p, q)$ is adjacent to a leaf.
    291    * Otherwise, the result is a tie.
    292 
    293 The counting part can also be solved easily in $\mathcal O(n)$. Denote $c$ as the number of leaves. The initial answer would be $c \cdot (n - c)$, considering the third case. For the fourth case, we can enumerate $m = f(p, q)$, which is adjacent to at least one leaf. Given $m$, $q$ must be a non-leaf neighbor of $m$, and let the number of different $q$ be $k$. For each of the potential $p$, which is a non-leaf node whose neighbors are all non-leaf nodes too, it is computed exactly $k - 1$ times for all the $k$ candidates of $q$ (since $m$ must be on the simple path from $p$ to $q$), so the extra contributions are easy to calculate. (If you do not think that much, you can use some simple DP, which I will not elaborate here.)
    294 
    295 **Code (C++)**
    296 
    297 ```
    298 #include <bits/stdc++.h>
    299 
    300 #define MAXN 200001
    301 std::vector<int> g[MAXN];
    302 inline int deg(int u) { return g[u].size(); }
    303 
    304 int d[MAXN];
    305 void solve() {
    306 	int n; std::cin >> n; long long ans = 0;
    307 	for (int i = 1, u, v; i < n; ++i) {
    308 		std::cin >> u >> v;
    309 		g[u].push_back(v), g[v].push_back(u);
    310 	}
    311 	int c1 = 0, c2 = 0;
    312 	for (int i = 1; i <= n; ++i) c1 += (deg(i) == 1);
    313 	ans += 1ll * c1 * (n - c1);
    314 	for (int i = 1; i <= n; ++i) if (deg(i) > 1) {
    315 		for (int v : g[i]) d[i] += (deg(v) > 1);
    316 		c2 += (d[i] == deg(i));
    317 	}
    318 	for (int m = 1; m <= n; ++m) if (deg(m) > 1 && d[m] != deg(m)) 
    319 		ans += 1ll * c2 * (d[m] - 1);
    320 	std::cout << ans << '\n';
    321 	for (int i = 1; i <= n; ++i) 
    322 		(std::vector<int>()).swap(g[i]), d[i] = 0;
    323 }
    324 
    325 int main() {
    326 	std::ios::sync_with_stdio(false);
    327 	std::cin.tie(nullptr), std::cout.tie(nullptr);
    328 	int t; std::cin >> t; while (t--) solve(); return 0;
    329 }
    330 ```
    331 
    332 **Rate the Problem**
    333 
    334 * Amazing problem:
    335 * Good problem:
    336 * Average problem:
    337 * Bad problem:
    338 * Didn't solve:
    339 
    340 [2053F - Earnest Matrix Complement](/contest/2053/problem/F "Good Bye 2024: 2025 is NEAR")
    341 
    342 Special thanks to [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225") for implementing a correct MCS ~~ahead of me~~, and [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") for generating the test data for this problem.
    343 
    344 **Hint 1**
    345 
    346 What are we going to fill into the matrix? In other words, is there any relationship between the filed numbers?
    347 
    348 **Hint 2**
    349 
    350 Try to come up with a naive DP solution that works in large time complexity, such as $\mathcal O(nk^2)$.
    351 
    352 **Hint 3**
    353 
    354 For many different numbers between two consecutive rows, however, the transition is almost the same.
    355 
    356 **Hint 4**
    357 
    358 If $x' = \max(a, x + b)$ and $x'' = \max(c, x' + d)$, then $x'' = \max(\max(a + d, c), x + b + d)$.
    359 
    360 **Solution**
    361 
    362 > **Conclusion**: For each row, an optimal solution exists, such that the newly filled-in numbers are the same.
    363 
    364 * **Proof**: Consider fixing the rows $i - 1$ and $i + 1$, and observe all the newly filled-in numbers at row $i$. Then a new number $u$ brings a contribution of $c_{u, i-1} + c_{u, i+1}$, and it is clear that there exists a scheme that takes the maximum value such that all the $u$ filled in are equal. Adjusting for each row leads to the above conclusion.
    365 
    366 Consider dp. Let $f_{i,j}$ denote the maximum contribution that can be achieved between the first $i$ rows **(ignoring the initial contribution)** when the empty elements in the $i$-th row are filled with $j$. Let $c_i$ be the number of $-1$ numbers in the $i$-th row, and $d_{i,j}$ denote the number of elements $j$ in the $i$-th row initially.
    367 
    368 The transfer should be as follows:
    369 
    370 $f_{i, j} = \max(\max\limits_{1 \leq w \leq k}(f_{i-1, w} + c_i \cdot d_{i-1, w} + c_{i-1} \cdot d_{i-1, j}), f_{i-1, j} + (d_{i, j} + c_i) \cdot (d_{i-1, j} + c_{i-1}) - d_{i, j}d_{i-1, j}).$
    371 
    372 In addition to being able to optimize the above transition to $\mathcal O(nk)$, the present problem in a matrix has a good property. Specifically, for the same $i$, there are only $\mathcal O(m)$ values of $j$ such that $d_{i,j} \neq 0$!
    373 
    374 If $d_{i,j} = 0$ and $d_{i-1, j} = 0$, the original transfer can be viewed as
    375 
    376 $f_{i,j} = \max(\max\limits_{1 \leq w \leq k}(f_{i-1, w}), f_{i-1, j} + c_i \cdot c_{i-1}).$
    377 
    378 This can be seen as a global modification in the form of $x \gets \max(a, x + b)$. The tags are composable in $\mathcal O(1)$; Otherwise, we can brutely update the new $dp_j$ for $\mathcal O(m)$ positions.
    379 
    380 Therefore, this problem is solved in $\mathcal O(nm)$. We decided to let every segment tree solution pass comfortably, so that we set small constraints and large TL.
    381 
    382 Bonus Hint for implementation: always use $\max(a, dp_j + b)$ to get the real value.
    383 
    384 **Code (C++)**
    385 
    386 ```
    387 #include <bits/stdc++.h>
    388  
    389 namespace FastIO {
    390 	char buf[1 << 21], *p1 = buf, *p2 = buf;
    391 #define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
    392 	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
    393 	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
    394 	template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
    395 	template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
    396 #undef getchar
    397 }; using namespace FastIO;
    398  
    399 using ll = long long;
    400 void solve() {
    401 	int n = read<int>(), m = read<int>(), k = read<int>(); ll cntP = 0, cntQ = 0;
    402 	std::vector<int> vep(m), veq(m), cntp(k + 1), cntq(k + 1), vis(k + 1);
    403 	std::vector<ll> dp(k + 1); ll a = 0, b = 0, v = 0, ext = 0; // max(a, x + b).
    404 	cntp[0] = cntq[0] = m;
    405 	auto get = [&](int x) -> int { return (~x) ? x : 0; };
    406 	auto read_q = [&]() -> void {
    407 		for (int i = 0; i < m; ++i) --cntq[get(veq[i])];
    408 		for (int i = 0; i < m; ++i) ++cntq[get(veq[i] = read<int>())];
    409 		cntQ = cntq[0];
    410 	};
    411 	auto roll = [&]() -> void { std::swap(vep, veq), std::swap(cntp, cntq), std::swap(cntP, cntQ); };
    412 	auto chkmax = [&](ll &a, ll b) -> void { a = std::max(a, b); };
    413 	read_q(), roll();
    414 	for (int i = 2; i <= n; ++i) {
    415 		read_q();
    416 		ll max_dp = std::max(a, v + b);
    417 		for (int k : vep) if (~k) chkmax(max_dp, std::max(a, dp[k] + b) + cntP * cntq[k]);
    418 		for (int k : veq) if (~k) chkmax(max_dp, std::max(a, dp[k] + b) + cntP * cntq[k]);
    419 		for (int k : vep) if ((~k) && vis[k] != i) {
    420 			vis[k] = i, ext += 1ll * cntp[k] * cntq[k];
    421 			dp[k] = std::max(a, dp[k] + b) + cntP * cntq[k] + cntQ * cntp[k] - b;
    422 			chkmax(dp[k], max_dp + cntp[k] * cntQ - b - cntP * cntQ);
    423 			chkmax(v, dp[k]);
    424 		} for (int k : veq) if ((~k) && vis[k] != i) {
    425 			vis[k] = i;
    426 			dp[k] = std::max(a, dp[k] + b) + cntP * cntq[k] + cntQ * cntp[k] - b;
    427 			chkmax(dp[k], max_dp + cntp[k] * cntQ - b - cntP * cntQ);
    428 			chkmax(v, dp[k]);
    429 		} a = std::max(max_dp, a + cntP * cntQ), b += cntP * cntQ;
    430 		roll();
    431 	} print<ll>(std::max(a, v + b) + ext, '\n');
    432 }
    433  
    434 int main() { int T = read<int>(); while (T--) solve(); return 0; }
    435 ```
    436 
    437 **Rate the Problem**
    438 
    439 * Amazing problem:
    440 * Good problem:
    441 * Average problem:
    442 * Bad problem:
    443 * Didn't solve:
    444 
    445 [2053G - Naive String Splits](/contest/2053/problem/G "Good Bye 2024: 2025 is NEAR")
    446 
    447 Special thanks to [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225") for generating the test data for this problem, and [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") for providing an alternative solution.
    448 
    449 And thanks to [Caylex](/profile/Caylex "International Master Caylex") for implementing a really correct MCS and rewriting the editorial, and [crazy_sea](/profile/crazy_sea "International Grandmaster crazy_sea") for offering a suggestion.
    450 
    451 **Hint 1**
    452 
    453 (If we do not have to be deterministic) We do not need any hard string algorithm.
    454 
    455 **Hint 2**
    456 
    457 In what cases won't greed work? Why?
    458 
    459 **Hint 3**
    460 
    461 Is your brute forces actually faster (maybe you can explain it by harmonic series)?
    462 
    463 **Solution**
    464 
    465 Let's call the prefix $s_1$ the short string and the suffix $s_2$ the long string. If $\lvert s_1\rvert\gt \lvert s_2\rvert$, swapping the order doesn't affect the answer.
    466 
    467 Consider a greedy approach. We first match a few short strings until we can't match anymore. If we can't match, we try discarding a few short strings and placing one long string. We enumerate how many short strings to discard. **Find the first position where we can place a long string.** We call this placing once a "matching process." The starting position of each "matching process" is the next position after the previous "matching process."
    468 
    469 However, this approach has a flaw. Below, I will explain the situation where this flaw occurs.
    470 
    471 **Why it has a flaw**
    472 
    473 It's not difficult to view the long string as several short strings concatenated with a "tail" at the end.
    474 
    475 Why only find the first position? Why wouldn't it be better to backtrack and discard a few more $s_1$'s before placing the long string?
    476 
    477 ![ ](/predownloaded/b3/51/b35142ed44b35fc81c3b85bdd26c01e6cb115aec.png)
    478 
    479 The diagram above is an example. The red line indicates the cutoff position for matching $s_1$. The three orange boxes represent the possible choices for attempting to match the long string.
    480 
    481 The last one is invalid, so skip it. Replace it with the "The first valid position to place the long string." box. This box is correct.
    482 
    483 The difference between choosing the second box and the first box is that when we end the matching and proceed to the next round, the content we need to match is that a suffix of $s_1$ has been moved to the beginning of $s_1$。
    484 
    485 As shown in the diagram.
    486 
    487 ![ ](/predownloaded/b1/51/b151263fea82be2f40fc7afdbe7656d9c6d27b3e.png)
    488 
    489 The alignment results in the following diagram.
    490 
    491 ![ ](/predownloaded/44/4f/444fde06483532a514b3c3451007e41f5c89814e.png)
    492 
    493 In the diagram, the case where $\lvert pre\rvert \gt \lvert suf\rvert$ is shown. The other case follows similarly.
    494 
    495 $pre+suf=suf+pre$, and as can be seen from the diagram, here $pre+suf$ needs to be "misaligned but equal." This means that $s_1$ must have a periodic cycle, and the "tail" must also be able to be formed through this cycle. Additionally, the $\lvert s_1 \rvert$ characters at the beginning of $s_2$ must still be able to be formed by the periodic cycle.
    496 
    497 In summary, it is equivalent to $s_1$ and $s_2$ having a **common periodic cycle**.
    498 
    499 In other words, **backtracking twice can lead to a solution, but backtracking once may not always work**. It is necessary for $s_1$ and $s_2$ to have a common periodic cycle.
    500 
    501 Having a common periodic cycle is too specific. First, the common periodic cycle of these two strings must indeed be the periodic cycle of string $s$. By finding this cycle in advance, it essentially becomes a problem of solving an equation. Let $a=\lvert s_1\rvert $ and $b=\lvert s_2\rvert$, and we need to check whether there are non-negative integer solutions $x$ and $y$ that satisfy the equation $xa+yb=\lvert s \rvert$.
    502 
    503 This equation-solving part is just for show. We enumerate $y$, and for each value of $y$, we compute the enumeration $\mathcal O\left(\frac{m}{n}\right)$ times. At most, we do this $n$ times, so the overall complexity is $\mathcal O(m)$.
    504 
    505 If we directly implement this, the worst-case complexity is related to the harmonic series. Consider a case like $s_1 = \texttt{a}, s_2 = \texttt{aaaaaaaab}$, and $t = \texttt{aaaaaaaaaaaaaaaaaaaaaaaaab}$. In this case, we would need to attempt $\mathcal O\left(\frac{m}{\lvert s_1\rvert }\right)$ steps to finish matching the short string. Each time we backtrack, it requires at most $\mathcal O\left(\frac{m}{\lvert s_2\rvert }\right)$ steps, and each of those takes $\mathcal O\left(\frac{\lvert s_2\rvert }{\lvert s_1\rvert }\right)$.
    506 
    507 **Optimization to Linear**
    508 
    509 Thanks to [zhoukangyang](/profile/zhoukangyang "Legendary Grandmaster zhoukangyang") and [crazy_sea](/profile/crazy_sea "International Grandmaster crazy_sea") for pointing out it!
    510 
    511 Yes, this problem can indeed be solved in linear time.
    512 
    513 First, let the prefix of the long string contain $c$ short strings. Then, the first "valid position to place the long string" we backtrack to can only be obtained by either backtracking $c$ short strings or $c+1$ short strings.
    514 
    515 This is easy to understand. Backtracking $c$ short strings means considering the prefix of the long string, then adding the "tail" of the long string. Backtracking $c + 1$ short strings only happens when the "tail" part of the long string is a prefix of the short string. For example, the hack in the CF comment section:
    516 
    517 <https://codeforces.com/blog/entry/136455?#comment-1234262>
    518 
    519 ```
    520 1
    521 8 8
    522 abaabaab
    523 abaababa
    524 ```
    525 
    526 The correct output should be:
    527 
    528 ```
    529 0010000
    530 ```
    531 
    532 When $k = 3$, $s_1 = \texttt{aba}$, $s_2 = \texttt{abaab}$, we first filled in 2 short strings, but if we backtrack $c = 1$ short string, it will be judged as unsolvable. This is how the error in std occurs. This situation only arises when the "tail" part of $s_2$ is a prefix of $s_1$.
    533 
    534 So, each time we calculate, we first use binary search to find this $c$, and the complexity is $\mathcal O\left(\sum\limits_{i=1}^n\log(\frac n i)\right)=\mathcal O(n)$. After that, backtracking only requires two checks. The backtracking process becomes linear.
    535 
    536 Next, let's accelerate the process of filling in short strings. The hack for brute-force filling has already been given above. If we directly use the method that everyone initially thought was correct, which is the "binary search for the number of short string occurrences" method, Then it can be accelerated by this set of hacks to achieve a $\log$ complexity.
    537 
    538 ```
    539 1
    540 2 5000000
    541 ab
    542 abababab....abababab
    543 ```
    544 
    545 [crazy_sea](/profile/crazy_sea "International Grandmaster crazy_sea") points out an alternative solution.
    546 
    547 Similar to block division, let $B = \frac{n}{\lvert s_1\rvert}$. We first try to match $B$ occurrences of $s_1$, meaning that each match can move forward by $n$ positions. After that, the remaining part will not exceed $B$ occurrences, and we binary search to find how many are left. For the part where we moved forward by $B$ occurrences, we can backtrack at most once, and then the binary search will take $\mathcal O(\log B)$. Each time, we can at least fill in $\lvert s_2\rvert $ occurrences. The time complexity for calculating the answer becomes $\mathcal O\left(\frac{m}{\lvert s_2\rvert }\log B\right)$, and the total complexity, due to $\mathcal O\left(\sum\limits_{i=1}^n \log(\frac{n}{i})\right) = \mathcal O(n)$, is $\mathcal O(m)$.
    548 
    549 Thus, the problem is solved in linear time.
    550 
    551 **...wtf?**
    552 
    553 During testing, we found that [EvenImage](/profile/EvenImage "Legendary Grandmaster EvenImage")'s solution is actually more violent than we thought (We have also received something similar in contest).
    554 
    555 He specially handled the case in which $X$ and $T$ share a common shortest period, and for the rest $i$, he just used two queues to optimize the BFS progress (actually changing it to `std::priority_queue<int>` or similar also works), and it passed just seeming to have a larger constant time complexity.
    556 
    557 I'm curious if anybody can (hack it or) prove that it is correct. Thanks in advance!
    558 
    559 **Code (log, C++)**
    560 
    561 This is written by [Caylex](/profile/Caylex "International Master Caylex").
    562 
    563 ```
    564 #include <bits/stdc++.h>
    565 using namespace std;
    566 template <int P>
    567 class mod_int
    568 {
    569     using Z = mod_int;
    570 
    571 private:
    572     static int mo(int x) { return x < 0 ? x + P : x; }
    573 
    574 public:
    575     int x;
    576     int val() const { return x; }
    577     mod_int() : x(0) {}
    578     template <class T>
    579     mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    580     bool operator==(const Z &rhs) const { return x == rhs.x; }
    581     bool operator!=(const Z &rhs) const { return x != rhs.x; }
    582     Z operator-() const { return Z(x ? P - x : 0); }
    583     Z pow(long long k) const
    584     {
    585         Z res = 1, t = *this;
    586         while (k)
    587         {
    588             if (k & 1)
    589                 res *= t;
    590             if (k >>= 1)
    591                 t *= t;
    592         }
    593         return res;
    594     }
    595     Z &operator++()
    596     {
    597         x < P - 1 ? ++x : x = 0;
    598         return *this;
    599     }
    600     Z &operator--()
    601     {
    602         x ? --x : x = P - 1;
    603         return *this;
    604     }
    605     Z operator++(int)
    606     {
    607         Z ret = x;
    608         x < P - 1 ? ++x : x = 0;
    609         return ret;
    610     }
    611     Z operator--(int)
    612     {
    613         Z ret = x;
    614         x ? --x : x = P - 1;
    615         return ret;
    616     }
    617     Z inv() const { return pow(P - 2); }
    618     Z &operator+=(const Z &rhs)
    619     {
    620         (x += rhs.x) >= P && (x -= P);
    621         return *this;
    622     }
    623     Z &operator-=(const Z &rhs)
    624     {
    625         (x -= rhs.x) < 0 && (x += P);
    626         return *this;
    627     }
    628     Z operator-() { return -x; }
    629     Z &operator*=(const Z &rhs)
    630     {
    631         x = 1ULL * x * rhs.x % P;
    632         return *this;
    633     }
    634     Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    635 #define setO(T, o)                                  \
    636     friend T operator o(const Z &lhs, const Z &rhs) \
    637     {                                               \
    638         Z res = lhs;                                \
    639         return res o## = rhs;                       \
    640     }
    641     setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
    642 #undef setO
    643         friend istream &
    644         operator>>(istream &is, mod_int &x)
    645     {
    646         long long tmp;
    647         is >> tmp;
    648         x = tmp;
    649         return is;
    650     }
    651     friend ostream &operator<<(ostream &os, const mod_int &x)
    652     {
    653         os << x.val();
    654         return os;
    655     }
    656 };
    657 typedef long long ll;
    658 typedef unsigned long long ull;
    659 mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
    660 constexpr int p = 993244853;
    661 using Hash = mod_int<p>;
    662 // using Hash = ull;
    663 const Hash base = rnd() % 20091119 + 30;
    664 string s, t;
    665 Hash st;
    666 int mnlen;
    667 Hash S[5000020];
    668 Hash T[5000020];
    669 Hash pw[5000020];
    670 inline Hash SUM(const int l, const int r, const Hash *s) { return s[r] - s[l - 1] * pw[r - l + 1]; }
    671 int n, m;
    672 inline bool check(const int l, const int r, const Hash x, const int len, const Hash *S) { return r - l + 1 >= len && SUM(l, l + len - 1, S) == x && SUM(l, r - len, S) == SUM(l + len, r, S); }
    673 inline bool calc(const int L1, const int R1, const int L2, const int R2, const int l1, const int l2)
    674 {
    675     if (mnlen && check(L1, R1, st, mnlen, S) && check(L2, R2, st, mnlen, S))
    676     {
    677         if (check(1, m, st, mnlen, T))
    678         {
    679             for (int i = 0; i <= m; i += l2)
    680             {
    681                 if (!((m - i) % l1))
    682                     return 1;
    683             }
    684             return 0;
    685         }
    686     }
    687     const Hash s1 = SUM(L1, R1, S);
    688     const Hash s2 = SUM(L2, R2, S);
    689     // int l = 1, r = l2 / l1, okcnt = 0;
    690     // while (l <= r)
    691     // {
    692     //     int mid = l + r >> 1;
    693     //     if (check(L2, L2 + mid * l1 - 1, s1, l1, S))
    694     //         l = (okcnt = mid) + 1;
    695     //     else
    696     //         r = mid - 1;
    697     // }
    698     int ed = 0;
    699     while (ed <= m)
    700     {
    701         int L = 1, R = (m - ed) / l1, cnt = 0;
    702         while (L <= R)
    703         {
    704             int mid = L + R >> 1;
    705             if (check(ed + 1, ed + mid * l1, s1, l1, T))
    706                 L = (cnt = mid) + 1;
    707             else
    708                 R = mid - 1;
    709         }
    710         if (ed + cnt * l1 + 1 > m)
    711             return 1;
    712         // bool found = 0;
    713         // int st = ed + (cnt - okcnt) * l1 + 1;
    714         // if (st > ed && st + l2 - 1 <= m && SUM(st, st + l2 - 1, T) == s2)
    715         // {
    716         //     ed = st + l2 - 1;
    717         //     found = 1;
    718         // }
    719         // if (!found)
    720         //     return 0;
    721         bool found = 0;
    722         for (int st = ed + cnt * l1 + 1; st > ed; st -= l1)
    723         {
    724             if (st + l2 - 1 <= m && SUM(st, st + l2 - 1, T) == s2)
    725             {
    726                 ed = st + l2 - 1;
    727                 found = 1;
    728                 break;
    729             }
    730         }
    731         if (!found)
    732             return 0;
    733     }
    734     return 1;
    735 }
    736 void solve()
    737 {
    738     // build();
    739     mnlen = 0;
    740     cin >> n >> m >> s >> t;
    741     s = ' ' + s;
    742     t = ' ' + t;
    743     for (int i = 1; i <= n; i++)
    744         S[i] = S[i - 1] * base + Hash(s[i] - 'a' + 1);
    745     for (int i = 1; i <= m; i++)
    746         T[i] = T[i - 1] * base + Hash(t[i] - 'a' + 1);
    747     for (int i = 1; i <= n; i++)
    748     {
    749         if (n % i == 0 && check(1, n, S[i], i, S))
    750         {
    751             st = S[i];
    752             mnlen = i;
    753             break;
    754         }
    755     }
    756     for (int i = 1; i < n; i++)
    757         putchar('0' ^ (i <= n - i ? calc(1, i, i + 1, n, i, n - i) : calc(i + 1, n, 1, i, n - i, i)));
    758     putchar('\n');
    759 }
    760 int main()
    761 {
    762     pw[0] = Hash(1);
    763     for (int i = 1; i <= 5'000'000; i++)
    764         pw[i] = pw[i - 1] * base;
    765     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    766     int t;
    767     cin >> t;
    768     while (t--)
    769         solve();
    770     return 0;
    771 }
    772 ```
    773 
    774 **Code (linear, C++)**
    775 
    776 This is written by [Caylex](/profile/Caylex "International Master Caylex").
    777 
    778 ```
    779 #include <bits/stdc++.h>
    780 using namespace std;
    781 template <int P>
    782 class mod_int
    783 {
    784     using Z = mod_int;
    785 
    786 private:
    787     static int mo(int x) { return x < 0 ? x + P : x; }
    788 
    789 public:
    790     int x;
    791     int val() const { return x; }
    792     mod_int() : x(0) {}
    793     template <class T>
    794     mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    795     bool operator==(const Z &rhs) const { return x == rhs.x; }
    796     bool operator!=(const Z &rhs) const { return x != rhs.x; }
    797     Z operator-() const { return Z(x ? P - x : 0); }
    798     Z pow(long long k) const
    799     {
    800         Z res = 1, t = *this;
    801         while (k)
    802         {
    803             if (k & 1)
    804                 res *= t;
    805             if (k >>= 1)
    806                 t *= t;
    807         }
    808         return res;
    809     }
    810     Z &operator++()
    811     {
    812         x < P - 1 ? ++x : x = 0;
    813         return *this;
    814     }
    815     Z &operator--()
    816     {
    817         x ? --x : x = P - 1;
    818         return *this;
    819     }
    820     Z operator++(int)
    821     {
    822         Z ret = x;
    823         x < P - 1 ? ++x : x = 0;
    824         return ret;
    825     }
    826     Z operator--(int)
    827     {
    828         Z ret = x;
    829         x ? --x : x = P - 1;
    830         return ret;
    831     }
    832     Z inv() const { return pow(P - 2); }
    833     Z &operator+=(const Z &rhs)
    834     {
    835         (x += rhs.x) >= P && (x -= P);
    836         return *this;
    837     }
    838     Z &operator-=(const Z &rhs)
    839     {
    840         (x -= rhs.x) < 0 && (x += P);
    841         return *this;
    842     }
    843     Z operator-() { return -x; }
    844     Z &operator*=(const Z &rhs)
    845     {
    846         x = 1ULL * x * rhs.x % P;
    847         return *this;
    848     }
    849     Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    850 #define setO(T, o)                                  \
    851     friend T operator o(const Z &lhs, const Z &rhs) \
    852     {                                               \
    853         Z res = lhs;                                \
    854         return res o## = rhs;                       \
    855     }
    856     setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
    857 #undef setO
    858         friend istream &
    859         operator>>(istream &is, mod_int &x)
    860     {
    861         long long tmp;
    862         is >> tmp;
    863         x = tmp;
    864         return is;
    865     }
    866     friend ostream &operator<<(ostream &os, const mod_int &x)
    867     {
    868         os << x.val();
    869         return os;
    870     }
    871 };
    872 typedef long long ll;
    873 typedef unsigned long long ull;
    874 mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
    875 constexpr int p = 993244853;
    876 using Hash = mod_int<p>;
    877 // using Hash = ull;
    878 const Hash base = rnd() % 20091119 + 30;
    879 string s, t;
    880 Hash st;
    881 int mnlen;
    882 Hash S[5000020];
    883 Hash T[5000020];
    884 Hash pw[5000020];
    885 // int doit;
    886 inline Hash SUM(const int l, const int r, const Hash *s) { return s[r] - s[l - 1] * pw[r - l + 1]; }
    887 int n, m;
    888 inline bool check(const int l, const int r, const Hash x, const int len, const Hash *S)
    889 {
    890     // doit++;
    891     return r - l + 1 >= len && SUM(l, l + len - 1, S) == x && SUM(l, r - len, S) == SUM(l + len, r, S);
    892 }
    893 inline bool calc(const int L1, const int R1, const int L2, const int R2, const int l1, const int l2)
    894 {
    895     if (mnlen && check(L1, R1, st, mnlen, S) && check(L2, R2, st, mnlen, S))
    896     {
    897         if (check(1, m, st, mnlen, T))
    898         {
    899             for (int i = 0; i <= m; i += l2)
    900             {
    901                 if (!((m - i) % l1))
    902                     return 1;
    903             }
    904             return 0;
    905         }
    906     }
    907     const Hash s1 = SUM(L1, R1, S);
    908     const Hash s2 = SUM(L2, R2, S);
    909     int l = 1, r = l2 / l1, okcnt = 0;
    910     while (l <= r)
    911     {
    912         int mid = l + r >> 1;
    913         if (check(L2, L2 + mid * l1 - 1, s1, l1, S))
    914             l = (okcnt = mid) + 1;
    915         else
    916             r = mid - 1;
    917     }
    918     const int tt = (n / l1);
    919     int ed = 0;
    920     while (ed <= m)
    921     {
    922         int L = 1, R = (m - ed) / l1, cnt = 0;
    923         int tcnt = 0;
    924         while (tcnt + tt <= R && check(ed + 1, ed + (tcnt + tt) * l1, s1, l1, T))
    925             tcnt += tt;
    926         L = max(L, tcnt);
    927         R = min(R, tcnt + tt - 1);
    928         // cerr << ed << ' ' << L << ' ' << R << '\n';
    929         while (L <= R)
    930         {
    931             int mid = L + R >> 1;
    932             if (check(ed + 1, ed + mid * l1, s1, l1, T))
    933                 L = (cnt = mid) + 1;
    934             else
    935                 R = mid - 1;
    936         }
    937         if (ed + cnt * l1 + 1 > m)
    938             return 1;
    939         // int st = ed + (cnt - okcnt) * l1 + 1;
    940         // if (st > ed && st + l2 - 1 <= m && SUM(st, st + l2 - 1, T) == s2)
    941         // {
    942         //     ed = st + l2 - 1;
    943         //     continue;
    944         // }
    945         // return 0;
    946         bool found = 0;
    947         for (int st = ed + (cnt - okcnt) * l1 + 1, cnt = 1; cnt <= 2 && st > ed; st -= l1, cnt++)
    948         {
    949             if (st + l2 - 1 <= m && SUM(st, st + l2 - 1, T) == s2)
    950             {
    951                 ed = st + l2 - 1;
    952                 found = 1;
    953                 break;
    954             }
    955         }
    956         if (!found)
    957             return 0;
    958     }
    959     return 1;
    960 }
    961 void solve()
    962 {
    963     // build();
    964     mnlen = 0;
    965     cin >> n >> m >> s >> t;
    966     s = ' ' + s;
    967     t = ' ' + t;
    968     for (int i = 1; i <= n; i++)
    969         S[i] = S[i - 1] * base + Hash(s[i] - 'a' + 1);
    970     for (int i = 1; i <= m; i++)
    971         T[i] = T[i - 1] * base + Hash(t[i] - 'a' + 1);
    972     for (int i = 1; i <= n; i++)
    973     {
    974         if (n % i == 0 && check(1, n, S[i], i, S))
    975         {
    976             st = S[i];
    977             mnlen = i;
    978             break;
    979         }
    980     }
    981     for (int i = 1; i < n; i++)
    982         putchar('0' ^ (i <= n - i ? calc(1, i, i + 1, n, i, n - i) : calc(i + 1, n, 1, i, n - i, i)));
    983     putchar('\n');
    984     // cerr << doit << '\n';
    985 }
    986 int main()
    987 {
    988     // freopen("out.txt", "r", stdin);
    989     pw[0] = Hash(1);
    990     for (int i = 1; i <= 5'000'000; i++)
    991         pw[i] = pw[i - 1] * base;
    992     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    993     int t;
    994     cin >> t;
    995     while (t--)
    996         solve();
    997     // cerr << fixed << setprecision(10) << 1.0 * clock() / CLOCKS_PER_SEC << '\n';
    998     return 0;
    999 }
   1000 ```
   1001 
   1002 **Rate the Problem**
   1003 
   1004 * Amazing problem:
   1005 * Good problem:
   1006 * Average problem:
   1007 * Bad problem:
   1008 * Didn't solve:
   1009 
   1010 [2053H - Delicate Anti-monotonous Operations](/contest/2053/problem/H "Good Bye 2024: 2025 is NEAR")
   1011 
   1012 Special thanks to [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225") and [N_z__](/profile/N_z__ "International Grandmaster N_z__") for developing this problem.
   1013 
   1014 **Hint 1**
   1015 
   1016 What if $w = 2$? Is it optimal to increase $\sum\limits_{i=0}^n [a_i \neq a_{i+1}]$ (suppose $a_0 = a_{n+1} = 2$)?
   1017 
   1018 **Hint 2**
   1019 
   1020 If $w \geq 3$, what's the answer to the first question?
   1021 
   1022 **Hint 3**
   1023 
   1024 If $a_i = a_{i+1}$, after the operation we can obtain $a_{i-1} = a_i$ or $a_{i+1} = a_{i+2}$ (and possibly, both).
   1025 
   1026 **Hint 4**
   1027 
   1028 Try to think of the whole process reversedly. If $w \geq 3$, $1 \leq a_i \leq w - 1$, can you solve the problem?
   1029 
   1030 **Hint 5**
   1031 
   1032 How many extra operations are required for each $1 \leq i \leq n$ if $a_i = w$, in the above scheme you use for $a_i \leq w - 1$?
   1033 
   1034 **Solution**
   1035 
   1036 Read the Hints.
   1037 
   1038 * $w = 2$
   1039 
   1040 After any operation, $k = \sum\limits_{i=0}^n [a_i \neq a_{i+1}]$ won't decrease (suppose $a_0 = a_{n+1} = 2$). For a fixed $k$, the maximal $\sum a_i = 2n - \frac{1}{2}k$ and can be reached by each time turning a $[2, 1, 1]$ into $[2, 2, 1]$ (or symmetrically, $[1, 1, 2] \rightarrow [1, 2, 2]$.
   1041 
   1042 * $w \geq 3$
   1043   + No initial operations can be conducted, or $\min(a_i) = w$
   1044 
   1045 This case is trivial.
   1046 
   1047 * $w \geq 3$
   1048   + Some initial operations can be conducted
   1049 
   1050 We claim that the answer to the first question is $nw - 1$. For the second question, let's study some rather easier cases below.
   1051 
   1052 * $w \geq 3$
   1053   + Some initial operations can be conducted
   1054     - $a_i \neq w$
   1055 
   1056 We pretend that the final sequence is $[w, w, \dots, w, (w-1), w, w, \dots, w]$, then since $(a_i, a_{i+1})$ must be different after the operation, the last operation can only occur on $[w, (w-1)]$ (or $[(w-1), w]$). And since initially $a_i \neq w$, each position must have been operated on at least once.
   1057 
   1058 This gives us states such as $[w, \dots, w, x, x, w, \dots, w]$, $[w, \dots, w, y, y, x, w, \dots, w]$, etc. To the leftmost positions, we get $a_1 = a_2$ (essentially based on Hint 3). Also, we get ...... $a_{n-1} = a_n$? This is if and only if the initial $[w, (w - 1)]$ is neither at the beginning nor at the end. If the initial $[w, (w - 1)]$ is at the beginning, we only need $a_{n-1} = a_n$ to achieve the goal, and symmetrically the same. Less is more. Obviously, we only need to satisfy either $a_1 = a_2$ or $a_{n-1} = a_n$, and then use $n - 1$ more operations to reach the target situation.
   1059 
   1060 How do we get to $a_1 = a_2$ (symmetrically the same)? Based on Hint 3, we find the smallest $x$ that satisfies $a_x = a_{x+1}$, and then follow the example above, again using $x - 1$ operations to conduct the equality sign to $a_1 = a_2$.
   1061 
   1062 **Why is it optimal?**
   1063 
   1064 > **Lemma 1**: We can never choose an index $a_i = w$, fix it (i.e. avoid changing $a_i$ in the following operations), and then use some operations to reach $\sum a_i = nw - 1$ unless $[a_1, \ldots, a_i] = [w, \ldots, w]$ or $[a_i, \ldots, a_n] = [w, \ldots, w]$.
   1065 
   1066 **Proof**: If not so, the array is split into two parts: $[a_1, \ldots, a_{i-1}]$ and $[a_{i+1}, \ldots, a_n]$. We have: after some operations, the maximum $\sum a_i$ we can get for each part are respectively $(i-1)w - 1, (n-i)w - 1$, and add them up and we get $nw - 2$, which is less than $nw - 1$, so it's never optimal.
   1067 
   1068 > **Lemma 2**: Look at the final array $a$, consisting of $n - 1$ element $w$ and $1$ element $(w - 1)$. Obtain an array $a'$ by keeping the elements with the value of $w$. Denote $t_i$ as the last round in which ${a'}_i$ was changed to $w$ (and then become fixed). Then, there exists some $k$ such that $t_1 \lt t_2 \lt \dots \lt t_k \gt t_{k+1} \gt \dots \gt t_{n-1}$.
   1069 
   1070 **Proof**: This follows from **Lemma 1**.
   1071 
   1072 According to **Lemma 2**, we can see the pattern that we used above is optimal.
   1073 
   1074 * $w \geq 3$
   1075   + Some initial operations can be conducted
   1076     - $a_1 \neq w, a_n \neq w$
   1077 
   1078 Basically, the idea remains to reach $a_1 = a_2$ in the same way first (symmetrically the same), and then to extend to all positions. However, at this point, in the second stage, some problems may arise as follows:
   1079 
   1080 * $[\dots \underline{a_k}\ a_{k+1}\ w\ a_{k+3} \dots]$
   1081 * $[\dots \underline{\color{red}{a_{k+1}}\ a_{k+1}}\ w\ a_{k+3} \dots]$
   1082 * $[\dots \color{red}s\ \underline{\color{red}w\ w}\ a_{k+3} \dots]$
   1083 * $[\dots \color{red}{\underline{s\ s}}\ t\ a_{k+3} \dots]$
   1084 * $[\dots \color{red}w\ \underline{\color{red}t\ t}\ a_{k+3} \dots]$
   1085 * $[\dots \color{red}{w\ w}\ \underline{\color{red}{a_{k+3}}\ a_{k+3}} \dots]$
   1086 
   1087 In which $s, t, w$ are three distinct integers in the range $[1, w]$ (This also explains why we need to specially deal with the $w = 2$ case). Since we cannot fix $a_{k+2} = w$ at the beginning (refer to the "Why is it optimal?" spoiler above), we have to first change $a_{k+2}$ into something not equal to $w$, and that cost at least $2$ extra operations, which is shown here.
   1088 
   1089 **Do we always need $2$ extra operations?** One may note that if $a_i = a_{i+1} = w$, in which the two elements are both in the way of expansion, we can only use $1$ operation to vanish their existence. Formally, if there is a maximum continuous subsegment of $w$ in the way of expansion, let its length be $L$, then we will spend $\lceil \frac{L}{2} \rceil + [L = 1]$ extra operations.
   1090 
   1091 **What is 'in the way of expansion'?**
   1092 
   1093 Suppose in the first stage, we pick $a_x = a_{x+1}$ and keep operating on it until $a_1 = a_2$. Then after it, $\forall 3 \leq k \leq x + 1$, $a_k$ can be an arbitrary number which is different from the initial $a_{k-1}$, thus we can always force it to be $\neq w$.
   1094 
   1095 In the above case, only elements $[a_{x+2}, \ldots, a_n]$ are considered 'in the way of expansion', and symmetrically the same.
   1096 
   1097 * $w \geq 3$
   1098   + Some initial operations can be conducted
   1099     - No additional constraints
   1100 
   1101 It may come to you that if $a_1 = w$, we can ignore $a_1$; if $a_1 = a_2 = w$, we can ignore $a_2$. Symmetrically the same. And so on... Then we boil the problem down to the case above.
   1102 
   1103 It is correct unless in some rare cases when we ignore all the prefixes and suffixes, there will be no remaining $a_i = a_{i+1}$; or if we pick any pair $a_i = a_{i+1}$ as the starting pair in the remaining array, it is not optimal compared to picking an $a_k = a_{k+1} = w (a_{k+2} \neq w)$ (symmetrically the same). So, we have to special handle the deleted prefix and suffix, once it has a length greater than $2$.
   1104 
   1105 In summary, the problem can be solved in $\mathcal O(n)$.
   1106 
   1107 **Code (C++)**
   1108 
   1109 ```
   1110 #include <bits/stdc++.h>
   1111 
   1112 #define MAXN 200005
   1113 int a[MAXN];
   1114 
   1115 void solve() {
   1116 	int N, w; scanf("%d%d", &N, &w);
   1117 	for (int i = 1; i <= N; ++i) scanf("%d", a + i);
   1118 	if (N == 1) return (void)printf("%d 0\n", a[1]);
   1119 	if (*std::min_element(a + 1, a + N + 1) == w)
   1120 		return (void)printf("%lld 0\n", 1ll * w * N);
   1121 	if (w == 2) {
   1122 		int ans = N * 2, pans = 0;
   1123 		for (int i = 1, j = 1; i <= N; i = ++j) if (a[i] == 1) {
   1124 			--ans; while (j < N && a[j + 1] == 1) ++j; pans += j - i;
   1125 		}
   1126 		return (void)printf("%d %d\n", ans, pans);
   1127 	}
   1128 	bool flag = true;
   1129 	for (int i = 1; i < N; ++i) if (a[i] == a[i + 1]) flag = false;
   1130 	if (flag) return (void)printf("%lld 0\n", std::accumulate(a + 1, a + N + 1, 0ll));
   1131 	printf("%lld ", 1ll * w * N - 1);
   1132 	if (std::accumulate(a + 1, a + N + 1, 0ll) == 1ll * w * N - 1) return (void)puts("0");
   1133 	int ans = 0x3f3f3f3f, l = (a[1] == w ? 2 : 1), r = (a[N] == w ? N - 1 : N);
   1134 	if ((a[1] == w && a[2] == w) || (a[N] == w && a[N - 1] == w)) {
   1135 		int Lw = 0, Rw = N + 1;
   1136 		while (a[Lw + 1] == w) ++Lw; while (a[Rw - 1] == w) --Rw;
   1137 		int pans = Rw - Lw;
   1138 		for (int i = Lw + 1, j = i; i < Rw; i = ++j) if (a[i] == w) {
   1139 			while (j + 1 < Rw && a[j + 1] == w) ++j;
   1140 			pans += (i == j ? 2 : ((j - i) >> 1) + 1);
   1141 		}
   1142 		ans = pans, l = Lw + 1, r = Rw - 1;
   1143 	}
   1144 	for (int d = 0; d < 2; std::reverse(a + l, a + r + 1), ++d) 
   1145 		for (int i = l - 1, pre = 0, len = 0; i + 2 <= r; ) {
   1146 			if (a[i + 1] == a[i + 2]) 
   1147 				ans = std::min(r - (i + 1) + r - l - 1 + pre - ((len == 1) && i + 2 < r && a[i + 3] != w ? 1 : 0), ans);
   1148 			++i; if (a[i] == w) ++len, pre += (len == 1 ? 2 : len == 2 ? -1 : (len & 1)); else len = 0;
   1149 	}
   1150 	printf("%d\n", ans);
   1151 }
   1152 
   1153 int main() { int T; scanf("%d", &T); while (T--) solve(); return 0; }
   1154 ```
   1155 
   1156 **Rate the Problem**
   1157 
   1158 * Amazing problem:
   1159 * Good problem:
   1160 * Average problem:
   1161 * Bad problem:
   1162 * Didn't solve:
   1163 
   1164 [2053I1 - Affectionate Arrays (Easy Version)](/contest/2053/problem/I1 "Good Bye 2024: 2025 is NEAR")
   1165 
   1166 **Hint 1**
   1167 
   1168 What is the minimized LIS?
   1169 
   1170 **Hint 2**
   1171 
   1172 How do you prove that it is an achievable lower bound?
   1173 
   1174 **Hint 3**
   1175 
   1176 Go for a brute DP first.
   1177 
   1178 **Solution**
   1179 
   1180 We claim that the minimized LIS is $\sum a_i$. Let $p$ be $\sum a_i$.
   1181 
   1182 Since it is required that $\operatorname{LIS}(b) = p$ while $\sum b_i = p$, we point out that it is equivalent to **each of the prefix sums of the sequence being between $[0, p]$**.
   1183 
   1184 * **Sufficiency**: $\forall X \in [0, p], Y \in [0, p]$, $X - Y \leq p$. Also, we can pick $X = p, Y = 0$, so it can only be $= p$.
   1185 * **Necessity**: disproof. If a prefix sum is $ \lt 0$, then choose the whole array except for this prefix; if a prefix sum is $ \gt p$, then choose this prefix. Both derive a contradiction of the LIS being greater than $p$.
   1186 
   1187 Consider dp. Let $f_{i,j}$ denote, after considering the first $i$ numbers, the minimum **extra** sequence length (i.e. the actual length minus $i$), when the current prefix sum is $j$. The initial states are $f_{0,j} = [j \neq 0]$. The transfer is simple too:
   1188 
   1189 $f_{i,j} = \min\limits_{0 \leq k + a_i \leq p} (f_{i-1,k} + [k + a_i \neq j])$
   1190 
   1191 It is possible to optimize the transfer to $\mathcal O(np)$, since for each $j$, the contribution from at most one $k$ is special ($+0$). We can calculate the prefix and suffix $\min$ for $f_{i-1}$ and it will be fast to get the dp array in the new row. Then, let's focus on optimizing it to $\mathcal O(n)$.
   1192 
   1193 We call the set of $0 \leq k \leq p$ satisfying $0 \leq k + a_i \leq p$ as the legal interval of $i$ (denoted as $L_i$).
   1194 
   1195 It is concluded that the range of $f_{i, 0\dots p}$ is at most $1$, and this can be proven by considering the transfer to each of the $j$ with the $k \in L_i$ which has the least $f_{i-1, k}$. Let $v_i = \min_{0 \leq j \leq p}(f_{i, j})$. We also have: for those $j$ with $f_{i,j} = v_i$, they form a consecutive segment in the integer field. Let the segment be covering $[l_i, r_i]$.
   1196 
   1197 Inductive proof. The essence of the transfer is that it shifts all the DP values $= v_{i-1}$ by $a_i$ unit length, and all the other numbers will be updated to $v_{i-1} + 1$. Then truncates the $j \in ((-\inf, 0) \cup (p, +\inf))$ part. The consecutive segment remains consecutive. Specially, if $[l_{i-1}, r_{i-1}] \cap L_i = \varnothing$, then $\min_{k \in L_i}(f_{i-1, k}) = v_{i-1} + 1$, hence we need to set $v_i = v_{i-1} + 1$, and $l_i, r_i$ as the range of $j = k + a_i$ in which $k \in L_i$. Otherwise, $v_i = v_{i-1}$, and $l_i, r_i$ can be calculated by shifting $l_{i-1}, r_{i-1}$ by $a_i$ unit length.
   1198 
   1199 In fact, we only need to maintain three variables $l, r, v$ to represent the current consecutive segment and the current value field. Therefore, this problem can be easily solved in $\mathcal O(n)$.
   1200 
   1201 **Code (C++)**
   1202 
   1203 ```
   1204 #include <bits/stdc++.h>
   1205  
   1206 namespace FastIO {
   1207 	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
   1208 	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
   1209 	template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
   1210 	template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
   1211 }; using namespace FastIO;
   1212  
   1213 #define MAXN 3000001
   1214 int a[MAXN];
   1215 void solve() {
   1216 	int N = read<int>(); long long p = 0, l = 0, r = 0, v = 0;
   1217 	for (int i = 1; i <= N; ++i) p += (a[i] = read<int>());
   1218 	for (int i = 1; i <= N; ++i) if (a[i] >= 0) {
   1219 		l += a[i], r = std::min(r + a[i], p);
   1220 		if (l > r) ++v, l = a[i], r = p;
   1221 	} else {
   1222 		a[i] = -a[i];
   1223 		r -= a[i], l = std::max(l - a[i], 0ll);
   1224 		if (l > r) ++v, l = 0, r = p - a[i];
   1225 	}
   1226 	print<int>(v + N + (int)(r != p), '\n');
   1227 }
   1228 int main() { int T = read<int>(); while (T--) solve(); return 0; }
   1229 ```
   1230 
   1231 **Rate the Problem**
   1232 
   1233 * Amazing problem:
   1234 * Good problem:
   1235 * Average problem:
   1236 * Bad problem:
   1237 * Didn't solve:
   1238 
   1239 [2053I2 - Affectionate Arrays (Hard Version)](/contest/2053/problem/I2 "Good Bye 2024: 2025 is NEAR")
   1240 
   1241 **Hint 1**
   1242 
   1243 Try insert numbers into spaces between the elements of $a$ (including the beginning and the end). Note that an array be can be formed in multiple ways (for example, you can insert a number $x$ to the left or right of the original number $x$ in array $a$). What's the number of different ways?
   1244 
   1245 **Answer**
   1246 
   1247 It's actually the "value", that is, the number of occurrances of $a$. Use the fact that "only one number can be inserted into each space" to prove.
   1248 
   1249 **Solution**
   1250 
   1251 Read the editorial for I1 and the hints first.
   1252 
   1253 According to the hint, you can count the number of ways to insert the new numbers into the space, so the dp and transitions are similar to those in problem I1.
   1254 
   1255 We can add an additional dp array, $g_{i, j}$ representing the number of different ways when everything meets the description of $f_{i, j}$. Let's see from which values it can be transferred:
   1256 
   1257 * If $f_{i, j} = v_i$, then $f_{i, j}$ can only be transferred from $f_{i-1, j-a_i}$. That is, $g_{i, j} = g_{i-1, j-a_i}$.
   1258 * If $f_{i, j} = v_i + 1$, then $f_{i, j} = \sum_{k \in L_i, f_{i-1, k} = f_{i, j} - 1} g_{i-1, k}$.
   1259 
   1260 We can use some tags and a Deque to maintain the whole process, so the amortized time complexity is $\mathcal O(n)$.
   1261 
   1262 **Code (C++)**
   1263 
   1264 ```
   1265 #include <bits/stdc++.h>
   1266  
   1267 namespace FastIO {
   1268 	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
   1269 	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
   1270 	template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
   1271 	template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
   1272 }; using namespace FastIO;
   1273  
   1274 const int MOD = 998244353;
   1275 namespace Modint {
   1276 	inline int add(int x, int y) { return (x += y) >= MOD ? x - MOD : x; }
   1277 	inline int sub(int x, int y) { return x < y ? x - y + MOD : x - y; }
   1278 	inline int mul(int x, int y) { return 1ll * x * y % MOD; }
   1279 	inline int pow(int x, int y) { int r = 1; for (; y; y >>= 1, x = mul(x, x)) if (y & 1) r = mul(r, x); return r; }
   1280 	inline int inv(int x) { return pow(x, MOD - 2); }
   1281 };
   1282 struct modint {
   1283 	int v;
   1284 	modint (int x = 0) : v(x) { /* for debug only. assert(0 <= x && x < MOD); */ }
   1285 	inline int get() { return v; }
   1286 	modint operator - () const { return v ? MOD - v : 0; }
   1287 	modint operator + (const modint &k) const { return Modint::add(v, k.v); }
   1288 	modint operator - (const modint &k) const { return Modint::sub(v, k.v); }
   1289 	modint operator * (const modint &k) const { return Modint::mul(v, k.v); }
   1290 	modint operator / (const modint &k) const { return Modint::mul(v, Modint::inv(k.v)); }
   1291 	modint pow(const modint &k) const { return Modint::pow(v, k.v); }
   1292 	modint inverse() const { return Modint::inv(v); }
   1293 	modint operator += (const modint &k) { (v += k.v) >= MOD && (v -= MOD); return *this; }
   1294 	modint operator -= (const modint &k) { (v -= k.v) < 0 && (v += MOD); return *this; }
   1295 	modint operator *= (const modint &k) { return v = Modint::mul(v, k.v); }
   1296 	modint operator /= (const modint &k) { return v = Modint::mul(v, Modint::inv(k.v)); }
   1297 };
   1298  
   1299 struct Node {
   1300 	int f; modint g; long long len;
   1301 	Node () {}
   1302 	Node (int F, int G, long long L) : f(F), g(G), len(L) {}
   1303 	Node (int F, modint G, long long L) : f(F), g(G), len(L) {}
   1304 }; std::deque<Node> Q;
   1305  
   1306 #define MAXN 3000001
   1307 int a[MAXN];
   1308 void solve() {
   1309 	int N = read<int>(); long long p = 0, l = 0, r = 0, v = 0;
   1310 	for (int i = 1; i <= N; ++i) p += (a[i] = read<int>());
   1311 	for (int i = 1; i <= N; ++i) assert (std::abs(a[i]) <= p);
   1312 	Q.clear(); Q.push_back(Node(0, 1, 1)), Q.push_back(Node(1, 1, p));
   1313 	modint gv = 1, gz = p % MOD, tv = 0, tz = 0;
   1314 	for (int i = 1; i <= N; ++i) if (a[i] >= 0) {
   1315 		for (long long ls = a[i]; ls > 0; ) {
   1316 			Node k = Q.back(); Q.pop_back();
   1317 			if (ls < k.len) Q.push_back(Node(k.f, k.g, k.len - ls)), k.len = ls;
   1318 			(k.f == v ? gv : gz) -= k.g * (k.len % MOD), ls -= k.len;
   1319 		}
   1320 		l += a[i], r = std::min(r + a[i], p);
   1321 		if (l > r) ++v, l = a[i], r = p, gv = gz, tv = tz, gz = tz = 0;
   1322 		gz += -tz * (a[i] >= MOD ? a[i] - MOD : a[i]);
   1323         if (a[i] > 0) Q.push_front(Node(v + 1, -tz, a[i]));
   1324         tz += gv + tv * ((r - l + 1) % MOD);
   1325 	} else if (a[i] < 0) {
   1326 		a[i] = -a[i];
   1327 		for (long long ls = a[i]; ls > 0; ) {
   1328 			Node k = Q.front(); Q.pop_front();
   1329 			if (ls < k.len) Q.push_front(Node(k.f, k.g, k.len - ls)), k.len = ls;
   1330 			(k.f == v ? gv : gz) -= k.g * (k.len % MOD), ls -= k.len;
   1331 		}
   1332 		r -= a[i], l = std::max(l - a[i], 0ll);
   1333 		if (l > r) ++v, l = 0, r = p - a[i], gv = gz, tv = tz, gz = tz = 0;
   1334 		gz += -tz * (a[i] >= MOD ? a[i] - MOD : a[i]), Q.push_back(Node(v + 1, -tz, a[i])), tz += gv + tv * ((r - l + 1) % MOD);
   1335     }
   1336 	print<int>((Q.back().g + (r == p ? tv : tz)).get(), '\n');
   1337 }
   1338 int main() { int T = read<int>(); while (T--) solve(); return 0; }
   1339 ```
   1340 
   1341 **Bonus**
   1342 
   1343 Try to solve the initial problem: count the number of valid array $b$ for $n\le 500$.
   1344 
   1345 **hint**
   1346 
   1347 Consider $f_{i,j,k}$: the number of ways to fill the first $i$ elements of $b$, which contains at most $j$ first elements from $a$ as a subsequence, and the sum of the first $i$ elements is $k$.
   1348 
   1349 Try to optimize this from $O(n^2s^2)$ to $O(n^2s)$, and then $O(\rm{poly}(n))$, and then $O(n^3)$.
   1350 
   1351 **Rate the Problem**
   1352 
   1353 * Amazing problem:
   1354 * Good problem:
   1355 * Average problem:
   1356 * Bad problem:
   1357 * Didn't solve: