codeforces-scrape

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

2183.md (60067B)


      1 Source: https://codeforces.com/blog/entry/149944
      2 
      3 We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated!
      4 
      5 **Rate The Contest!**
      6 
      7 * Great contest
      8 * Good contest
      9 * Average contest
     10 * Bad contest
     11 
     12 ## [2183A — Binary Array Game](https://codeforces.com/contest/2183/problem/A)
     13 
     14 Idea & Preparation: [wangmarui](/profile/wangmarui "Grandmaster wangmarui")
     15 
     16 **Rate The Problem!**
     17 
     18 * Good Problem
     19 * Okay Problem
     20 * Bad Problem
     21 * Didn't Solve
     22 
     23 **Hint 1**
     24 
     25 If the sequence $a$ consists entirely of $1$ s, what will Alice do?
     26 
     27 **Hint 2**
     28 
     29 Consider discussing the values of $a_1$ and $a_n$.
     30 
     31 **Solution**
     32 
     33 First, if the entire sequence consists of $1$ s, Alice wins immediately by operating on the whole sequence.
     34 
     35 Note that the last operation must involve at least one of $a_1$ or $a_n$. We discuss based on the values of $a_1$ and $a_n$:
     36 
     37 If $a_1 = 1$, then Alice can directly operate on the interval $[2,n]$ to win, because $a_{2 \sim n}$ must contain at least one $0$.
     38 
     39 If $a_n = 1$, then Alice can directly operate on the interval $[1,n-1]$ to win, because $a_{1 \sim n-1}$ must contain at least one $0$.
     40 
     41 If $a_1 = 0$ and $a_n = 0$, then operating on the entire sequence would certainly cause Alice to lose. This implies that Alice cannot operate on both $a_1$ and $a_n$ simultaneously. Therefore, after Alice's operation, there will still be at least one $0$ in the sequence $a$. Bob can then operate on the entire sequence to win. Hence, in this case, Bob wins.
     42 
     43 Time complexity: $O(\sum n)$.
     44 
     45 **Implementation**
     46 
     47 ```
     48 #include<bits/stdc++.h>
     49 using namespace std;
     50 int _t_,n,a[100010];
     51 void solve()
     52 {
     53     cin>>n;
     54     for(int i=1;i<=n;i++)
     55         cin>>a[i];
     56     if(a[1]+a[n]==0)
     57         cout<<"NO\n";
     58     else
     59         cout<<"YES\n";
     60 }
     61 int main()
     62 {
     63     ios::sync_with_stdio(0);
     64     cin.tie(0),cout.tie(0);
     65     cin>>_t_;
     66     while(_t_--)
     67         solve();
     68     return 0;
     69 }
     70 ```
     71 
     72 ## [2183B — Yet Another MEX Problem](https://codeforces.com/contest/2183/problem/B)
     73 
     74 Idea & Preparation: [wangmarui](/profile/wangmarui "Grandmaster wangmarui")
     75 
     76 **Rate The Problem!**
     77 
     78 * Good Problem
     79 * Okay Problem
     80 * Bad Problem
     81 * Didn't Solve
     82 
     83 **Hint 1**
     84 
     85 Considering that in the end only $k - 1$ numbers will remain, which numbers in an interval of length $k$ are invalid?
     86 
     87 **Hint 2**
     88 
     89 Consider the Pigeonhole Principle.
     90 
     91 **Solution**
     92 
     93 Since only $k - 1$ numbers will remain in the end, it is relatively easy to notice that for any interval of length $k$, numbers within this interval that are greater than or equal to $k-1$ or have duplicate values are invalid. One of these two types of numbers can be removed. Since there are only $k - 1$ numbers from $0$ to $k-2$, in any interval of length $k$, there must be at least one number that can be deleted. Therefore, the answer is $\min(\text{mex}(a), k-1)$.
     94 
     95 Time complexity: $O(\sum n)$.
     96 
     97 **Implementation**
     98 
     99 ```
    100 #include<bits/stdc++.h>
    101 using namespace std;
    102 #define re register
    103 #define ll long long
    104 #define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)
    105 #define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
    106 #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    107 #define endl '\n'
    108 ll _t_;
    109 ll n,m;
    110 ll maxn;
    111 ll a[1000010];
    112 ll b[1000010];
    113 void _clear(){}
    114 void solve()
    115 {
    116     _clear();
    117     cin>>n>>m;
    118     forl(i,1,n)
    119         cin>>a[i],a[i]=min(a[i],n+1);
    120     forl(i,0,n+5)
    121     	b[i]=0;
    122     ll mex=0;
    123 	forl(i,1,n)
    124 		b[a[i]]++;
    125 	while(b[mex])
    126 		mex++;
    127 	cout<<min(mex,m-1)<<endl; 
    128 }
    129 int main()
    130 {
    131     IOS;
    132     _t_=1;
    133     cin>>_t_;
    134     while(_t_--)
    135         solve();
    136     return 0;
    137 }
    138 ```
    139 
    140 ## [2183C — War Strategy](https://codeforces.com/contest/2183/problem/C)
    141 
    142 Idea & Preparation: [Network_Error](/profile/Network_Error "Grandmaster Network_Error")
    143 
    144 **Rate The Problem!**
    145 
    146 * Good Problem
    147 * Okay Problem
    148 * Bad Problem
    149 * Didn't Solve
    150 
    151 **Hint 1**
    152 
    153 Consider a greedy algorithm.
    154 
    155 **Hint 2**
    156 
    157 What shape must the finally occupied bases take?
    158 
    159 **Hint 3**
    160 
    161 If the capital is the first city (i.e., $k=1$), how to solve it?
    162 
    163 **Claim 1**
    164 
    165 The finally occupied bases must form an interval containing $k$.
    166 
    167 **Proof**
    168 
    169 If the finally occupied bases do not form an interval containing $k$, then there must exist some $x, y$ such that $1 \le x \lt y \lt k$ or $k \lt y \lt x \le n$, with $x$ occupied and $y$ unoccupied. Consider a soldier at $y$ starting from $k$ and moving to $x$; it must pass through base $x$ along the way. Consider making this soldier stop exactly at $x$. Then soldier $y$ ends up at $x$. After a finite number of such adjustments, we will reach a state where no further adjustment is possible, which implies the finally occupied bases must be an interval containing $k$.
    170 
    171 **Claim 2**
    172 
    173 Suppose this interval contains $a$ positions to the left of $k$ and $b$ positions to the right of $k$ (excluding $k$ itself) ($0 \le a \le k-1$, $0 \le b \le n-k$). It is possible to occupy this interval if and only if $a + b + \max(a, b) - 1 \le m$.
    174 
    175 **Proof**
    176 
    177 Sufficiency:
    178 
    179 We can imagine a simple strategy. Initially, we do nothing until the capital contains $a$ soldiers. Then we move $a$ soldiers from $k$ to $k-1$, then move $a-1$ soldiers from $k-1$ to $k-2$, and so on. Thus $k-1, k-2, \ldots, k-a$ are all filled with soldiers. Then we wait (if necessary) until the capital contains $b$ soldiers and move them in the same way to $k+1, \ldots, k+b$. It can be observed that this strategy requires exactly $a + b + \max(a, b) - 1$ days.
    180 
    181 Necessity:
    182 
    183 We prove that for any strategy, the required number of days $m$ is at least $a + b + \max(a, b) - 1$.
    184 
    185 First, we need at least $a+b$ days to obtain the extra $a+b$ soldiers. Second, we cannot move new soldiers to new bases every moment. In fact, we can prove that there are at least $\max(a, b) - 1$ idle days. The proof is as follows.
    186 
    187 Assume without loss of generality that $a \ge b$.
    188 
    189 Define the potential function $h(S)$ of a state $S$ as the number of soldiers minus the number of occupied bases.
    190 
    191 Suppose the first move to the left is moving $t$ soldiers to the leftmost consecutive $t$ positions $k-a, \ldots, k-a+t-1$.
    192 
    193 (If the move is not to the leftmost positions but to some intermediate positions, we can show through adjustment that such a move is suboptimal. Therefore, an optimal solution will not contain such moves.)
    194 
    195 Let $S_0$ be the state before the move, $S_1$ be the state when moving $t$ soldiers to $k-a+t$, $S_2$ be the state after completing the move of all $t$ soldiers, and $S_3$ be the final state.
    196 
    197 We have $h(S_2) = h(S_1)$, $h(S_3) \ge h(S_2)$.
    198 
    199 $h(S_1) - h(S_0) \ge a - t$ (during the intermediate $a-t$ steps, the potential increases each time).
    200 
    201 $h(S_0) \ge t - 1$ (at least $t$ movable soldiers are needed).
    202 
    203 Summing up, we get $h(S_3) \ge a - 1$. Therefore, the number of days needed is at least $2a + b - 1$.
    204 
    205 In summary, at least $a + b + \max(a, b) - 1$ days are required.
    206 
    207 **Solution**
    208 
    209 We consider a greedy approach. First, if $k-1 \lt n-k$, we replace $k$ with $n+1-k$.
    210 
    211 We define two variables $a$ and $b$, representing how many cells have been extended to the left and right, respectively. Initially, $a = 0$, $b = 0$. Then we repeatedly try to increase $a$ and $b$ by $1$ in turns. We first try to increase $b$ by $1$ (if $b \lt n-k$ and $a + (b+1) + \max(a, b+1) - 1 \le m$), then set $b$ to $b+1$. Next, we try to increase $a$ by $1$ (if $a \lt k-1$ and $(a+1) + b + \max(a+1, b) - 1 \le m$). If we cannot increase $a$, we break the loop. Finally, $a + b + 1$ (don't forget the home base) is the answer. The time complexity is $O(n)$.
    212 
    213 **Implementation**
    214 
    215 ```
    216 #include<bits/stdc++.h>
    217 using namespace std;
    218 int n,k,m;
    219 signed main(){
    220     int T;
    221     cin>>T;
    222     while(T--){
    223         cin>>n>>m>>k;
    224         if(k-1<n-k)k=n+1-k;
    225         int a=0,b=0;
    226         while(1){
    227             if(b<n-k&&a+(b+1)+max(a,b+1)-1<=m)++b;
    228             if(a<k-1&&(a+1)+b+max(a+1,b)-1<=m)++a;
    229             else break;
    230         }
    231         cout<<a+b+1<<endl;
    232     }
    233 }
    234 ```
    235 
    236 **Bonus**
    237 
    238 Solve the problem in $O(1)$ or $O(\log n)$ time per test case.
    239 
    240 ## [2183D1 — Tree Coloring (Easy Version)](https://codeforces.com/contest/2183/problem/D1)
    241 
    242 Idea & Preparation: [jiazhichen844](/profile/jiazhichen844 "Grandmaster jiazhichen844")
    243 
    244 **Rate The Problem!**
    245 
    246 * Good Problem
    247 * Okay Problem
    248 * Bad Problem
    249 * Didn't Solve
    250 
    251 **Hint 1**
    252 
    253 Consider which points cannot be colored in the same operation.
    254 
    255 **Hint 2**
    256 
    257 Find a lower bound for the number of operations.
    258 
    259 **Solution**
    260 
    261 Suppose the number of points at depth $i$ is $t_i$. First, points at the same depth cannot be colored simultaneously, so the lower bound for the answer is $\max t_i$.
    262 
    263 However, note that if points in layer $x$ share a common parent, they and their parent also cannot be colored simultaneously. Thus, the answer must also be compared with $\max(t_x + 1)$.
    264 
    265 We claim this is the answer. Proof follows from the constructive proof in D2.
    266 
    267 ## [2183D2 — Tree Coloring (Hard Version)](https://codeforces.com/contest/2183/problem/D2)
    268 
    269 Idea & Preparation: [jiazhichen844](/profile/jiazhichen844 "Grandmaster jiazhichen844")
    270 
    271 **Rate The Problem!**
    272 
    273 * Good Problem
    274 * Okay Problem
    275 * Bad Problem
    276 * Didn't Solve
    277 
    278 **Hint 3**
    279 
    280 When can the minimum number of operations reach $\max t_i$? How much more than $\max t_i$ can it be at most?
    281 
    282 **Solution 1**
    283 
    284 We claim the maximum number of operations is $\max t_i + 1$. Consider the following constructive proof.
    285 
    286 Let $S_i$ denote the set of points for the $i$ th operation.
    287 
    288 Without loss of generality, let $T=\max t_i$. Find the largest $x$ such that $t_x=T$. Clearly, points with $d_i=x$ cannot be operated on simultaneously; we can place them into $S_1, S_2, \cdots, S_T$ respectively.
    289 
    290 Then we only need to consider placing points of depth $\neq x$ into $S$. First, consider points of depth $ \gt x$. Suppose we have already placed all points of depth $k-1$. Now, when placing points of depth $k$, it is clear that each $S_i$ can contain at most one point of depth $k-1$.
    291 
    292 Now, $t_{k-1}$ sets contain points of depth $k-1$, which impose constraints on the depth $k$ points to be placed; The remaining $T-t_{k-1}$ sets contain no points of depth $k-1$ and can freely add any point of depth $k$ (see the diagram below, where the upper red dots represent sets containing points of depth $k-1$, and the blue dots represent sets without such points).
    293 
    294    
    295  ![D](/predownloaded/7a/bd/7abdab44e9cdd63b1e8a77dcd2d83df5ddbee90c.png)   
    296  
    297 
    298 For restricted sets (where children cannot be placed), we can retain only one child and place the others into unrestricted sets. Since the number of points in the lower layer is strictly less than $T$, at least one unrestricted set will remain. At this point, we can place each retained child into the set to its right.
    299 
    300 Next, we construct the point of depth $ \lt x$. Suppose we have already constructed the point of depth $k+1$. Now we need to place the point of depth $k$ into a set. Clearly, there are $t_{k+1}$ sets with restrictions. Assume the current number of sets is $a = T$ or $T + 1$. The number of unrestricted sets is $c = a - t_{k+1}$. We proceed with some case analysis:
    301 
    302 1. $a=T$ and $c=0$: All points at depth $k+1$ share a common parent.
    303 
    304 This parent cannot be placed into any set. We set $a$ to $T+1$, place the parent into this new set, and assign the remaining points arbitrarily.
    305 
    306 1. Points at depth $k$ have at least two non-leaf neighbors.
    307 
    308 We can rotate these fathers into their children's sets, placing the remaining unrestricted nodes arbitrarily.
    309 
    310 1. A node at depth $k$ has exactly one non-leaf child, and at least one set lacks any node at depth $k+1$.
    311 
    312 Place this father into the set lacking a node at depth $k+1$, then place the remaining nodes arbitrarily.
    313 
    314 The above process constructs a solution with either $T$ or $T+1$ sets. It yields $T+1$ sets precisely when there are $T$ points at the same depth with the same parent, making this process clearly optimal. These sets can be maintained in $O(n)$ or $O(n\log n)$ time.
    315 
    316 Some bottom-up, directly greedy approaches are also valid, but their complexity is generally $O(n\log n)$.
    317 
    318 **Solution 2**
    319 
    320 This solution is from [nldr](/profile/nldr "International Master nldr").
    321 
    322 Consider the construction scheme.
    323 
    324 We assign each node $u$ a color $c_u \in {1, \dots, k}$ such that:
    325 
    326 If $dep_u = dep_v$ and $u \neq v$, then $c_u \neq c_v$.
    327 
    328 If $u$ is the parent node of $v$, then $c_u \neq c_v$.
    329 
    330 Assign colors layer by layer based on depth. For each layer of $m$ nodes, convert it into a matching problem.
    331 
    332 Select $m$ distinct colors from ${1, \dots, k}$ to assign to these $m$ nodes, ensuring each node does not receive the color of its parent node.
    333 
    334 Consider removing all nodes from the $d+1$th layer.
    335 
    336 Sort them by their parent node's color. This groups child nodes constrained by the same color together.
    337 
    338 Let the sorted nodes be $u_0, u_1, \dots, u_{m-1}$.
    339 
    340 Let their parent node colors be $f_0, f_1, \dots, f_{m-1}$.
    341 
    342 Define: $c_{u_i} = ((i + \Delta) \pmod k) + 1$.
    343 
    344 Here we treat colors as a cycle $0 \dots k-1$ and attempt to assign the sorted nodes $m$ consecutive colors.
    345 
    346 We need to find a $\Delta$ such that for all $i$, $(i + \Delta) \pmod k \neq f_i$.
    347 
    348 That is, $\Delta \not\equiv (f_i - i) \pmod k$.
    349 
    350 We compute all invalid $\Delta$ values (i.e., $(f_i - i) \pmod k$), yielding $m$ constraints in total.
    351 
    352 Since there are $k$ possible values for $\Delta$ and typically $m \lt k$ or constraints overlap, by the Pigeonhole Principle, a valid $\Delta$ must exist under the lower bound definition of $k$.
    353 
    354 In practice, because we've sorted by $f_i$, the constraints form a regular pattern—we only need $\Delta$ to avoid specific values.
    355 
    356 We can enumerate $\Delta$ values from smallest to largest and find the first valid $\Delta$.
    357 
    358 The complexity bottleneck lies in the sorting operation, which is $O(n \log n)$.
    359 
    360 **Implementation (Solution 1)**
    361 
    362 ```
    363 #include<bits/stdc++.h>
    364 #define int long long
    365 using namespace std;
    366 vector<int> e[300005],v[300005],g[300005];
    367 int n,d[300005],t[300005],id[300005],son[300005],snum[300005],fa[300005];
    368 bool flag[300005];
    369 void dfs(int pos,int fa)
    370 {
    371 	::fa[pos]=fa;
    372 	d[pos]=d[fa]+1;
    373 	t[d[pos]]++;
    374 	g[d[pos]].push_back(pos);
    375 	for(int x:e[pos])
    376 	{
    377 		if(x==fa)
    378 			continue;
    379 		snum[pos]++;
    380 		dfs(x,pos);
    381 	}
    382 }
    383 void test()
    384 {
    385 	cin>>n;
    386 	for(int i=1;i<=n;i++)
    387 		e[i].clear(),g[i].clear(),v[i].clear(),d[i]=t[i]=id[i]=snum[i]=0;
    388 	for(int i=1;i<n;i++)
    389 	{
    390 		int u,v;
    391 		cin>>u>>v;
    392 		e[u].push_back(v);
    393 		e[v].push_back(u);
    394 	}
    395 	dfs(1,0);
    396 	int mx=0,mt=0;
    397 	for(int i=1;i<=n;i++)
    398 		if(t[i]>=mx)
    399 			mx=t[i],mt=i;
    400 //	for(int i=1;i<=n;i++)
    401 //		cerr<<i<<" "<<fa[i]<<" "<<d[i]<<"\n";
    402 	int ans=mx;
    403 	for(int i=1;i<=mx;i++)
    404 		id[g[mt][i-1]]=i,v[i].push_back(g[mt][i-1]);
    405 	for(int i=mt+1;i<=n;i++)
    406 	{
    407 		vector<int> vfa;
    408 		for(int j:g[i-1])
    409 		{
    410 			son[j]=0;
    411 			if(snum[j])
    412 				flag[id[j]]=1;
    413 		}
    414 		int pos=1;
    415 		for(int j:g[i])
    416 		{
    417 			if(!son[fa[j]])
    418 				son[fa[j]]=j,vfa.push_back(fa[j]);
    419 			else
    420 			{
    421 				while(flag[pos])
    422 					pos++;
    423 				assert(pos<=mx);
    424 				id[j]=pos,v[pos].push_back(j),pos++;
    425 			}
    426 		}
    427 		while(flag[pos])
    428 			pos++;
    429 		assert(pos<=mx);
    430 		int lst=pos;
    431 		for(int x:vfa)
    432 		{
    433 			id[son[x]]=lst;
    434 			v[lst].push_back(son[x]);
    435 			lst=id[x];
    436 		}
    437 		for(int j:g[i-1])
    438 			flag[id[j]]=0;
    439 	}
    440 	for(int i=mt-1;i>=1;i--)
    441 	{
    442 		vector<int> vfa;
    443 		for(int j:g[i])
    444 			son[j]=0;
    445 		for(int j:g[i+1])
    446 		{
    447 			flag[id[j]]=1;
    448 			if(!son[fa[j]])
    449 				son[fa[j]]=j,vfa.push_back(fa[j]);
    450 		}
    451 		assert(!vfa.empty());
    452 		if(vfa.size()==1)
    453 		{
    454 			if(ans==t[i+1])
    455 				ans++,id[vfa[0]]=ans,v[ans].push_back(vfa[0]);
    456 			else
    457 			{
    458 				int pos=1;
    459 				while(flag[pos])
    460 					pos++;
    461 				assert(pos<=ans);
    462 				id[vfa[0]]=pos,v[pos].push_back(vfa[0]);
    463 			}
    464 		}
    465 		else
    466 		{
    467 			for(int i=0;i<vfa.size();i++)
    468 				id[vfa[i]]=id[son[vfa[(i+1)%vfa.size()]]],v[id[vfa[i]]].push_back(vfa[i]);
    469 		}
    470 		for(int j:g[i+1])
    471 			flag[id[j]]=0;
    472 		for(int x:vfa)
    473 			flag[id[x]]=1;
    474 		int pos=1;
    475 		for(int x:g[i])
    476 			if(!son[x])
    477 			{
    478 				while(flag[pos])
    479 					pos++;
    480 				assert(pos<=ans);
    481 				id[x]=pos,v[pos].push_back(x);
    482 				pos++;
    483 			}
    484 		for(int x:vfa)
    485 			flag[id[x]]=0;
    486 	}
    487 	cout<<ans<<"\n";
    488 	for(int i=1;i<=ans;i++)
    489 	{
    490 		cout<<v[i].size()<<" ";
    491 		for(int x:v[i])
    492 			cout<<x<<" ";
    493 		cout<<"\n";
    494 	}
    495 }
    496 signed main()
    497 {
    498     ios::sync_with_stdio(0);
    499     cin.tie(0);
    500     cout.tie(0);
    501     int t;
    502     cin>>t;
    503     for(int i=1;i<=t;i++)
    504     	test();
    505 }
    506 ```
    507 
    508 ## [2183E — LCM is Legendary Counting Master](https://codeforces.com/contest/2183/problem/E)
    509 
    510 Idea & Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526")
    511 
    512 **Rate The Problem!**
    513 
    514 * Good Problem
    515 * Okay Problem
    516 * Bad Problem
    517 * Didn't Solve
    518 
    519 **Hint 1**
    520 
    521 Consider the term $\frac{1}{\operatorname{lcm}(a_i,a_{i+1})}$. What properties can you derive if $a_i \lt a_{i+1}$?
    522 
    523 **Hint 2**
    524 
    525 Recall that $\frac{1}{\operatorname{lcm}(a_i,a_{i+1})} = \frac{\gcd(a_i,a_{i+1})}{a_i a_{i+1}}$. Notice that when $a_i \lt a_{i+1}$, the inequality $\gcd(a_i,a_{i+1}) \le a_{i+1}-a_i$ always holds.
    526 
    527 **Hint 3**
    528 
    529 You might have bounded the sum of the first $n-1$ terms. Try comparing the term $\frac{a_n-a_1}{a_1 a_n}$ (from the telescoping sum) with the last term $\frac{a_1}{a_1 a_n}$.
    530 
    531 **Hint 4**
    532 
    533 If $y \gt x$ and $\gcd(x,y)=y-x$, what does this imply about the relationship between $x$ and $y$? How many such pairs $(x,y)$ exist for $1\le x \lt y \le m$?
    534 
    535 **Solution**
    536 
    537 Note that
    538 
    539 $ \begin{aligned} &\quad \frac{1}{\operatorname{lcm}(a_1,a_2)}+\frac{1}{\operatorname{lcm}(a_2,a_3)}+\cdots+\frac{1}{\operatorname{lcm}(a_{n-1},a_n)}+\frac{1}{\operatorname{lcm}(a_n,a_1)} \\ &= \frac{\gcd(a_1,a_2)}{a_1a_2}+\frac{\gcd(a_2,a_3)}{a_2a_3}+\cdots+\frac{\gcd(a_{n-1},a_n)}{a_{n-1}a_n}+\frac{\gcd(a_1,a_n)}{a_1a_n} \\ &\le \frac{a_2-a_1}{a_1a_2}+\frac{a_3-a_2}{a_2a_3}+\cdots+\frac{a_n-a_{n-1}}{a_{n-1}a_n}+\frac{\color{red}{a_1}}{a_1a_n} \\ &= \left(\frac{1}{a_1}-\frac{1}{a_2}\right)+\left(\frac{1}{a_2}-\frac{1}{a_3}\right)+\cdots+\left(\frac{1}{a_{n-1}}-\frac{1}{a_n}\right)+\frac{1}{a_n} \\ &= \frac{1}{a_1} \\ &\le 1 \end{aligned} $
    540 
    541 The equality holds if and only if $\gcd(a_i,a_{i+1})=a_{i+1}-a_i$ for all $1\le i \lt n$, and $a_1=1$. Thus, the problem is transformed into counting the number of sequences that satisfy these conditions.
    542 
    543 The condition $\gcd(x,y)=y-x$ implies that $y-x$ is a divisor of $x$. In other words, there exists a divisor $d$ of $x$ such that $y=x+d$. Therefore, the total number of such valid pairs $(x,y)$ is only $\mathcal O(m \ln m)$. Consequently, we can easily obtain the answer using dynamic programming with a time complexity of $O(nm\ln m)$.
    544 
    545 **Implementation**
    546 
    547 ```
    548 #include<bits/stdc++.h>
    549 #define cint const int
    550 #define uint unsigned int
    551 #define cuint const unsigned int
    552 #define ll long long
    553 #define cll const long long
    554 #define ull unsigned long long
    555 #define cull const unsigned long long
    556 using namespace std;
    557 namespace FastIO
    558 {
    559     const int BUF_SIZE=1<<20;
    560     char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    561     char* in_ptr=in_buf+BUF_SIZE;
    562     char* out_ptr=out_buf;
    563     char get_char()
    564     {
    565         if(in_ptr==in_buf+BUF_SIZE)
    566         {
    567             in_ptr=in_buf;
    568             fread(in_buf,1,BUF_SIZE,stdin);
    569         }
    570         return *in_ptr++;
    571     }
    572     void put_char(char c)
    573     {
    574         if(out_ptr==out_buf+BUF_SIZE)
    575         {
    576             fwrite(out_buf,1,BUF_SIZE,stdout);
    577             out_ptr=out_buf;
    578         }
    579         *out_ptr++=c;
    580     }
    581     struct Flusher
    582     {
    583         ~Flusher()
    584         {
    585             if(out_ptr!=out_buf)
    586             {
    587                 fwrite(out_buf,1,out_ptr-out_buf,stdout);
    588             }
    589         }
    590     } flusher;
    591 }
    592 #define getchar FastIO::get_char
    593 #define putchar FastIO::put_char
    594 inline int read()
    595 {
    596     int x=0;
    597     bool zf=1;
    598     char ch=getchar();
    599     while(ch<'0'||ch>'9')
    600     {
    601         if(ch=='-')
    602         {
    603             zf=0;
    604         }
    605         ch=getchar();
    606     }
    607     while(ch>='0'&&ch<='9')
    608     {
    609         x=(x<<1)+(x<<3)+(ch^48);
    610         ch=getchar();
    611     }
    612     return zf?x:-x;
    613 }
    614 void print(cint x)
    615 {
    616     if(x==0)
    617     {
    618         putchar('0');
    619         return;
    620     }
    621     char buf[12];
    622     int len=0,y=x;
    623     if(y<0)
    624     {
    625         putchar('-');
    626         y=-y;
    627     }
    628     while(y)
    629     {
    630         buf[len++]=(y%10)+'0';
    631         y/=10;
    632     }
    633     while(len--)
    634     {
    635         putchar(buf[len]);
    636     }
    637 }
    638 inline void princh(cint x,const char ch)
    639 {
    640     print(x);
    641     putchar(ch);
    642 }
    643 cint N=3000,M=3000;
    644 cint mod=998244353;
    645 int n,m;
    646 int a[N+1];
    647 int dp[N+1][M+1];
    648 vector<int>d[M+1];
    649 int ans;
    650 void solve()
    651 {
    652     n=read();
    653     m=read();
    654     for(int i=1;i<=n;++i)
    655     {
    656         a[i]=read();
    657     }
    658     if(a[1]>1)
    659     {
    660         princh(0,'\n');
    661         return;
    662     }
    663     dp[1][1]=1;
    664     for(int i=2;i<=n;++i)
    665     {
    666         for(int j=1;j<=m;++j)
    667         {
    668             dp[i][j]=0;
    669             for(int x:d[j])
    670             {
    671                 (dp[i][j]+=dp[i-1][j-x])>=mod?(dp[i][j]-=mod):0;
    672             }
    673         }
    674         if(a[i])
    675         {
    676             for(int j=1;j<=m;++j)if(j!=a[i])dp[i][j]=0;
    677         }
    678     }
    679     ans=0;
    680     for(int j=1;j<=m;++j)
    681     {
    682         (ans+=dp[n][j])>=mod?(ans-=mod):0;
    683     }
    684     princh(ans,'\n');
    685 }
    686 int main()
    687 {
    688     // freopen(".in","r",stdin);
    689     // freopen(".out","w",stdout);
    690     for(int i=1;i<=M;++i)
    691     {
    692         for(int j=i;j<=M;j+=i)
    693         {
    694             d[j].push_back(i);
    695         }
    696     }
    697     int T=read();
    698     while(T--)solve();
    699     return 0;
    700 }
    701 ```
    702 
    703 ## [2183F — Jumping Man](https://codeforces.com/contest/2183/problem/F)
    704 
    705 Idea & Preparation: [Neil_Qian](/profile/Neil_Qian "Candidate Master Neil_Qian")
    706 
    707 **Rate The Problem!**
    708 
    709 * Good Problem
    710 * Okay Problem
    711 * Bad Problem
    712 * Didn't Solve
    713 
    714 **Hint 1**
    715 
    716 Calculating the sum of squares of counts is difficult.
    717 
    718 **Hint 2**
    719 
    720 Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings.
    721 
    722 **Hint 3**
    723 
    724 Try dynamic programming.
    725 
    726 **Hint 4**
    727 
    728 The DP transition is continuous over the DFS sequence.
    729 
    730 **Solution**
    731 
    732 Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings.
    733 
    734 Let $f_{i,j}$ represent the number of ways to choose two strings located at nodes $i$ and $j$, respectively, within their subtrees. Clearly, $f_{i,j}$ has a non-zero value only if $c_i = c_j$, where $c$ denotes the string sequence.
    735 
    736 Then, $f_{p,q}$ contributes to $f_{i,j}$ if and only if $p$ is in the subtree of $i$ and $q$ is in the subtree of $j$. By performing a depth-first search (DFS) on the tree and marking timestamps, the $(x, y)$ pairs of contributing $f_{p,q}$ must form a rectangle (as in a DFS sequence, each subtree is a range). Sorting by reverse DFS order and computing $2$ — dimensional suffix sums suffices.
    737 
    738 The time complexity is $O(n^2)$.
    739 
    740 **Implementation**
    741 
    742 ```
    743 #include <bits/stdc++.h>
    744 
    745 using namespace std;
    746 
    747 typedef long long ll;
    748 
    749 const int MAXN = 5e3 + 10;
    750 const int mod = 998244353;
    751 
    752 inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }
    753 inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; }
    754 inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; }
    755 
    756 int T, n, ans[MAXN], sum[MAXN][MAXN]; char s[MAXN];
    757 
    758 vector<int> g[MAXN]; int in[MAXN], out[MAXN], rev[MAXN], id;
    759 
    760 void init(int u, int f = 0) {
    761 	in[u] = ++id, rev[id] = u;
    762 	for (int v : g[u]) if (v != f) init(v, u);
    763 	out[u] = id;
    764 }
    765 
    766 inline 
    767 int query(int al, int ar, int bl, int br) {
    768 	return sub(add(sum[al][bl], sum[ar + 1][br + 1]), add(sum[al][br + 1], sum[ar + 1][bl]));
    769 }
    770 
    771 int main() {
    772 	for (scanf("%d", &T); T--; ) {
    773 		scanf("%d%s", &n, s + 1), id = 0;
    774 		for (int i = 1, u, v; i < n; i++) {
    775 			scanf("%d%d", &u, &v);
    776 			g[u].emplace_back(v), g[v].emplace_back(u);
    777 		}
    778 		init(1);
    779 		for (int i = n; i; i--) {
    780 			for (int j = n; j; j--) {
    781 				if (s[rev[i]] == s[rev[j]]) {
    782 					sum[i][j] = add(query(in[rev[i]] + 1, out[rev[i]], in[rev[j]] + 1, out[rev[j]]), 1);
    783 				}
    784 				cadd(sum[i][j], sub(add(sum[i + 1][j], sum[i][j + 1]), sum[i + 1][j + 1]));
    785 			}
    786 		}
    787 		for (int i = 1; i <= n; i++) {
    788 			printf("%d ", query(in[i], out[i], in[i], out[i]));
    789 		}
    790 		puts("");
    791 		for (int i = 1; i <= n; i++) g[i].clear();
    792 		for (int i = 1; i <= n; i++) {
    793 			for (int j = 1; j <= n; j++) sum[i][j] = 0;
    794 		}
    795 	}
    796 }
    797 ```
    798 
    799 ## [2183G — Snake Instructions](https://codeforces.com/contest/2183/problem/G)
    800 
    801 Idea & Preparation: [xvchongyv](/profile/xvchongyv "Expert xvchongyv") & [wangmarui](/profile/wangmarui "Grandmaster wangmarui")
    802 
    803 **Rate The Problem!**
    804 
    805 * Good Problem
    806 * Okay Problem
    807 * Bad Problem
    808 * Didn't Solve
    809 
    810 **Hint 1**
    811 
    812 Consider under what circumstances you need to return $-1$.
    813 
    814 **Answer**
    815 
    816 When there are three consecutive snakes with speeds $0, x, 0$, we cannot determine whether $x$ is $1$ or $2$, so we need to return $-1$ in this case. In all other situations, it's easy to have a scheme that uniquely determines all snakes' speeds.
    817 
    818 **Hint 2**
    819 
    820 Consider what information you can get by querying the string `L`.
    821 
    822 **Hint 3**
    823 
    824 The case analysis process for this problem is not complicated.
    825 
    826 **Hint 4**
    827 
    828 Consider querying three fixed strings to determine all snakes' speeds.
    829 
    830 **Solution**
    831 
    832 Consider querying the three strings: `L`, `LR`, and `R`.
    833 
    834 It can be observed that the sizes of the sets returned from querying `L` and `LR` are the same. The specific proof states that after querying `LR`, the positions of the surviving snakes are exactly their initial positions. Since the relative order of the snakes remains unchanged, performing operation `R` after operation `L` will definitely not cause any two snakes to collide. Therefore, the sizes of the returned sets are the same.
    835 
    836 By establishing a one-to-one correspondence with the initial coordinates, we can easily deduce the speeds of all snakes that survive after performing operation `L`.
    837 
    838 At this point, we only lack the speeds of the snakes that died after performing operation `L`. A simple case analysis reveals the following scenarios (the first number on the right represents the speed of the snake that died after operation `L`, and `_` indicates that there is no snake at that initial position):
    839 
    840 * `01`.
    841 * `02`.
    842 * `0_2`.
    843 * `12`.
    844 
    845 We can directly solve the problem by classifying these cases, but the implementation might be somewhat cumbersome. Therefore, let's consider a more concise approach to the case analysis.
    846 
    847 First, try to determine some snakes with speed $2$. For the position and speed of such a snake, the following cases allow direct determination:
    848 
    849 * The previous snake is at a distance of $1$ and has been determined to have speed $1$.
    850 * The previous snake is at a distance of $1$ and has not been determined. Let's explain why this snake's speed is certain in this case:
    851 * If the previous snake's speed is $0$, it will definitely not be killed in a collision, so this case is impossible.
    852 * If the previous snake's speed is at least $1$, then this snake must have a speed of at least $2$ to catch up and collide with the previous snake. Therefore, this snake's speed is at least $2$.
    853 * The previous snake is at a distance of $2$ and has been determined to have speed $0$.
    854 
    855 The case analysis above naturally eliminates the `0_2` and `12` scenarios.
    856 
    857 Now, only the `01` and `02` cases remain. It can be observed that only the patterns `010` and `020` are indistinguishable. Therefore, we can initially ignore this situation: first find one valid solution, and then check if this solution contains such an indistinguishable pattern.
    858 
    859 Otherwise, since the snake immediately after this one must have a speed of at least $1$ (under the condition of a unique solution), the position this snake would reach if it moved ignoring obstacles is exactly the position of the first snake whose position is $\ge$ this snake's position after performing the `R` query. If this snake does not come into contact with any other snake while moving right, its position can also be directly determined. Therefore, we can directly deduce the speeds of all snakes using this method.
    860 
    861 Time complexity: $O(\sum n)$ or $O(\sum n \log n)$.
    862 
    863 **Implementation**
    864 
    865 ```
    866 /*
    867 OI 2025 RP++!!!
    868 
    869 author: wmrqwq[alsu]
    870 
    871 time: 2025/7/12
    872 
    873 contest:
    874 
    875 Tips:
    876 
    877 RE, MLE?
    878 greedy, dp?
    879 natural time?
    880 map, umap?
    881 giveup rating, get score.
    882 brute force, right solution?
    883 %mod? std/run/maker/checker?
    884 add bruteforce?
    885 clear?
    886 double, long double?
    887 O(n)? O(n^2)!
    888 make data!
    889 
    890 last but not least.
    891 
    892 bruteforce -> SegTree?
    893 Think more.
    894 */
    895 //#pragma GCC optimize("Ofast")
    896 //#pragma GCC optimize("unroll-loops")
    897 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
    898 #include<bits/stdc++.h>
    899 using namespace std;
    900 //#define map unordered_map
    901 #define re register
    902 #define ll long long
    903 #define cll const ll
    904 #define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)
    905 #define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
    906 #define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))
    907 #define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))
    908 #define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)
    909 #define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)
    910 #define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))
    911 #define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))
    912 #define pii pair<ll,ll>
    913 #define mid ((l+r)>>1)
    914 #define lowbit(x) (x&-x)
    915 #define pb push_back
    916 #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    917 // #define endl '\n'
    918 #define QwQ return 0;
    919 #define db long double
    920 #define ull unsigned long long
    921 #define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y))
    922 #define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2)
    923 #define x first
    924 #define y second
    925 #define aty cout<<"Yes\n";
    926 #define atn cout<<"No\n";
    927 #define cfy cout<<"YES\n";
    928 #define cfn cout<<"NO\n";
    929 #define xxy cout<<"yes\n";
    930 #define xxn cout<<"no\n";
    931 #define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
    932 #define printat(x) x?cout<<"Yes\n":cout<<"No\n";
    933 #define printxx(x) x?cout<<"yes\n":cout<<"no\n";
    934 #define maxqueue priority_queue<ll>
    935 #define minqueue priority_queue<ll,vector<ll>,greater<ll>>
    936 #define bug1 cout<<"bug1,AWaDa?\n";
    937 #define bug2 cout<<"bug2,AWaDa!\n";
    938 #define bug3 cout<<"bug3,AKTang?\n";
    939 #define bug4 cout<<"bug4,AKTang!\n";
    940 #define IM (ll)1e9
    941 #define LM (ll)1e18
    942 #define MIM (ll)-1e9
    943 #define MLM (ll)-1e18
    944 #define sort stable_sort
    945 ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;}
    946 ll pw(ll x,ll y,ll mod){if(mod==1)return 0;if(y==0)return 1;if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;}
    947 ll pw(ll x){return 1ll<<x;}
    948 template<typename T1,typename T2>bool Max(T1&x,T2 y){if(y>x)return x=y,1;return 0;}template<typename T1,typename T2>bool Min(T1&x,T2 y){if(y<x)return x=y,1;return 0;}ll Ss=chrono::steady_clock::now().time_since_epoch().count();mt19937_64 Apple(Ss);ll rand_lr(ll l,ll r){return Apple()%(r-l+1)+l;}
    949 // cll mod=1e9+7,N=300010;ll fac[N],inv[N];void init(){fac[0]=1;forl(i,1,N-5)fac[i]=i*fac[i-1],fac[i]%=mod;inv[N-5]=pw(fac[N-5],mod-2,mod);forr(i,N-5,1)inv[i-1]=inv[i]*i%mod;}ll C(ll n,ll m){if(n<m || m<0)return 0;return (fac[n]%mod)*(inv[n-m]*inv[m]%mod)%mod;}
    950 // void add(ll&x,ll y){x=((x+y)%mod+mod)%mod;}void del(ll&x,ll y){x=(x%mod-y%mod+mod)%mod;}
    951 ll _t_;
    952 struct BIT{
    953     ll maxn;
    954     ll tree[1000010];
    955     void clear(ll l){
    956         forl(i,0,l)
    957             tree[i]=0;
    958     }
    959     void add(ll x,ll y){
    960         for(;x<=maxn;x+=lowbit(x))
    961             tree[x]+=y;
    962     }
    963     ll query(ll x){
    964         ll S=0;
    965         for(;x;x-=lowbit(x))
    966             S+=tree[x];
    967         return S;
    968     }
    969     ll query(ll l,ll r){
    970         return query(r)-query(l-1);
    971     }
    972 };
    973 // ll lg[1000010];
    974 void Init(){
    975     // forl(i,2,1e6+5)
    976     //     lg[i]=lg[i>>1]+1;
    977 }
    978 //sunny
    979 ll n;
    980 ll a[100010];
    981 ll ans[100010];
    982 vector<ll>vl,vr,vlr;
    983 //tulpa
    984 void ask(string s,vector<ll>&v)
    985 {
    986     cout<<"? "<<s<<endl;
    987     v.pb(rd());
    988     forl(i,1,v[0])
    989         v.pb(rd());
    990 }
    991 /*
    992 012
    993 
    994 01
    995 02
    996 
    997 120
    998 */
    999 void _clear(){}
   1000 void solve()
   1001 {
   1002     _clear();
   1003     vl.clear(),vr.clear(),vlr.clear();
   1004     cin>>n;
   1005     forl(i,1,n)
   1006         cin>>a[i],
   1007         ans[i]=-1;
   1008     ask("L",vl),ask("R",vr),ask("LR",vlr);
   1009     ll sz=vlr[0],L=1;
   1010     forl(i,1,n)
   1011     {
   1012         while(L<=sz && vlr[L]<a[i])
   1013             L++;
   1014         if(L<=sz && vlr[L]==a[i])
   1015             ans[i]=vlr[L]-vl[L];
   1016     }
   1017     forl(i,2,n)
   1018         if(ans[i]==-1 && ((a[i]-a[i-1]==1 && abs(ans[i-1])==1) || (a[i]-a[i-1]==2 && ans[i-1]==0)))
   1019         {
   1020             // if(ans[i-1]==-1)
   1021             //     ans[i-1]=1;
   1022             ans[i]=2;
   1023         }
   1024     forl(i,1,n)
   1025         if(ans[i]==-1)
   1026             ans[i]=*lower_bound(vr.begin()+2,vr.end(),a[i])-a[i];
   1027     forl(i,1,n-2)
   1028         if(a[i]+1==a[i+1] && a[i+1]+1==a[i+2] && ans[i]+ans[i+2]==0 && ans[i+1])
   1029         {
   1030             cout<<"! "<<-1<<endl;
   1031             return ;
   1032         }
   1033     cout<<"! ";
   1034     forl(i,1,n)
   1035         cout<<ans[i]<<' ';
   1036     cout<<endl;
   1037 }
   1038 int main()
   1039 {
   1040     Init();
   1041 //    freopen("tst.txt","r",stdin);
   1042 //    freopen("sans.txt","w",stdout);
   1043     IOS;
   1044     _t_=1;
   1045     cin>>_t_;
   1046     while(_t_--)
   1047         solve();
   1048     QwQ;
   1049 }
   1050 ```
   1051 
   1052 ## [2183H — Minimise Cost](https://codeforces.com/contest/2183/problem/H)
   1053 
   1054 Idea & Preparation: [Hoks_](/profile/Hoks_ "Grandmaster Hoks_") Special Thanks: [Sorasaki_Hina](/profile/Sorasaki_Hina "Master Sorasaki_Hina")
   1055 
   1056 **Rate The Problem!**
   1057 
   1058 * Good Problem
   1059 * Okay Problem
   1060 * Bad Problem
   1061 * Didn't Solve
   1062 
   1063 **Hint 1**
   1064 
   1065 Subsequences are too hard; can we find some properties? How should we approach the case where $k\le n\le500$?
   1066 
   1067 **Hint 2**
   1068 
   1069 The approach for $k\le n\le500$ is too naive; how can we optimize it? What if $k\le n\le5000$?
   1070 
   1071 **Hint 3**
   1072 
   1073 What if we are guaranteed that the count of positive numbers $m \le 5000$?
   1074 
   1075 **Hint 4**
   1076 
   1077 The requirement of **exactly** $k$ segments, combined with the previous optimizations, suggests what technique? Consider the data constraints.
   1078 
   1079 **Solution**
   1080 
   1081 Sort $a$ in non-decreasing order. The cost of a group depends only on the multiset of its values, so the original positions are irrelevant.
   1082 
   1083 **Lemma 1 (canonical form).** There exists an optimal partition whose groups are contiguous blocks in the sorted array. If their lengths are $l_1,l_2,\dots,l_k$ in order of increasing values, then $l_1\ge l_2\ge\cdots\ge l_k$.
   1084 
   1085 **Proof of Lemma 1**
   1086 
   1087 Fix the block sizes. Every element is multiplied by the size of its block, so the total cost is a dot product between the values and a multiset of multipliers in which every block size $\ell$ occurs exactly $\ell$ times. By the rearrangement inequality, pairing values in non-decreasing order with multipliers in non-increasing order does not increase the cost. Regrouping equal multipliers into blocks of the corresponding sizes gives contiguous blocks with non-increasing lengths.
   1088 
   1089 Henceforth, partitions are partitions of the sorted array into contiguous blocks. Let $S_0=0$, $S_i=a_1+\cdots+a_i$, and
   1090 
   1091 $C(j,i)=(i-j)(S_i-S_j)$
   1092 
   1093 be the cost of the block $a_{j+1}\dots a_i$. If $f_{t,i}$ is the minimum cost of partitioning the first $i$ elements into exactly $t$ blocks, then
   1094 
   1095 $f_{t,i}=\min_{0\le j \lt i}\bigl(f_{t-1,j}+C(j,i)\bigr),$
   1096 
   1097 which gives an $O(n^2k)$ algorithm if evaluated directly.
   1098 
   1099 For $0\le a\le b\le c\le d\le n$, expansion gives
   1100 
   1101 $\bigl(C(a,d)+C(b,c)\bigr)-\bigl(C(a,c)+C(b,d)\bigr)=(d-c)(S_b-S_a)+(b-a)(S_d-S_c). \tag{1}$
   1102 
   1103 If all elements are non-negative, the right-hand side is non-negative, so
   1104 
   1105 $C(a,c)+C(b,d)\le C(a,d)+C(b,c). \tag{2}$
   1106 
   1107 This quadrangle inequality (QI) implies decision monotonicity in each DP layer, and therefore an $O(nk)$ algorithm for non-negative arrays. For arbitrary signs, (2) may fail.
   1108 
   1109 Let
   1110 
   1111 $z=\#\{i:a_i\le 0\},\qquad m=n-z=\#\{i:a_i \gt 0\}.$
   1112 
   1113 Thus $0$ is grouped with the non-positive elements. Let $\mathcal P_0$ be the partition whose first block contains the smallest $n-k+1$ elements and whose other blocks are singletons; its cost is
   1114 
   1115 $\operatorname{base}=(n-k+1)S_{n-k+1}+\bigl(S_n-S_{n-k+1}\bigr). \tag{3}$
   1116 
   1117 **Lemma 2 (boundary shift).** In a canonical partition with at least two blocks, let the first two block lengths be $p\ge q$. If $q\ge2$ and the first element $x$ of the second block satisfies $x\le0$, moving $x$ into the first block does not increase the cost.
   1118 
   1119 **Proof of Lemma 2**
   1120 
   1121 Let $A$ be the sum of the first block and $U$ the sum of the second block after removing $x$. The move changes the cost by
   1122 
   1123 $\bigl((p+1)(A+x)-pA\bigr)+\bigl((q-1)U-q(x+U)\bigr)=A-U+(p+1-q)x.$
   1124 
   1125 All elements of the first block are at most $x$, so $A\le px$; all elements counted in $U$ are at least $x$, so $U\ge(q-1)x$. Hence $A-U\le(p-q+1)x\le0$, using $p\ge q$ and $x\le0$. Also $(p+1-q)x\le0$.
   1126 
   1127 After a shift, reapply Lemma 1 to the later blocks. The first block has grown and remains a longest block, so its set of elements is unchanged by this reordering. If $k=1$, then $\mathcal P_0$ is the unique partition; below let $k\ge2$.
   1128 
   1129 **Case 1: $k \gt m$.** Then $\mathcal P_0$ is optimal. Indeed, in a canonical partition, if the second block is a singleton then all later blocks are singletons. Otherwise its first element must be non-positive: if it were positive, all remaining elements would be positive, at most $m$ elements in $k-1\ge m$ blocks, forcing all those blocks to be singletons. Lemma 2 therefore moves the first cut one step right without increasing the cost. Repeating ends at $\mathcal P_0$. In particular, all positive elements are singletons.
   1130 
   1131 **Case 2: $k\le m$.** There is an optimal partition whose first block contains all non-positive elements. To see this, let the first cut be $b \lt z$ in a canonical optimal partition. The second block starts with a non-positive element. It cannot be a singleton: otherwise all later blocks would be singletons and $b=n-k+1\ge n-m+1=z+1$, a contradiction. Lemma 2 hence increases $b$ by one without increasing the cost. Repeating gives $b\ge z$. Later blocks are then positive, although the first block may also contain positive elements.
   1132 
   1133 This structural form with monotone DP on the positive suffix gives $O(nk)$. For the full constraints, use Aliens' trick. Its inner DP requires QI also for transitions from cut $0$, and deleting cuts inside the non-positive prefix is not enough: for $a=(-100,1,1,1)$ and $(a,b,c,d)=(0,2,3,4)$, the right-hand side of (1) is negative. We extend the forced prefix further.
   1134 
   1135 Start with $T=z$. While $t=T+1\le n$ satisfies
   1136 
   1137 $tS_t-(t-1)S_{t-1} \lt a_t, \tag{4}$
   1138 
   1139 increase $T$ to $t$. The left side is the marginal cost of appending $a_t$ to the first $t-1$ elements as one block.
   1140 
   1141 **Claim.** For $k\le m$, there is an optimal partition whose first cut is at least $T$, unless it is $\mathcal P_0$.
   1142 
   1143 **Proof of the claim**
   1144 
   1145 Take a canonical optimal partition whose first block contains all non-positive elements and whose first cut is $b \lt T$. Put $t=b+1$. Then $a_t \gt 0$ and (4) holds. If the second block has length $L\ge2$ and its remaining sum after removing $a_t$ is $U \gt 0$, moving $a_t$ into the first block changes the cost by
   1146 
   1147 $\bigl(tS_t-(t-1)S_{t-1}\bigr)-La_t-U \lt 0,$
   1148 
   1149 because the bracket is less than $a_t$ by (4). Reapply Lemma 1 to the later blocks and repeat. If at some stage the second block is a singleton in canonical form, all later blocks are singletons, so the partition is $\mathcal P_0$.
   1150 
   1151 Thus, apart from $\mathcal P_0$, only cuts in
   1152 
   1153 $\mathcal J=\{0\}\cup\{j:T\le j \lt n\} \tag{5}$
   1154 
   1155 are needed. If $T \gt n-k+1$, no partition with first cut in $\mathcal J$ has $k$ blocks, so the answer is $\operatorname{base}$. If $T\le n-k+1$, then $\mathcal P_0$ itself uses only cuts from $\mathcal J$.
   1156 
   1157 **Lemma 3.** Inequality (2) holds for all $a,b\in\mathcal J$ with $a\le b\le c\le d$.
   1158 
   1159 **Proof of Lemma 3**
   1160 
   1161 If $a\ge T$, all elements after $a$ are positive, so both differences in (1) are non-negative. Let $a=0$ and $b\ge T$. Then (1) becomes
   1162 
   1163 $(d-c)S_b+b(S_d-S_c). \tag{6}$
   1164 
   1165 Since $c\ge b\ge T\ge z$, we have $S_d-S_c\ge(d-c)a_{b+1}$. It remains to prove $S_b+b a_{b+1}\ge0$ for $T\le b \lt n$.
   1166 
   1167 If $T \lt n$, failure of (4) at $t=T+1$ gives $(T+1)S_{T+1}-TS_T\ge a_{T+1}$, equivalently $S_T+T a_{T+1}\ge0$. For $b \gt T$, both $S_b\ge S_T$ and $b a_{b+1}\ge T a_{T+1}$, since the added elements are positive and $a_{T+1} \gt 0$. Hence $S_b+b a_{b+1}\ge0$ for all $b\ge T$, and (6) is at least $(d-c)(S_b+b a_{b+1})\ge0$.
   1168 
   1169 Let $G(t)$ be the minimum cost of a partition into exactly $t$ blocks using cuts from $\mathcal J$, where $1\le t\le n-T+1$.
   1170 
   1171 **Lemma 4.** $G$ is convex: $G(t-1)+G(t+1)\ge2G(t)$ for $2\le t\le n-T$.
   1172 
   1173 **Proof of Lemma 4**
   1174 
   1175 Let optimal partitions with $t-1$ and $t+1$ blocks have cut sequences $0=x_0 \lt \cdots \lt x_{t-1}=n$ and $0=y_0 \lt \cdots \lt y_{t+1}=n$. Choose the smallest $j\in[1,t-1]$ with $y_{j+1}\le x_j$; it exists since $y_t \lt n=x_{t-1}$, and minimality gives $x_{j-1} \lt y_j \lt y_{j+1}\le x_j$.
   1176 
   1177 Exchange the suffixes after this crossing: use the first partition up to $x_{j-1}$, the block $(x_{j-1},y_{j+1}]$, and the second partition after $y_{j+1}$; symmetrically, use the second partition up to $y_j$, the block $(y_j,x_j]$, and the first partition after $x_j$. Both resulting partitions have $t$ blocks and cuts in $\mathcal J$. They differ from the original pair only in the crossing blocks, where Lemma 3 gives
   1178 
   1179 $C(x_{j-1},y_{j+1})+C(y_j,x_j)\le C(x_{j-1},x_j)+C(y_j,y_{j+1}).$
   1180 
   1181 Hence the sum of their costs is at most $G(t-1)+G(t+1)$, while each cost is at least $G(t)$.
   1182 
   1183 Now apply Aliens' trick. For an integer reward $\mu$ per block, let $\operatorname{check}(\mu)$ be the minimum of $\text{cost}-\mu\cdot(\text{number of blocks})$ over partitions with cuts in $\mathcal J$, and let $\operatorname{cnt}(\mu)$ be the corresponding number of blocks, with ties broken toward fewer blocks. Adding the same constant $-\mu$ to every block preserves (2). By Lemma 4, $\operatorname{cnt}(\mu)$ is non-decreasing in $\mu$. For the largest $\mu$ with $\operatorname{cnt}(\mu)\le k$, the standard recovery gives $G(k)=\operatorname{check}(\mu)+\mu k$. The answer is $\min(\operatorname{base},G(k))$.
   1184 
   1185 To compute $\operatorname{check}(\mu)$, let $dp[i]$ be the optimal pair (penalised value, block count) for the first $i$ elements; in the implementation, `ck(mu)` evaluates this DP and returns whether the resulting block count is at most $k$. Then $dp[0]=(0,0)$ and, for $i\ge\max(T,1)$,
   1186 
   1187 $dp[i]=\min_{j\in\mathcal J,\ j \lt i}\bigl(dp[j]+C(j,i)-\mu\bigr),$
   1188 
   1189 with the block count increased by $1$ in each transition. In the code, `a` is overwritten by the prefix sums $S$, `p` is $\max(T,1)$, the precomputed `ans` is $\operatorname{base}$, and `calc(i,j,mu)` evaluates the transition above.
   1190 
   1191 By Lemma 3, the optimal $j$ is monotone in $i$. The queue `q` stores candidate cuts in increasing order, and `lim[idx]` is the first right endpoint at which `q[idx + 1]` is at least as good as `q[idx]`. Removing front candidates with `lim[l] <= i` therefore leaves an optimal cut for $dp[i]$. To insert $i$, `find(i,q[r],mu)` binary-searches the first endpoint where $i$ beats the tail candidate `q[r]`; if this point is at most `lim[r - 1]`, then `q[r]` never becomes optimal and is discarded. Each cut enters and leaves the queue once, so one check takes $O(n\log n)$ time.
   1192 
   1193 The binary search over $\mu$ needs $O(\log V)$ checks, where $V=O(n^2\max_i|a_i|)$. The total complexity is $O(n\log n\log V)$ time and $O(n)$ memory per test case after sorting. All costs are stored in `__int128`.
   1194 
   1195 **Implementation**
   1196 
   1197 ```
   1198 #include <bits/stdc++.h>
   1199 using namespace std;
   1200  
   1201 #define S cerr << "SYT AK IOI" << endl;
   1202 #define M cerr << "MKF AK IOI" << endl;
   1203  
   1204 using ll = long long;
   1205 using pii = pair<int, int>;
   1206 using uint = unsigned int;
   1207 using ull = unsigned long long;
   1208 mt19937 rnd(0 ^ (*new int));
   1209 // #define int long long                                             //use it if possible
   1210 #define pb(x) push_back(x)
   1211 #define F(i, a, b) for (int i = (a), i##end = (b); i <= (i##end); ++i)
   1212 #define UF(i, a, b) for (int i = (a), i##end = (b); i >= (i##end); --i)
   1213 #define gc() getchar()
   1214 #define pc putchar
   1215 #define popcount(x) __builtin_popcount(x)
   1216  
   1217 inline void init();
   1218 inline void IO();
   1219 __int128 n,k,p;
   1220 __int128 a[1000100],lim[1000100],q[1000100];
   1221 array<__int128,2>dp[1000100];
   1222 ll rd()
   1223 {
   1224 	ll x;
   1225 	cin>>x;
   1226 	return x;
   1227 }
   1228 inline array<__int128,2> calc(__int128 i,__int128 j,__int128 x){
   1229     return (array<__int128,2>){dp[j][0]+(i-j)*(a[i]-a[j])-x,dp[j][1]+1};
   1230 }
   1231 inline bool c2(__int128 x,__int128 i,__int128 j,__int128 m){
   1232     return calc(x,j,m)>=calc(x,i,m);
   1233 }
   1234 inline __int128 find(__int128 i,__int128 j,__int128 m){
   1235     int l=i,r=n,mid,res=n+1;
   1236     while(l<=r) c2(mid=l+r>>1,i,j,m)?res=mid,r=mid-1:l=mid+1;
   1237     return res;
   1238 }
   1239 inline __int128 ck(__int128 mid){
   1240     for(__int128 i=p,l=1,r=1;i<=n;i++){
   1241         for(;l<r&&lim[l]<=i;l++);dp[i]=calc(i,q[l],mid);
   1242         for(;l<r&&lim[r-1]>=find(i,q[r],mid);r--);
   1243         lim[r]=find(i,q[r],mid);q[++r]=i;
   1244     }
   1245     return dp[n][1]<=k;
   1246 }
   1247 void print(__int128 x){if(x<0) putchar('-'),x=-x;if(x>9) print(x/10);putchar(x%10+'0');}
   1248 inline void mian()
   1249 {
   1250 //    cin>>n>>k;
   1251 	n=rd(),k=rd();
   1252     F(i,1,n)a[i]=rd();
   1253     sort(a+1,a+1+n);
   1254     F(i,2,n)a[i]+=a[i-1];
   1255     if(k==1){print(n*a[n]);putchar('\n');return;}
   1256     __int128 ans=(n-k+1)*a[n-k+1]+a[n]-a[n-k+1];p=1;
   1257     while(p<=n and a[p]-a[p-1]<=0)p++;
   1258     while(p<=n and p*a[p]-a[p]+a[p-1]<(p-1)*a[p-1])p++;
   1259     --p,p=max(p,(__int128)1);
   1260     if(n-p<k-1){print(ans);putchar('\n');return;}
   1261     __int128 l=-n*n*(__int128)(1e9),r=-l,mid,res=l;
   1262     while(l<=r) ck(mid=l+r>>1)?res=mid,l=mid+1:r=mid-1;
   1263     ck(res);
   1264     ans=min(ans,(__int128)k*res+dp[n][0]);
   1265     print(ans);putchar('\n');
   1266 }
   1267 signed main()
   1268 {
   1269     IO();
   1270     cin.tie(nullptr)->sync_with_stdio(false);
   1271     int T = 1;
   1272     #define multitest 1
   1273 #ifdef multitest
   1274     T=rd();
   1275 #endif
   1276     init();
   1277  
   1278     while (T--)
   1279         mian();
   1280     return 0;
   1281 }
   1282  
   1283 inline void init()
   1284 {
   1285 }
   1286  
   1287 #define NAME(x) #x
   1288 #define INNAME(x) NAME(x)
   1289 // #define FILEIO sub3_15
   1290 inline void IO()
   1291 {
   1292 #ifdef FILEIO
   1293     freopen(INNAME(FILEIO) ".in", "r", stdin), freopen(INNAME(FILEIO) ".out", "w", stdout);
   1294 #endif
   1295 }
   1296 ```
   1297 
   1298 ## [2183I1 — Pairs Flipping (Easy Version)](https://codeforces.com/contest/2183/problem/I1)
   1299 
   1300 Idea & Preparation: [Network_Error](/profile/Network_Error "Grandmaster Network_Error") Special Thanks: [N_z__](/profile/N_z__ "International Grandmaster N_z__")
   1301 
   1302 **Rate the problem**
   1303 
   1304 * Good Problem
   1305 * Okay Problem
   1306 * Bad Problem
   1307 * Didn't Solve
   1308 
   1309 **Hint 1**
   1310 
   1311 What if $s=1111\ldots$?
   1312 
   1313 **Hint 2**
   1314 
   1315 Try dividing the sequence into two equal halves, eliminating both halves by assigning odd and even lengths respectively.
   1316 
   1317 **Hint 3**
   1318 
   1319 Try processing recursively to reduce $n$ to a smaller scale.
   1320 
   1321 **Hint 4**
   1322 
   1323 Try further optimizing one of the two halves.
   1324 
   1325 **Solution**
   1326 
   1327 If $n$ is even, we only consider $s_1s_2\ldots s_{n-1}$. Now assume that $n$ is odd. Let $m=\frac{n-1}2$.
   1328 
   1329 Consider dividing the $n$ numbers into the first $m$ and the last $m+1$ parts. The first $m$ are eliminated using odd lengths in $[1,m-1]$, and the last $m+1$ are eliminated using even lengths in $[1,m]$. (Assume that $m$ is even; it is similar when $m$ is odd.)
   1330 
   1331 Let $solvePartially(l,r,p)$ denote the process of considering that there are 1s only in the interval $[l,r]$ and at some position $p$ outside $[l,r]$, and only using lengths in $[1,r-l]$ to eliminate. If $s_l=s_r=0$ or $s_l=s_r=1$, we operate on $l,r$ and recurse to $solvePartially(l+1,r-1,p)$; otherwise, assume that $s_l=1,s_r=0$ and $r \lt p$. If $p-(r-l)\in [l+1,r-1]$, we operate on $p-(r-l),p$ and then recurse to $solvePartially(l+1,r-1,l)$. Otherwise, the $1$ at $p$ is difficult to eliminate. Note that this situation occurs at most $\left\lfloor\log_3\frac{n}2\right\rfloor$ times, so we have obtained a solution with $c\le 2\left\lfloor\log_3\frac{n}2\right\rfloor+2$, roughly $24$ in the constraints of the problem, which is not acceptable.
   1332 
   1333 Proof that the above situation occurs at most $\left\lfloor\log_3\frac{n}2\right\rfloor$ times:
   1334 
   1335 * Note that the occurrence of an impossible elimination necessarily comes with $p-(r-l)\ge r$. Let $q+p=l+r$; then we must have $3(r-l)\le p-q$. Since $1\le r-l\le \frac{n}2$, it can happen at most $\left\lfloor\log_3\frac{n}2\right\rfloor$ times. In other words, each time an elimination is impossible, the interval length must reduce to $1/3$ of its original length.
   1336 
   1337 In the above approach, the left and right sides are almost independent. Since operations on the left side are allowed to extend to the right side, we try to eliminate the left side completely. Let $solveCompletely(l,r,p)$ denote that the interval $[l,r]$ except for some position $p$ on the left side has been completely eliminated, and that we still need to eliminate position $p$ together with parts outside $[l,r]$. If $s_l=s_r=1$ or $s_l=s_r=0$, we eliminate $l,r$ and recurse to $solveCompletely(l-1,r+1,p)$; otherwise, assume that $s_l=1,s_r=0$, we eliminate $p,p+r-l$ and then recurse to $solveCompletely(l-1,r+1,l)$. In this way, for the left half, we can reduce it to a single remaining position $p$. Finally, we have optimised to $c\le \left\lfloor\log_3 \frac n2\right\rfloor+2$, which is below $14$ under the constraints of this problem. The code is easy to implement.
   1338 
   1339 **Code**
   1340 
   1341 ```
   1342 #include <bits/stdc++.h>
   1343 using namespace std;
   1344 signed main() {
   1345     ios_base::sync_with_stdio(false); 
   1346     cin.tie(0);
   1347     int t;
   1348     cin >> t;
   1349     while(t--) {
   1350         int n;
   1351         cin >> n;
   1352         string a;
   1353         cin >> a;
   1354         vector<int> ops(n/2+5);
   1355         auto operate = [&](int i)->void{
   1356             if(ops[i]==0) return;
   1357             else {
   1358                 a[ops[i]-1]^=1;
   1359                 a[ops[i]-1+i]^=1;
   1360             }
   1361         };  
   1362         auto solveCompletely = [&](auto self, int l, int r, int x)->void{
   1363             if(l>r) return;
   1364             if(a[l]==a[r]) {
   1365                 if(a[l]=='1') ops[r-l]=l+1, operate(r-l);
   1366                 self(self, l+1, r-1, x);
   1367                 return;
   1368             }
   1369             if(x!=-1 && x<l) {
   1370                 if(x+r-l>=l) {
   1371                     ops[r-l]=x+1, operate(r-l);
   1372                 }
   1373             } else if(x!=-1 && x>r) {
   1374                 if(x-r+l<=r) {
   1375                     ops[r-l]=x-r+l+1, operate(r-l);
   1376                 }
   1377             }
   1378             if(a[l]=='1') {
   1379                 self(self, l+1, r-1, l);
   1380             } else {
   1381                 self(self, l+1, r-1, r);
   1382             }
   1383         };
   1384         auto solvePartially = [&](auto self, int l, int r)->int{
   1385             if(l>r) return -1;
   1386             if(l==r) if(a[l]=='1') return l; else return -1;
   1387             int x = self(self, l+1, r-1);
   1388             if(a[l]==a[r]) {
   1389                 if(a[l]=='1') ops[r-l]=l+1, operate(r-l);
   1390                 return x;
   1391             } else {
   1392                 if(x!=-1) {
   1393                     ops[r-l]=x+1, operate(r-l);
   1394                 }
   1395                 if(a[l]=='1') return l;
   1396                 else return r;
   1397             }
   1398         };
   1399         solvePartially(solvePartially, 0, (n-1)/2-1);
   1400         if(n%2) solveCompletely(solveCompletely, (n-1)/2, n-1, -1);
   1401         else solveCompletely(solveCompletely, (n-1)/2, n-2, -1);
   1402         for(int i=1; i<=n/2; i++) cout << ops[i] << " ";
   1403         cout << endl;
   1404     }
   1405     return 0;
   1406 }
   1407 ```
   1408 
   1409 ## [2183I2 — Pairs Flipping (Hard Version)](https://codeforces.com/contest/2183/problem/I2)
   1410 
   1411 Idea & Preparation: [Network_Error](/profile/Network_Error "Grandmaster Network_Error")
   1412 
   1413 **Rate the problem**
   1414 
   1415 * Good Problem
   1416 * Okay Problem
   1417 * Bad Problem
   1418 * Didn't Solve
   1419 
   1420 **Solution**
   1421 
   1422 In the I1 approach, we can observe that the main cost arises from isolated $1$'s outside the interval that occasionally cannot be eliminated. We consider optimizing this situation.
   1423 
   1424 The following diagram illustrates a scenario where such an elimination fails:
   1425 
   1426 ```
   1427  1111111111111|1??????0|1111111111110
   1428  p             l      r             q
   1429 ```
   1430 
   1431 Here, $p$ is the previous $1$ we could not eliminate (without loss of generality, assume $p \lt l$), the current interval being processed is $[l,r]$, and $l-p \ge r-l$ (making it impossible to eliminate directly using the previous method). $q$ is the symmetric point of $p$.
   1432 
   1433 At this point, the operation lengths we can use are $q-p-2, q-p-4, q-p-6, \ldots, r-l$. Note that $q-p$ is excluded because we have already used it earlier.
   1434 
   1435 Let the lengths of the three segments be $A$, $B$, and $C$, where $A=C$. This scenario is denoted as $F(A,B,C)$.
   1436 
   1437 Next, we will study in detail how to eliminate for $F(A,B,C)$.
   1438 
   1439 If $A \lt B-1$, we have essentially solved it in I1.
   1440 
   1441 For example, in a simple case where $r-l = l-p$ and $s_l=1, s_r=0$, we can apply an operation of length $r-l$ on $p$ and $l$, thereby eliminating both $p$ and $l$ simultaneously.
   1442 
   1443 For other cases, we can show that there is always a method to eliminate until only one $1$ remains, and this remaining $1$ can only be at one of the positions $l, l-1, l-2, r, r+1, r+2$. This part can be resolved through case analysis.
   1444 
   1445 Specifically, we only need to consider three cases: $A=B$, $A=B+1$, or $A=B-1$. If the case falls outside these three, such as $A',B',C'$, we always shift the interval inward and transform it into $A'-1, B'+2, C'-1$.
   1446 
   1447 We take $F(B-1,B,B-1)$ as an example to discuss the specific method.
   1448 
   1449 We further discuss based on $s_l$ and $s_r$. For convenience, we label the positions starting from $p$ as $0, \ldots, q-p$, and use a sequence to represent the positions operated on in order of decreasing length. Let the maximum available length be $L = q-p-2$. For example, the sequence $0,3,1$ means we first use an operation of length $L$ on $p$ and $p+L$, then use an operation of length $L-2$ on $p+3$ and $p+3+(L-2)$, and finally use an operation of length $L-4$ on $p+1$ and $p+1+(L-4)$.
   1450 
   1451 1. $s_l = s_r = 0$. We operate in order: $[0,1,2,\ldots,B-4], 2B-5, B-3$. Finally, a $1$ remains at index $B-2$.
   1452 2. $s_l = 1, s_r = 0$. We operate in order: $0, [(3,2),(5,4),(7,6),\ldots,(B-3,B-4)], B-1, 1$. Finally, a $1$ remains at index $B-2$.
   1453 3. $s_l = 0, s_r = 1$. We operate in order: $[0,1,2,\ldots,B-3], 2B-3$. Finally, a $1$ remains at index $B-2$.
   1454 4. $s_l = s_r = 1$. We operate in order: $[1,2,3,\ldots,B-2], 0$. Finally, a $1$ remains at index $2B-2$.
   1455 
   1456 Similarly, elimination methods for $F(B,B,B)$ and $F(B+1,B,B+1)$ can be obtained.
   1457 
   1458 Thus, between every two adjacent $1$'s that cannot be eliminated, we can always save one elimination, leaving a $1$ within a distance of at most $2$ from $l$ or $r$. Let the interval length be $s$. Whenever a $1$ cannot be eliminated, $s$ becomes at least $\frac19 s + \frac{2}{3}$. Therefore, the number of remaining $1$'s is approximately $\log_9\frac{n}{2}+O(1)$. Note that when the interval length is small, it may consume many $1$'s. A constant optimization is that when the recursion interval length does not exceed $18$, we can use an $O(n^2 2^n)$ dynamic programming approach to easily find the optimal solution, and the optimal solution can always leave no more than $1$ remaining $1$. Additionally, there are other optimizations, such as running the algorithm forward and backward on the sequence and taking the better result. All of these can pass.
   1459 
   1460 It can be proven that when $n \le 2 \times 10^6$, the total number of $1$'s does not exceed $7$.
   1461 
   1462 **Code**
   1463 
   1464 ```
   1465 #include<bits/stdc++.h>
   1466 using namespace std;
   1467 
   1468 const int N=2e6,DB=20;
   1469 int n,a[N+1];
   1470 int ans[N+1];
   1471 int mid;
   1472 inline void op(int x,int y)
   1473 {
   1474     if(x>y)swap(x,y);
   1475     ans[y-x]=x;
   1476     a[x]^=1;
   1477     a[y]^=1;
   1478 }
   1479 inline void del(int x,int y)
   1480 {
   1481     if(x>y)swap(x,y);
   1482     if(!ans[y-x])return;
   1483     ans[y-x]=0;
   1484     a[x]^=1;
   1485     a[y]^=1;
   1486 }
   1487 #define ppc __builtin_popcount
   1488 namespace DP{
   1489     int n;
   1490     bool f[DB+1][1<<DB+1];
   1491     int g[DB+1][1<<DB+1];
   1492     void dp()
   1493     {
   1494         n=DB;
   1495         f[n][0]=1;
   1496         for(int S=1;S<(1<<n);S<<=1)f[n][S]=1;
   1497         for(int len=n;len>=2;len-=2)
   1498         {
   1499             for(int S=0;S<(1<<n);S++)
   1500             {
   1501                 if(!f[len][S])continue;
   1502                 f[len-2][S]=1;
   1503                 g[len-2][S]=-1;
   1504                 for(int i=0;i+len-1<n;i++)
   1505                 {
   1506                     f[len-2][S^(1<<i)^(1<<(i+len-1))]=1;
   1507                     g[len-2][S^(1<<i)^(1<<(i+len-1))]=i;
   1508                 }
   1509             }
   1510         }
   1511     }
   1512     vector<int>ask(int S)
   1513     {
   1514         int len=0;
   1515         vector<int>ans(n+2);
   1516         while(len<n)
   1517         {
   1518             int pos=g[len][S];
   1519             ans[len+1]=pos;
   1520             if(pos!=-1)
   1521             {
   1522                 S^=1<<pos;
   1523                 S^=1<<(pos+len+1);
   1524             }
   1525             len+=2;
   1526         }
   1527         return ans;
   1528     }
   1529 }
   1530 int solvec(int l,int r,int p)
   1531 {
   1532     if(!l)return p;
   1533     if(a[l]==a[r])
   1534     {
   1535         if(a[l])op(l,r);
   1536         return solvec(l-1,r+1,p);
   1537     }
   1538     if(p)op(p,p+r-l);
   1539     if(a[l])return solvec(l-1,r+1,l);
   1540     else return solvec(l-1,r+1,r);
   1541 }
   1542 void solvep(int l,int r,int p,bool flag)
   1543 {
   1544     if(l>=r)return;
   1545     if(!p)
   1546     {
   1547         if(a[l]==a[r])
   1548         {
   1549             if(a[l])op(l,r);
   1550             solvep(l+1,r-1,0,0);
   1551             return;
   1552         }
   1553         if(a[l])solvep(l+1,r-1,l,0);
   1554         else solvep(l+1,r-1,r,0);
   1555         return;
   1556     }
   1557     if(r-l+1==DB)
   1558     {
   1559         int S=0;
   1560         for(int i=l;i<=r;++i)S|=a[i]<<(i-l);
   1561         vector<int>res=DP::ask(S);
   1562         for(int len=r-l;len>=1;len-=2)
   1563         {
   1564             if(res[len]!=-1)op(res[len]+l,res[len]+len+l);
   1565         }
   1566         return;
   1567     }
   1568     int x=l+r-p,y=p;
   1569     if(x>y)swap(x,y);
   1570     int A=l-x,B=r-l+1;
   1571     int len=y-x-2;
   1572     auto f=[&](int a){int b=a+len;len-=2,a=a+x,b=b+x;if(p>l)a=l+r-a,b=l+r-b;op(a,b);};
   1573     if(!flag&&r-l+1>=10&&abs(A-B)==1)
   1574     {
   1575         for(int i=x+1;i<l;++i)del(i,l+r-i);
   1576         int type=a[l]|(a[r]<<1);
   1577         if(p>r)type=a[r]|(a[l]<<1);
   1578         if(A==B-1)
   1579         {
   1580             switch(type)
   1581             {
   1582                 case 0:for(int i=0;i<=B-4;i++)f(i);f(2*B-5);f(B-3);break;
   1583                 case 1:f(0);for(int i=3;i<=B-3;i+=2)f(i),f(i-1);f(B-1);f(1);break;
   1584                 case 2:for(int i=0;i<=B-3;i++)f(i);f(2*B-3);break;
   1585                 case 3:for(int i=1;i<=B-2;i++)f(i);f(0);break;
   1586             }
   1587         }
   1588         else if(A==B)
   1589         {
   1590             switch(type)
   1591             {
   1592                 case 0:for(int i=0;i<=B-2;i++)f(i);f(2*B-1);break;
   1593                 case 1:
   1594                     if(B%3==2){f(1);f(0);for(int i=3;i<=B-5;i+=3)f(i+1),f(i+2),f(i);f(B-1);f(B);f(2);}
   1595                     else if(B%3==0){f(1);f(0);for(int i=3;i<=B-6;i+=3)f(i+1),f(i+2),f(i);f(B-3);f(B);f(B-1);f(2);}
   1596                     else{f(1);f(0);for(int i=3;i<=B-7;i+=3)f(i+1),f(i+2),f(i);f(B-3);f(B-4);f(B);f(B-1);f(2);}
   1597                     break;
   1598                 case 2:f(1);f(0);for(int i=3;i<=B-3;i+=2)f(i),f(i-1);f(B-1);f(2*B-2);break;
   1599                 case 3:f(0);for(int i=3;i<=B-1;i+=2)f(i),f(i-1);f(1);break;
   1600             }
   1601         }
   1602         else if(A==B+1)
   1603         {
   1604             switch(type)
   1605             {
   1606                 case 0:for(int i=1;i<=B;i++)f(i);f(0);break;
   1607                 case 1:for(int i=1;i<B;i++)f(i);f(0);f(B);break;
   1608                 case 2:for(int i=1;i<=B-1;i+=2)f(i),f(i-1);f(2*B);break;
   1609                 case 3:
   1610                     if(B%3==2){f(0);f(1);for(int i=3;i<=B-2;i+=3)f(i+2),f(i),f(i+1);f(2);}
   1611                     else if(B%3==0){f(1);f(0);for(int i=3;i<=B-3;i+=3)f(i+1),f(i+2),f(i);f(B);f(2);}
   1612                     else{f(1);f(0);for(int i=4;i<=B-3;i+=3)f(i),f(i+1),f(i-1);f(B);f(B-1);f(2);}
   1613                     break;
   1614             }
   1615         }
   1616         for(int i=x;i<=l;++i)if(a[i]){solvep(l+1,r-1,i,1);return;}
   1617         for(int i=r;i<=y;++i)if(a[i]){solvep(l+1,r-1,i,1);return;}
   1618         solvep(l+1,r-1,0,1);
   1619         return;
   1620     }
   1621     if(a[l]&&a[r])
   1622     {
   1623         op(l,r);
   1624         solvep(l+1,r-1,p,flag);
   1625         return;
   1626     }
   1627     len=r-l;
   1628     auto down=[&](){
   1629         if(a[l])solvep(l+1,r-1,l,0);
   1630         else if(a[r])solvep(l+1,r-1,r,0);
   1631         else solvep(l+1,r-1,0,0);
   1632     };
   1633     if(p+len>l&&p+len<r)
   1634     {
   1635         op(p,p+len);
   1636         down();
   1637         return;
   1638     }
   1639     if(p-len>l&&p-len<r)
   1640     {
   1641         op(p,p-len);
   1642         down();
   1643         return;
   1644     }
   1645     down();
   1646 }
   1647 int rn;
   1648 void solve()
   1649 {
   1650     cin>>n;
   1651     rn=(n>>1);
   1652     for(int i=1;i<=n;++i)
   1653     {
   1654         char ch;
   1655         cin>>ch;
   1656         a[i]=ch-'0';
   1657     }
   1658     for(int i=1;i<=n;++i)ans[i]=0;
   1659     if(!(n&1))
   1660     {
   1661         op(n-(n>>1),n);
   1662         --n;
   1663     }
   1664     mid=(n+1>>1);
   1665     if(!(mid&1))--mid;
   1666     int p=solvec((mid>>1),(mid>>1)+2,(a[(mid>>1)+1]?(mid>>1)+1:0));
   1667     solvep(mid+1,n,0,0);
   1668     for(int i=1;i<=rn;++i)cout<<ans[i]<<' ';
   1669     cout<<'\n';
   1670 }
   1671 int main()
   1672 {
   1673     DP::dp();
   1674     int T;
   1675     cin>>T;
   1676     while(T--)solve();
   1677     return 0;
   1678 }
   1679 ```