Excellent contest

Good contest

Average contest

Bad contest

Terrible contest

Lemma 1. There exists an optimal solution in which each zero is divided separately.

Proof. Suppose in some optimal solution, a zero is grouped with other elements. Separating it into a singleton group does not decrease the total score. Hence, we can transform any optimal solution into one where all zeros are divided separately without worsening the objective. $$$\blacksquare$$$

Therefore, we can restrict our attention to the subsequence consisting only of $1$s and $2$s.

Lemma 2. There exists an optimal solution in which any group containing both $$$1$$$ and $$$2$$$ is exactly either $$$[1,2]$$$ or $$$[2,1]$$$.

Proof. Consider a group that contains $$$1$$$, $$$2$$$, and possibly other elements. Splitting it into $$$[1,2]$$$ (or $$$[2,1]$$$) and the remaining part does not decrease the total score. Consequently, we can transform any optimal solution into the desired form. $$$\blacksquare$$$

By Lemma 2, we can greedily extract all $$$[1,2]$$$ or $$$[2,1]$$$ pairs from the remaining sequence.

Finally, for the leftover elements, the best strategy is clearly to take triplets $$$[1,1,1]$$$ and $$$[2,2,2]$$$ whenever possible.

We assume $$$n\geq 4$$$ in what follows.

Let us analyze the strategies of both players. Reimu aims to get as close to Remilia as possible, while Remilia aims to get as far away from Reimu as possible. Remilia will use her moves to increase the distance without being caught, and indeed it is optimal for her to use as many moves as possible.

The distance on the circle can be measured with $$$d=min(|x_1-x_2|,n-|x_1-x_2|)$$$. Once $$$d=1$$$, Remilia can increase $$$d$$$ by $$$1$$$ since the circle is large enough ($$$n\geq 4$$$). Similarly, Reimu can decrease $$$d$$$ by $$$1$$$ each turn.

Therefore, we can calculate the outcome directly. The answer is the initial distance plus the extra time gained by Remilia's moves, $$$min(|x_1-x_2|,n-|x_1-x_2|)+k$$$.

Note that when $$$n\leq 3$$$, the answer is always $$$1$$$, because Reimu can always catch Remilia in one step.

The case $$$a=b$$$ is trivial. We consider two cases separately: $$$a \gt b$$$ and $$$a \lt b$$$.

We first discuss $$$a \lt b$$$ in what follows. Consider the longest common prefix of $$$a$$$ and $$$b$$$, scanning from the highest digit to the lowest significant digit. Let $$$x$$$ be the digit of $$$a$$$ be at that position and $$$y$$$ be the digit of $$$b$$$ be at that position. If $$$d_n \gt x$$$, choose $$$y$$$ as the smallest $$$d_i$$$ such that $$$d_i \gt x$$$. Then set the digits beneath in $$$b$$$ to $$$d_1$$$. This guarantees that $$$b$$$ is the smallest number greater than $$$a$$$ and the decimal representation of $$$b$$$ contains only digits from $$$d$$$. Otherwise, if $$$d_n \lt x$$$,we should change an earlier digit to satisfy the inequality. Note that we can make the number of digits in $$$b$$$ more than $$$a$$$.

Similarly, we assume $$$a \gt b$$$. Consider the longest common prefix of $$$a$$$ and $$$b$$$, scanning from the highest digit to the lowest significant digit. Let $$$x$$$ be the digit of $$$a$$$ be at that position and $$$y$$$ be the digit of $$$b$$$ be at that position. If $$$d_1 \lt x$$$, choose $$$y$$$ as the largest $$$d_i$$$ such that $$$d_i \lt x$$$. Then set the digits beneath in $$$b$$$ to $$$d_n$$$. This guarantees that $$$b$$$ is the largest number smaller than $$$a$$$ and the decimal representation of $$$b$$$ contains only digits from $$$d$$$. Otherwise, if $$$d_1 \gt x$$$,we should change an earlier digit to satisfy the inequality. Note that if $$$d=[1,2,3]$$$, then $$$b=0$$$ is invalid, because $$$0$$$ dosn't belongs to $$$d$$$.

Depending on the implementation, the time complexity can be $$$O(10n\log a)$$$, $$$O(10n\log^2 a)$$$, $$$O(n\log a)$$$ or $$$O(n\log^2 a)$$$.

We can apply the principle of inclusion--exclusion to compute the answer. First, enumerate a vertical dividing line at integer coordinate $$$x$$$ from $$$1$$$ to $$$n$$$; the contribution is recalculated only when the set of points on the left side changes ~---otherwise, we skip redundant computations.

For each such $$$x$$$, we then enumerate a horizontal dividing line at integer $$$y$$$ from $$$1$$$ to $$$n$$$, while carefully excluding overlapping cases to avoid double-counting. Let the y-coordinates of the points on the left side be $$${y_1,y_2,\dots,y_k}$$$, sorted in increasing order. For consecutive y-values $$$y_i$$$ and $$$y_{i+1}$$$, all values in the form $$$k+0.5$$$ in the interval $$$(y_i+0.5,\;y_{i+1}-0.5)$$$ give the same left-side point set. Thus, the left side produces a set of y-intervals, and similarly, the right side also forms a set of y-intervals. To count all valid configurations, we need to count the number of interval-pairs (one interval from the left, one from the right) that intersect in at least one point. This can be computed efficiently using a Fenwick tree (Binary Indexed Tree) and a set data structure.

The overall time complexity is $$$O(n\log n)$$$.

An observation is that any valid dividing line must cross at least one of the two groups determined by the smaller y-coordinate.

Suppose the line crosses the group with smaller $$$x$$$ and smaller $$$y$$$. Enumerate the point whose $$$y$$$-coordinate is maximal within this group (and among those with the same maximal $$$y$$$, take the one with the larger $$$x$$$). Using appropriate pre-computation, we can efficiently determine the feasible vertical dividing position $$$x$$$.

The case where the line crosses the group with larger $$$x$$$ but smaller $$$y$$$ is symmetric to the above.

The overall time complexity is $$$O(n)$$$.

First, consider solving the whole array. We can first compute the total number of possible configurations of $$$a$$$ using stars and bars. Let this number be $$$tot$$$. The remaining sum to be freely distributed is $$$sum= m - \sum_{i} a_i[a_i\neq -1]$$$, and the number of undetermined positions is $$$cnt=\sum_{i} [a_i = -1]$$$. It is obvious $$$tot=\binom{sum+cnt-1}{cnt-1}$$$. We adopt the convention $$$\binom{-1}{-1}=1$$$ to simplify boundary cases.

Denote $$$S_1=2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)$$$ and $$$S_2=\sum_{b \text{ is valid}}\sum_{1\leq i \leq n}b_i^2 (n+1-i))$$$. We should compute each part individually.

To do the computation, we need to first introduce some useful math conclusions. We give the $$$T_0,T_1,T_2$$$.

We recall the following standard combinatorial identities: \begin{enumerate} \item If $$$n\geq 0$$$, then $$$\binom{n}{m}=\binom{n}{n-m}$$$

\item For any $$$n,m$$$,then $$$m\binom{n}{m}=n\binom{n-1}{m-1}$$$

\item If $$$n,m\geq 0$$$, then $$$n\binom{n+m}{n}=(m+1)\binom{n+m}{m+1}$$$ \end{enumerate}

The $$$T_0$$$ is classic,while $$$T_1,T_2$$$ need some work.

The computation of $$$T_1$$$ is straightforward.

Similarly, we compute $$$T_2$$$:

We now derive $$$T_3$$$:

We first deal with $$$S_2$$$.$$$S_2=\sum_{1\leq i \leq n}\sum_{b \text{ is valid}}b_i^2 (n+1-i))$$$.If $$$a_i\geq 0$$$, $$$b_i=a_i$$$, so the formula can be written like $$$a_i^2(n+1-i) tot$$$. If $$$a_i=-1$$$,the formula can be written like

Second, we cope with $$$S_1$$$.

$$$S_1=2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)$$$

After selecting $$$i,j$$$, we only need to compute $$$\sum_{b \text{ is valid}}b_ib_j$$$.

There are three cases:

\begin{enumerate} \item $$$a_i\neq -1 \text{ and } a_j\neq -1$$$.

$$$\sum_{b \text{ is valid}}b_ib_j=tot\cdot a_ia_j$$$

\item $$$a_i\neq -1 \text{ and } a_j = -1$$$, $$$a_i\neq -1 \text{ and } a_j = -1$$$.

It remains to consider $$$a_i\neq -1 \text{ and } a_j = -1$$$, because another case is similar.

It can also be computed by the expectation of each position.

\item $$$a_i = -1 \text{ and } a_j = -1$$$.

It is the trickiest part of the solution. We analyze this case carefully.

It is just a constant, which is easy to compute.

\end{enumerate}

Then, it is time to cope with $$$S_1$$$.

$$$S_1=2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)$$$

For type $$$1$$$, it suffices to compute

.

For type $$$2$$$, it suffices to compute

.

For type $$$3$$$, it suffices to compute

.

All required quantities can be maintained using a segment tree, and the interval queries and modifications can be processed easily. Note that $$$n-j+1=(n+1)-j$$$. So process $$$X \cdot(n+1)$$$ and $$$X \cdot j$$$ in two data structures. Implementation details are omitted for brevity; see the accompanying code.

By querying on the tree, we can get the answer. And the information can also be modified efficiently.

After all, we can solve the problem in the total time complexity $$$O(1\ 000\ 000)-O((n+q)\log n)$$$ and total space complexity $$$O(1\ 000\ 000+n)$$$.

Note $$$\binom{-1}{-1}=1$$$ in the code.

For a fixed query interval, denote it by $$$b_1,b_2,\ldots,b_L$$$.

Define

and

Here, $$$A_i$$$ is the prefix sum contributed by fixed positions, and $$$T_i$$$ is the number of free positions in the first $$$i$$$ elements.

Let

The total value that must be assigned to all free positions is

If $$$N \lt 0$$$, there is no valid sequence, so the answer is $$$0$$$.

If $$$k=0$$$, there is only one possible sequence. The answer is $$$\sum_i A_i^2$$$ if $$$N=0$$$, and $$$0$$$ otherwise.

Now assume $$$k \gt 0$$$ and $$$N\ge 0$$$.

Let the values assigned to the $$$k$$$ free positions be

where

The number of such assignments is

For prefix $$$i$$$, there are exactly $$$T_i$$$ free positions inside it. Therefore, the contribution of assigned values to this prefix is

So the real prefix sum at position $$$i$$$ is

Therefore, we need to calculate

Expanding the square gives

Now we calculate these three parts separately.

First, consider the $$$A_i^2$$$ part.

Since $$$A_i$$$ does not depend on the assignment, every valid assignment contributes the same value. Hence this part contributes

Second, consider the $$$2A_iX_{T_i}$$$ part.

By symmetry, among all weak compositions of $$$N$$$ into $$$k$$$ parts, every variable has the same total contribution. Thus

Therefore,

Substituting $$$t=T_i$$$, we get

After summing over all $$$i$$$, this part contributes

Third, consider the $$$X_{T_i}^2$$$ part.

We need the second moment of

For all weak compositions of $$$N$$$ into $$$k$$$ parts, we have

and for $$$p\ne q$$$,

Since

we get

Equivalently,

Substituting $$$t=T_i$$$ and summing over all positions, the final formula is

All divisions are done modulo $$$998244353$$$ using modular inverses.

Now we explain why this can be maintained by a segment tree.

For every interval, the formula only needs the following values:

Therefore, each segment tree node maintains:

Here, $$$len$$$ is the length of the segment, $$$sum$$$ is the total fixed value in the segment, and $$$cnt$$$ is the number of $$$-1$$$ positions in the segment.

The other values are:

All prefix values are defined relative to the left end of the current segment.

When merging two adjacent segments $$$L$$$ and $$$R$$$, every prefix inside $$$L$$$ remains unchanged.

For a prefix inside $$$R$$$, the entire left segment is already before it. Therefore,

and

So the merge formulas are:

Thus, the maintained information is closed under concatenation, so it is suitable for a segment tree.

A point update only changes one leaf, and then all nodes on the path to the root are recomputed.

For a range query, we merge $$$O(\log n)$$$ segment tree nodes in left-to-right order. This gives all values required by the formula above.

After precomputing factorials and inverse factorials for combinations, the total complexity is

Solution

Let sum be the sum of all fixed values in the interval, and let cnt be the number of -1's.

If:

• sum > m; or
• cnt = 0 and sum ≠ m;

then no valid sequence exists, and the answer is 0.

The following discussion focuses only on valid cases.

For a single query, we have a simple brute-force approach with complexity $$$O(nm)$$$.

Let:

• $$$A_i$$$: The sum of fixed values among the first $$$i$$$ positions;
• $$$C_i$$$: The count of -1's among the first $$$i$$$ positions;
• $$$rem = m - sum$$$.

Then:

Here, $$$x_i$$$ represents the total sum distributed to the first $$$C_i$$$ unknown variables (the -1's).

Fixing a prefix $$$i$$$, if the unknowns in this prefix are assigned a sum of $$$j$$$, then the suffix unknowns must be assigned $$$rem-j$$$.

The number of ways is given by the classic Stars and Bars method:

However, this approach still has excessive complexity. We consider further optimization.

This recurrence uses identity transformations: - $$$n\binom{n+k-1}{k-1}= k\binom{n+k-1}{k}$$$, - $$$n(n-1)\binom{n+k-1}{k-1}= k(k+1)\binom{n+k-1}{k+1}$$$, - $$$\sum_{k=0}^{n} \binom{k}{a}\binom{n-k}{m-a}=\binom{n+1}{m+1}$$$.

Thus, we obtain an $$$O(n)$$$ solution for the problem, which corresponds to the solution for E1.

How can we optimize further?

Observing the formula above, it becomes clear that if we can quickly maintain interval information such as:

• $$$sum$$$,
• $$$cnt$$$,
• $$$\sum_{i=1}^nA_i^2$$$,
• $$$\sum_{i=1}^nA_iC_i$$$,
• $$$\sum_{i=1}^nC_i$$$,
• $$$\sum_{i=1}^nC_i^2$$$,

a Segment Tree can handle these operations within $$$O(\log n)$$$ time complexity.
Therefore, the solution for E2 is to use a Segment Tree to optimize the recurrence formula, achieving a total time complexity of $$$O(M+(n+q)\log n)$$$.

First Solution

We binary-search the answer $$$V$$$. The monotonicity is clear: a larger $$$V$$$ is harder to achieve, and as $$$k$$$ increases, the feasible $$$V$$$ decreases.

Root the tree arbitrarily at $$$1$$$. For a node $$$x$$$, define $$$dp(x)$$$ as the maximum length (in edges) of a downward-only path starting at $$$x$$$ such that every vertex on the path satisfies: the weight of the component containing that vertex (after cutting the path) is at least $$$V$$$.

During DFS, at node $$$x$$$, we have the $$$dp$$$-values of its children. We need to check whether we can form a path of length $$$k$$$ that passes through $$$x$$$ (or starts at $$$x$$$). This reduces to finding two distinct children $$$y_1$$$, $$$y_2$$$ such that $$$dp(y_1) + dp(y_2) + 2 \ge k$$$ (or a single child with $$$dp(y) + 1 \ge k$$$ if the path starts downward from $$$x$$$).

Sorting the $$$dp$$$-values of the children allows an $$$O(\text{deg}(x)\log \text{deg}(x))$$$ check per node via two-pointers.

The overall time complexity is: $$$O(n\log V\log n)$$$.

Second Solution

Instead of computing $$$dp$$$ by length, we can pre-compute the total weight of each subtree and sort the children of each vertex accordingly. For a candidate $$$V$$$, we can check feasibility by sorting children according to their subtree weights (or the weight of the ``outside-the-path'' component) and using a two-pointer scan to see if a $$$k$$$-edge path exists that meets the $$$V$$$ threshold everywhere.

This eliminates the $$$\log n$$$ factor from sorting $$$dp$$$-values inside the binary search.

The overall time complexity is: $$$O(n\log n+n \log V)$$$.

Third Solution

It's the same as the juan_123's, just for reference.

Apply centroid decomposition. For a centroid $$$rt$$$, any $$$k$$$-edge path either lies entirely within one of $$$rt$$$'s subtrees (handled recursively) or passes through $$$rt$$$. In the latter case, the path consists of two legs, one in each of two different subtrees of $$$rt$$$.

For each vertex $$$u$$$ in a subtree, compute the minimum component weight along the path from $$$u$$$ to $$$rt$$$ (this is the minimum of the ``remaining component weights'' for vertices on that segment). Now, choosing two vertices $$$u$$$, $$$v$$$ in different subtrees gives a path through $$$rt$$$; the overall value is the minimum of the two minima from $$$u$$$ and $$$v$$$ and the components attached to other children of $$$rt$$$.

A key observation: if the largest component (by total weight) attached to $$$rt$$$ is not included in the path, it cannot be the minimum component. We only need to consider the possibility that the path touches the largest component, or handle the case where the largest component is excluded, which simplifies the check.

Carefully pruning with this observation, and using appropriate data structures to query for pairs of legs whose total length is $$$k$$$, leads to an $$$O(n \log n)$$$ solution.

Pruning cases where $$$k$$$ exceeds the size of the current component yields improved performance.

The overall time complexity is: $$$O(n\log n)$$$.

First, we consider how to characterize the connected components formed after deleting the edges along a path, specifically focusing on the component containing a vertex $$$x$$$ on the path.

Let the root of the tree be $$$r$$$. Define $$$sz_x$$$ as the sum of weights in the subtree of $$$x$$$, $$$fa_x$$$ as the parent of $$$x$$$, and $$$tot$$$ as the sum of all $$$a_i$$$. Let LCA denote the lowest common ancestor of all points on the path. We analyze the position of $$$x$$$ on the path:

1. If $$$x$$$ is an endpoint of the path but not the LCA, the edge connecting $$$x$$$ to its parent $$$fa_x$$$ is deleted, while the edges to its children remain. The size of the resulting component is

. 2. If $$$x$$$ is neither the LCA nor an endpoint, the edges to $$$fa_x$$$ and to one specific child (say $$$y$$$) are deleted. The component size is

. 3. If $$$x$$$ is the LCA, then 1 or 2 edges to its children (say $$$y$$$ and $$$z$$$) are deleted. The component size is

.

We employ Centroid Decomposition. At each step, we fix a centroid $$$r_0$$$ as the root and consider the contribution of all paths passing through $$$r_0$$$. For any such path, the LCA is $$$r_0$$$. Let $$$son_{r_0}$$$ be the set of children of $$$r_0$$$.

For contributions of type 1 and 2, we DFS the subtrees rooted at the children of $$$r_0$$$. We compute $$$val_{u,d}$$$, representing the maximum possible minimum component size if we select a path of length $$$d$$$ within the subtree of $$$u$$$ ($$$u \in son_{r_0}$$$), without yet considering the component containing the root $$$r_0$$$.

Now, consider a pair $$$(x, y, d_0, d_1)$$$ where $$$d_0 + d_1 = k$$$, $$$x, y \in son_{r_0}$$$, and $$$x \neq y$$$. This represents a path with endpoints in the subtrees of $$$x$$$ and $$$y$$$ at depths $$$d_0$$$ and $$$d_1$$$, respectively. The minimum component size for this configuration is:

Next, we handle the term $$$tot - sz_x - sz_y$$$ associated with the root component.

Note that for any $$$u$$$ and $$$d$$$,

. This is because $a_i > 0$, and $$$val$$$ represents splitting a subtree into parts, which cannot exceed the sum of the whole subtree.

Let $$$v$$$ be the child of $$$r_0$$$ with the largest subtree size ($$$sz_v$$$). If $$$x \neq v$$$ and $$$y \neq v$$$, the size of the root's component $$$s = tot - sz_x - sz_y$$$ satisfies

. Since this component fully contains the large subtree of $v$, it will never be the minimum. Thus, we can ignore the root's contribution in this case and use prefix/suffix minimums to calculate the contribution efficiently.

Otherwise, one endpoint lies in the subtree of $$$v$$$. We can enumerate the other endpoint's subtree, making the calculation straightforward.

The total time complexity is $$$O(n \log n)$$$.

A crucial detail is that during the DFS for subtree sizes, if we encounter a node that was previously a centroid root, we must add the size of the subtree blocked by that centroid to the current subtree size.

Root the tree arbitrarily at $$$1$$$.

For a node $$$u$$$, define $$$dp(u)$$$ as the maximum length (in edges) of a downward-only path starting at $$$u$$$ such that every vertex on the path satisfies: the weight of the component containing that vertex (after cutting the path) is at least $$$V$$$.

Define $$$f(u,x)$$$ as the maximum $$$V$$$ satisfies: $$$dep(u)+dp(u)\geq x$$$.

Define $$$b(u)$$$ as $$$\sum\limits_{v\in subtree(u)}a(v)$$$.

According to the solution above, we could easily write a $$$O(n^2)$$$ brute force to calculate $$$f(u,x)$$$ and the answer. Try to optimize it by using long path decomposition.

First we should calculate $$$f(u,x)$$$. The transition is: $$$f(u,x)=\max\limits_{fa_v=u}(\min(b(u)-b(v),f(v,x)))$$$ for $$$x \gt dep(u)$$$ and $$$f(u,x)=b(u)$$$ for $$$x=dep(u)$$$.

The most difficult part is the $$$\min(b(u)-b(v),f(v,x))$$$. Note that, $$$f(v,x)\geq f(v,x+1)$$$, so every time we set a prefix of $$$f(v)$$$ to $$$b(u)-b(v)$$$, we use something similar to ODT to solve this. Instead of maintain $$$(x,val)$$$ to represent $$$f(u,x)=val$$$, we maintain $$$(l,r,val)$$$ to represent $$$f(u,x)=val$$$ for all $$$x\in [l,r]$$$. The other part is easy to solve.

Then we should calculate the answer. We calculate the answer at the lca of the path. Assume that the lca is node $$$u$$$.

If $$$u$$$ is one of the endpoint, then the answer is $$$\max\limits_{fa_v=u}(\min(f(v,dep(u)+k),b(1)-b(v)))$$$. It seems that we should binerary search for the position where $$$f(u,dep(u)+k)$$$ store. But note that $$$f(v,x)$$$ is useless while $$$x \gt dep(u)+k$$$, so we erase them. And the $$$f(u,dep(u)+k)$$$ is at the end of $$$f(u)$$$.

If $$$u$$$ is not a endpoint, then the answer is $$$\max\limits_{fa_v=fa_w=u,x+y\geq 2dep(u)+k}(\min(f(v,x),f(w,y),b(1)-b(v)-b(w)))$$$. It is easy to solve if there is no $$$b(1)-b(v)-b(w)$$$.

Define $$$son(u)$$$ as $$$v$$$ with the maximum $$$b(v)$$$ satisfies: v is the son of $$$u$$$. Note that $$$\min(f(v,x),f(w,y))\leq b(1)-b(v)-b(w)$$$ while neither $$$v$$$ or $$$w$$$ is equal to $$$son(u)$$$. So we use brute force while $$$v=son(u)$$$ and $$$w=son(u)$$$.

The overall time complexity is: $$$O(n)$$$.

code

374853549