[2256A-Three Numbers on the Blackboard](https://codeforces.me/contest/2256/problem/A) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Sort the numbers as $a\le b\le c$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
After at least one operation, consider the median.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
Doing nothing gives $c-a$; replacing $c$ with $a+b$ gives $b$.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Suppose the current numbers are $x\le y\le z$. An operation keeps two numbers and replaces the third with their sum. Since all values are nonnegative, the new sum is no smaller than either retained number. Thus the new median is the larger retained number, which is at least the old median $y$. The median never decreases.↵
↵
After an operation that retains $u\le v$, the numbers are $u,v,u+v$. Their range is exactly $v$, also their median. Hence every nonempty sequence of operations ends with a range of at least the initial median $b$.↵
↵
With no operation the range is $c-a$. Replacing $c$ with $a+b$ produces $a,b,a+b$, whose range is $b$. Therefore the answer is $\min(c-a,b)$.↵
↵
The time and space complexities are both $O(1)$.↵
↵
</spoiler>↵
↵
[2256B-Domino Tiles](https://codeforces.me/contest/2256/problem/B) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Cancel the common term in the inequality between two adjacent dominoes.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
The condition is equivalent to $s_i\ne s_{i+2}$ for every $i$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
Once the first two characters are fixed, the rest are determined.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Adjacent dominoes have different weights exactly when $s_i+s_{i+1}\ne s_{i+1}+s_{i+2}$.↵
↵
Canceling $s_{i+1}$ gives $s_i\ne s_{i+2}$. Since the alphabet is binary, this is equivalent to $s_{i+2}=1-s_i$.↵
↵
Therefore $s_1,s_2$ determine the whole string. Enumerate their four assignments and check whether the implied string agrees with every known character. The answer is at most $4$, so the modulus does not affect it.↵
↵
The time complexity is $O(n)$ and the space complexity is $O(1)$.↵
↵
</spoiler>↵
↵
[2255A-Hot Potatoes at the Fairy Warehouse](https://codeforces.me/contest/2255/problem/A) / [2256C](https://codeforces.me/contest/2256/problem/C) Idea: [user:Error_yuan,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Split the 1s on the cycle into maximal runs. Unless a run covers the whole cycle, initially only its last potato can move.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Passing too early gives the next opportunity to players of the other team.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
The last player of each run waits until the final round. Every initial 10 becomes 01, all other potatoes stay still, and the exact value of $k$ is irrelevant.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
The total score is always the number of potatoes, so the game is zero-sum. Consider a maximal run of 1s followed by an empty position. Every potato except the last one is blocked.↵
↵
If the last potato is passed early, it reaches the other team and leaves an empty position behind, enabling the preceding potato. Both newly enabled players belong to the other team, so with another round the opponent may cancel the point just gained. Passing in the final round leaves no response and is optimal.↵
↵
Thus only the last potato of each run moves one step in the final round. If the whole cycle is filled, nothing moves. For an initial position $i$:↵
↵
- if $s_i=1$ and $s_{i+1}=0$, the team owning $i$ scores;↵
- if $s_i=s_{i+1}=1$, the other team scores.↵
↵
Scan the cycle once. The implementation is zero-indexed: even positions belong to red and odd positions to blue. Their scores are printed in that order.↵
↵
The time complexity is $O(n)$ and the space complexity is $O(1)$.↵
↵
</spoiler>↵
↵
[2255B-A Ribbon for Tomorrow](https://codeforces.me/contest/2255/problem/B) / [2256D](https://codeforces.me/contest/2256/problem/D) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Check whether a valid reversal can change either run count or the first character.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
In $x^ay^bx^c$, choosing one endpoint in each $x$-run lets us redistribute the total length of those two runs.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
Operations redistribute run lengths but do not change the order of run colors.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Split the string into maximal runs. The two endpoints of an operation contain the same character. Internal adjacencies are only reversed, and the endpoint character on either boundary stays unchanged. Hence the numbers of 0-runs and 1-runs are invariant, as are the character counts.↵
↵
If the reversal contains the first position, the new first character is the old right endpoint, equal to the old first character. Otherwise it is untouched. Thus the first character is invariant. Since run colors alternate, the run counts and first character determine their entire order.↵
↵
Conversely, consider $x^ay^bx^c$. A reversal with one endpoint in each $x$-run can split the total $a+c$ into any two positive lengths while leaving the middle run unchanged. Repeating this between adjacent runs of the same color realizes any positive composition of all 0s, and independently any positive composition of all 1s. These invariants are therefore sufficient.↵
↵
If character $x$ occurs $cnt_x$ times in $seg_x$ nonempty runs, its run lengths can be chosen in $\binom{cnt_x-1}{seg_x-1}$ ways. The two colors are independent, so the answer is $\binom{cnt_0-1}{seg_0-1}\binom{cnt_1-1}{seg_1-1}$.↵
↵
An absent character contributes a factor of $1$.↵
↵
We can precompute inverses without binary exponentiation. Let the prime modulus be $P$. Since every required $i<P$, its inverse exists. From $P=\left\lfloor\frac Pi\right\rfloor i+(P\bmod i)$ we obtain $i^{-1}=-\left\lfloor\frac Pi\right\rfloor(P\bmod i)^{-1}\pmod P$.↵
↵
Because $P\bmod i<i$, enumerating $i$ in increasing order computes each inverse from an earlier one. Factorials and inverse factorials follow in the same loop.↵
↵
Each test case takes $O(n)$ time. Preprocessing uses $O(N)$ time and space, where $N=10^6$.↵
↵
</spoiler>↵
↵
[2255C-Even If the World Turns](https://codeforces.me/contest/2255/problem/C) / [2256E](https://codeforces.me/contest/2256/problem/E) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Let $w$ be the number of black cells and $S_r,S_c$ their coordinate sums modulo $n$. Observe how they change after a shift.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Since $\gcd(w,n)=1$, $(w^{-1}S_r,w^{-1}S_c)$ behaves like the center of mass of the picture.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
Swapping a black cell $p$ with a white cell $p+\delta$ increases the coordinate sum by $\delta$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
↵
In the first run, move the center to the target. In the second run, recompute it from the transformed picture.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Identify coordinates $1,2,\ldots,n$ with $0,1,\ldots,n-1$ in $\mathbb Z_n$. Let $S=(S_r,S_c)$ be the sum of black-cell coordinates. A shift by $d$ changes it to $S+wd$. Define $C=w^{-1}S$. Then $C$ changes to $C+d$, exactly as an ordinary cell does.↵
↵
Every rotation or reflection is an affine map $p\mapsto Mp+t$. It changes the sum to $MS+wt$ and therefore changes the center to $MC+t$, again exactly like a cell.↵
↵
After color inversion, $w'=n^2-w\equiv-w\pmod n$. The coordinate sum of the whole board is $0$ modulo $n$, so the new black-cell sum is $S'=-S$. Hence the new center is $(-w)^{-1}(-S)=C$. Color inversion does not affect it.↵
↵
In the first run, we want the sum after swapping to be $wx$. Let $\delta=wx-S$. If $\delta=0$, swap one cell with itself. Otherwise find a black cell $p$ for which $p+\delta$ is white and swap them.↵
↵
Such a cell must exist. Otherwise the black-cell set would be invariant under translation by nonzero $\delta$. Every orbit of this translation has length $L>1$ with $L\mid n$. The black cells would be a union of complete orbits, so $L\mid w$, contradicting $\gcd(w,n)=1$.↵
↵
The swap makes the center equal to the target. All later transformations move them together. In the second run, recompute $w,S_r,S_c$ and output $w^{-1}S$. Since $n\le800$, enumerate $1\le t<n$ until $wt\equiv1\pmod n$; no extended Euclidean algorithm is needed.↵
↵
Each run takes $O(n^2)$ time and $O(n^2)$ space.↵
↵
</spoiler>↵
↵
[2255D-How Long Until Nothing Remains?](https://codeforces.me/contest/2255/problem/D) / [2256F](https://codeforces.me/contest/2256/problem/F) Idea: [user:Error_yuan,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Fix the chosen index in every second and work backward from the final zero array. A current upper bound $x$ becomes either $2x+1$ or $2x$ after one backward step.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
If index $i$ is selected in the seconds in $S$, it can end at zero after $T$ seconds exactly when $a_i\le\sum_{s\in S}2^{s-1}$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
For fixed $T$, distribute $1,2,4,\ldots,2^{T-1}$ among the demands. Process them in decreasing order and always choose the largest remaining demand.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Fix all choices during the $T$ seconds and consider position $i$. Working backward, if values at most $x$ can already reach zero, then a preceding selected step allows $y$ exactly when $\lfloor y/2\rfloor\le x$, or $y\le2x+1$. A nonselected step gives $\lceil y/2\rceil\le x$, or $y\le2x$. Repeating this proves the condition in Hint 2.↵
↵
Thus feasibility in $T$ seconds is equivalent to assigning every capacity $1,2,\ldots,2^{T-1}$ to one demand so that demand $a_i$ receives total capacity at least $a_i$.↵
↵
Process capacities from largest to smallest. Let the current capacity be $p$ and the largest remaining demand be $x$. If $x>p$, all smaller capacities sum to only $p-1$, so every feasible assignment must give $p$ to $x$. If $x\le p$, let $p$ finish $x$. In any feasible assignment giving $p$ to some $y\le x$ and a set of smaller capacities to $x$, swapping those two assignments remains feasible. Hence the greedy rule is correct.↵
↵
Every positive number must be selected at least once, since repeated ceiling division alone never reaches zero. Thus $T\ge n$. Also $a_i<2^{30}$, so $T=n+30$ is always sufficient. Binary-search $T$ in this interval.↵
↵
Every capacity at least $2^{30}$ can finish one demand alone. Remove the largest $T-30$ demands with these capacities. At most $30$ demands remain; put them in a max-heap and simulate only $2^{29},\ldots,1$.↵
↵
Sorting takes $O(n\log n)$. Each check takes $O(30\log30)$, there are $O(\log30)$ checks, and the space complexity is $O(n)$.↵
↵
</spoiler>↵
↵
[2255E1-What Will Remain at the End? (Easy Version)](https://codeforces.me/contest/2255/problem/E1) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
For each position, its values over all versions form a sequence. Maintain its sum, maximum prefix, maximum suffix, and maximum subarray when appending a segment.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
A value is always in $\{-1,0,1\}$. For each possible initial value, a sequence of operations can store its final value and the summary of the generated history.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
This representation is closed under concatenating operation sequences, so it can serve as a lazy segment-tree tag.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
↵
Range updates only compose tags. A position's history is materialized when that position is queried by pushing its root-to-leaf tags.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
For a nonempty sequence segment, store $(S,P,Q,M)$: its sum, maximum prefix sum, maximum suffix sum, and maximum nonempty subarray sum. Two adjacent summaries merge in $O(1)$; a crossing maximum subarray is the left maximum suffix followed by the right maximum prefix.↵
↵
Fix one array position. Its value lies in $V=\{-1,0,1\}$. For an operation segment $T$, let $f_T(s)$ be the final value from initial state $s$, and let $H_T(s)$ summarize the values recorded while executing $T$. There are only three states, so this representation has constant size.↵
↵
If $A$ is followed by $B$, then $f_{AB}(s)=f_B(f_A(s))$ and $H_{AB}(s)=H_A(s)\mathbin{\Vert}H_B(f_A(s))$, where $\Vert$ concatenates two histories and merges their summaries. Tags therefore compose in $O(1)$.↵
↵
Each segment-tree node stores the unpushed operation segment applying to its whole interval. A range update composes tags in $O(\log n)$ nodes. After each operation, a record-current-value event is applied to the whole tree to create the new version.↵
↵
A query at $p$ pushes the tags on its root-to-leaf path and materializes all history since the previous query. If the old history has maximum suffix $Q_0$ and maximum subarray $M_0$, while the new segment has $(S,P,Q,M)$, then $M'=\max(M_0,M,Q_0+P)$ and $Q'=\max(Q,Q_0+S)$.↵
↵
Only these two old values need to persist at each position.↵
↵
Record version $0$ initially. A type-4 operation at time $i$ queries versions $0$ through $i-1$, so answer it before recording version $i$, which equals version $i-1$. Other operations update first and record afterward. Decode online input modulo $2^{64}$ exactly as specified.↵
↵
The total time complexity is $O((n+q)\log n)$ and the space complexity is $O(n)$.↵
↵
</spoiler>↵
↵
[2255E2-What Will Remain at the End? (Hard Version)](https://codeforces.me/contest/2255/problem/E2) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
The segment tree and historical maximum-subarray framework are unchanged from G1. Only the constant-size operation tag changes.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Before the first assignment, after fixing the sign of the initial $x$, every value is one of $-|x|,0,|x|$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
The first assignment removes all dependence on $x$. Split a tag into a coefficient prefix depending on $|x|$ and a fixed numeric suffix.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
↵
To compose $A$ followed by $B$, distinguish whether an assignment has occurred in either segment.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
**Solution 1**↵
↵
Without assignments, negation changes only the sign and $\max(x,0)$ only replaces a negative value with zero. For each of the three initial signs, store the summary of the coefficient sequence and the final coefficient in $\{-1,0,1\}$. Substituting the real input multiplies the sequence by $|x|$.↵
↵
The first assignment is a dividing point. Before it, values still depend on $x$; from it onward, they are fixed. Represent an operation segment by:↵
↵
- a coefficient prefix depending on $|x|$, stored for all three initial signs;↵
- a fixed numeric suffix and the final actual value.↵
↵
This representation has constant size. It is also closed under concatenation.↵
↵
If $A$ contains an assignment, its output is constant. Feeding that constant into $B$ fixes all history produced by $B$, so concatenate the fixed histories.↵
↵
If neither segment contains an assignment, compose their three coefficient states exactly as in G1.↵
↵
If only $B$ contains an assignment, append the part of $B$ before its first assignment to each coefficient prefix of $A$. The fixed suffix of $B$ becomes the fixed suffix of the result. Every case takes $O(1)$.↵
↵
Assignment, negation, $\max(x,0)$, and recording a version all have direct tags of this form. The remaining segment-tree logic and version ordering are identical to G1.↵
↵
The total time complexity is $O((n+q)\log n)$ and the space complexity is $O(n)$.↵
↵
**Solution 2**↵
↵
There is also an amortized solution that performs operation $3$ directly on the segment tree. Store the current minimum $mn$ and maximum $mx$ in every node. Range assignment and range negation use ordinary lazy tags. For operation $3$:↵
↵
- if $mn\ge0$, do nothing;↵
- if $mx\le0$, assign zero to the whole node;↵
- otherwise the node contains both positive and negative values, so recurse into its children.↵
↵
Thus operation $3$ never has to appear in a historical tag. It is materialized as several range assignments to zero.↵
↵
Call a segment-tree node bad if $mn<0<mx$.↵
↵
Let the potential $\Phi$ be the number of bad nodes. When a fully covered node is negated, $(mn,mx)$ becomes $(-mx,-mn)$, so the bad status of that node and every node below it is preserved. Assignment can only remove bad nodes. A range assignment or negation recomputes nodes only on its two boundary paths, so it creates at most $O(\log n)$ new bad nodes.↵
↵
Now consider operation $3$. Apart from $O(\log n)$ nodes on the two boundary paths, every internal node into which the recursion continues was bad before the operation. After the operation, its interval contains no negative value, so that bad node has disappeared. A recursion tree has at most one more terminal node than internal nodes. Hence one operation costs $O(\log n+D)$, where $D$ is the number of bad nodes destroyed by this operation. Operation $3$ creates no bad nodes. The initial potential is $O(n)$, while all other operations increase it by only $O(q\log n)$ in total. Therefore all operation-3 recursions take $O(n+q\log n)$ time altogether.↵
↵
The historical part still uses the four-value sequence summary from G1. After every operation, append one record-current-value event at the root. Since every clamp has already been materialized as assignment to zero, pending historical actions contain only assignment, negation, and recording.↵
↵
Before the first assignment, an initial value $x$ can only become $x$ or $-x$. It is therefore enough to keep two initial states, negative and nonnegative, storing the generated coefficient-sequence summary and the final sign. After the first assignment, all later values are independent of the initial input, so keep a fixed numeric suffix and the final value. Two such tags still compose in $O(1)$ in chronological order.↵
↵
For a query at $p$, push all tags on the root-to-leaf path and append the new history summary to the already materialized history of that position. Version $0$ and type-4 recording are handled in the same order as in Solution 1.↵
↵
The total time complexity is $O(n+q\log n)$ and the space complexity is $O(n)$.↵
↵
</spoiler>↵
↵
[2255F-Who Will Witness the End?](https://codeforces.me/contest/2255/problem/F) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
View each factor $a_u+a_v$ as choosing one endpoint of edge $(u,v)$. Every exponent is $0$, $1$, or $2$. The numbers of vertices with exponents $0$ and $2$ are equal, and these two types alternate after all other vertices are removed.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
The coefficient of a monomial type depends only on the number of variables appearing twice. Express the answer using $e_re_{n-r}$, where $e_r$ is the $r$-th elementary symmetric polynomial.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
Coefficient comparison gives a linear system that can be eliminated from high indices to low indices. Direct elimination is $O(n^2)$; use the ratio of adjacent $c_k$ and Pascal's identity to derive a short recurrence.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
↵
Adjacent equations give a second-order recurrence in $h_r,h_{r+1},h_{r+2}$. All $e_r$ are coefficients of $\prod_{i=1}^n(1+a_ix)$ and can be computed by divide-and-conquer NTT.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Expand the weight of one cyclic ordering. Choosing one term from $a_u+a_v$ is equivalent to orienting edge $(u,v)$ toward the chosen endpoint.↵
↵
Every vertex has degree two, so its exponent is $0$, $1$, or $2$. The exponent sum is $n$, hence the numbers of vertices with exponents $0$ and $2$ are equal; call both numbers $k$.↵
↵
Fix these two sets. An exponent-0 vertex has both edges directed outward, an exponent-2 vertex has both directed inward, and every ordinary vertex has one edge in and one out. After ordinary vertices are removed, the two special types must alternate. Conversely, alternation uniquely determines the orientations of all paths between them.↵
↵
For $k\ge1$, the $2k$ special vertices have $(2k-1)!$ relative cyclic orders. Fix one exponent-0 vertex as the start. The exponent-2 vertices can be permuted arbitrarily, as can the remaining exponent-0 vertices, giving $k!(k-1)!$ alternating orders. Inserting the other $n-2k$ vertices does not change this ratio. Therefore the coefficient of this monomial type over all cyclic orders is↵
↵
$$↵
c_k=\frac{(n-1)!k!(k-1)!}{(2k-1)!}.↵
$$↵
↵
For $k=0$, every vertex has one edge in and one out. The whole cycle must be consistently clockwise or counterclockwise, so↵
↵
$$↵
c_0=2(n-1)!.↵
$$↵
↵
Now consider a symmetric-polynomial representation. Let $e_r$ be defined by↵
↵
$$↵
\prod_{i=1}^n(1+a_ix)=\sum_{r=0}^n e_rx^r.↵
$$↵
↵
In $e_re_{n-r}$, fix a monomial with $k$ variables appearing twice and $k$ absent. Repeated variables must be chosen from both factors and absent variables from neither. Choose $r-k$ of the remaining $n-2k$ variables for the first factor, so its coefficient is↵
↵
$$↵
\binom{n-2k}{r-k}.↵
$$↵
↵
Let $m=\lfloor n/2\rfloor$ and write the answer as↵
↵
$$↵
\sum_{r=0}^m h_re_re_{n-r}.↵
$$↵
↵
Comparing each monomial type gives↵
↵
$$↵
c_k=\sum_{r=k}^m\binom{n-2k}{r-k}h_r↵
\qquad(0\le k\le m).↵
$$↵
↵
Equation $k$ contains only $h_k,h_{k+1},\ldots,h_m$, with coefficient $1$ on $h_k$. Thus the variables can be solved from large indices to small indices, but doing so directly takes $O(n^2)$.↵
↵
For $k\ge1$, divide two adjacent coefficients:↵
↵
$$↵
\begin{aligned}↵
\frac{c_{k+1}}{c_k}↵
&=\frac{(k+1)!k!}{(2k+1)!}↵
\frac{(2k-1)!}{k!(k-1)!}\\↵
&=\frac{k(k+1)}{(2k)(2k+1)}\\↵
&=\frac{k+1}{2(2k+1)}.↵
\end{aligned}↵
$$↵
↵
The $k=0$ case follows directly from $c_0,c_1$. Hence↵
↵
$$↵
(4k+2)c_{k+1}-(k+1)c_k=0.↵
$$↵
↵
Define↵
↵
$$↵
L_k=(k+1)c_k-(4k+2)c_{k+1}=0↵
\qquad(0\le k<m).↵
$$↵
↵
Fix $k$, set $N=n-2k$ and $j=r-k$, and let $A_t=\binom{N-2}{t}$, with out-of-range binomial coefficients equal to zero.↵
↵
Using Pascal's identity twice,↵
↵
$$↵
\binom Nj=A_j+2A_{j-1}+A_{j-2},↵
$$↵
↵
Now use↵
↵
$$↵
jA_j=(N-j-1)A_{j-1},\qquad↵
(N-j)A_{j-2}=(j-1)A_{j-1},↵
$$↵
↵
together with $r=k+j$ and $n=N+2k$. The entire coefficient calculation can be displayed as↵
↵
$$↵
\begin{aligned}↵
[h_r]L_k↵
&=(k+1)\binom Nj-(4k+2)\binom{N-2}{j-1}\\↵
&=(k+1)(A_j+2A_{j-1}+A_{j-2})-(4k+2)A_{j-1}\\↵
&=(k+1)A_j-2kA_{j-1}+(k+1)A_{j-2}\\↵
&=(r+1)A_j-(n-2)A_{j-1}+(n-r+1)A_{j-2}.↵
\end{aligned}↵
$$↵
↵
Substituting into $L_k$ and shifting the latter two indices gives↵
↵
$$↵
0=L_k=\sum_{r=k}^m\binom{n-2k-2}{r-k}↵
\left((r+1)h_r-(n-2)h_{r+1}+(n-r-1)h_{r+2}\right),↵
$$↵
↵
where out-of-range $h$ values are zero. Define↵
↵
$$↵
E_r=(r+1)h_r-(n-2)h_{r+1}+(n-r-1)h_{r+2}.↵
$$↵
↵
Then↵
↵
$$↵
\sum_{r=k}^m\binom{n-2k-2}{r-k}E_r=0.↵
$$↵
↵
Equation $k$ contains only $E_k,E_{k+1},\ldots,E_m$, with coefficient $1$ on $E_k$. Apart from the top boundary, backward elimination gives $E_r=0$, or↵
↵
$$↵
(r+1)h_r=(n-2)h_{r+1}-(n-r-1)h_{r+2}.↵
$$↵
↵
The highest two terms come directly from the original system:↵
↵
$$↵
h_m=c_m,\qquad↵
h_{m-1}=c_{m-1}-(n-2m+2)h_m.↵
$$↵
↵
If $n=2m+1$ is odd, these values satisfy $E_{m-1}=-E_m$. Their binomial coefficients in every sum are equal, so they cancel. The remaining equations give $E_{m-2},E_{m-3},\ldots,E_0=0$. Apply the second-order recurrence starting from $m-2$.↵
↵
If $n=2m$ is even, the first two values give $E_{m-1}=0$, but $E_m$ has no matching boundary term. Compute one more value from the original system:↵
↵
$$↵
h_{m-2}=c_{m-2}-4h_{m-1}-6h_m.↵
$$↵
↵
It satisfies $E_{m-2}=-E_m$. Again their coefficients are equal and they cancel, giving $E_{m-3},E_{m-4},\ldots,E_0=0$. Apply the recurrence starting from $m-3$.↵
↵
Finally compute all $e_r$ by multiplying the $n$ linear polynomials $1+a_ix$ with divide and conquer, using NTT for every convolution. Substitute the resulting coefficients into $\sum_{r=0}^m h_re_re_{n-r}$.↵
↵
The time complexity is $O(n\log^2 n)$ and the space complexity is $O(n\log n)$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
↵
Sort the numbers as $a\le b\le c$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
After at least one operation, consider the median.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
Doing nothing gives $c-a$; replacing $c$ with $a+b$ gives $b$.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Suppose the current numbers are $x\le y\le z$. An operation keeps two numbers and replaces the third with their sum. Since all values are nonnegative, the new sum is no smaller than either retained number. Thus the new median is the larger retained number, which is at least the old median $y$. The median never decreases.↵
↵
After an operation that retains $u\le v$, the numbers are $u,v,u+v$. Their range is exactly $v$, also their median. Hence every nonempty sequence of operations ends with a range of at least the initial median $b$.↵
↵
With no operation the range is $c-a$. Replacing $c$ with $a+b$ produces $a,b,a+b$, whose range is $b$. Therefore the answer is $\min(c-a,b)$.↵
↵
The time and space complexities are both $O(1)$.↵
↵
</spoiler>↵
↵
[2256B-Domino Tiles](https://codeforces.me/contest/2256/problem/B) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Cancel the common term in the inequality between two adjacent dominoes.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
The condition is equivalent to $s_i\ne s_{i+2}$ for every $i$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
Once the first two characters are fixed, the rest are determined.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Adjacent dominoes have different weights exactly when $s_i+s_{i+1}\ne s_{i+1}+s_{i+2}$.↵
↵
Canceling $s_{i+1}$ gives $s_i\ne s_{i+2}$. Since the alphabet is binary, this is equivalent to $s_{i+2}=1-s_i$.↵
↵
Therefore $s_1,s_2$ determine the whole string. Enumerate their four assignments and check whether the implied string agrees with every known character. The answer is at most $4$, so the modulus does not affect it.↵
↵
The time complexity is $O(n)$ and the space complexity is $O(1)$.↵
↵
</spoiler>↵
↵
[2255A-Hot Potatoes at the Fairy Warehouse](https://codeforces.me/contest/2255/problem/A) / [2256C](https://codeforces.me/contest/2256/problem/C) Idea: [user:Error_yuan,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Split the 1s on the cycle into maximal runs. Unless a run covers the whole cycle, initially only its last potato can move.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Passing too early gives the next opportunity to players of the other team.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
The last player of each run waits until the final round. Every initial 10 becomes 01, all other potatoes stay still, and the exact value of $k$ is irrelevant.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
The total score is always the number of potatoes, so the game is zero-sum. Consider a maximal run of 1s followed by an empty position. Every potato except the last one is blocked.↵
↵
If the last potato is passed early, it reaches the other team and leaves an empty position behind, enabling the preceding potato. Both newly enabled players belong to the other team, so with another round the opponent may cancel the point just gained. Passing in the final round leaves no response and is optimal.↵
↵
Thus only the last potato of each run moves one step in the final round. If the whole cycle is filled, nothing moves. For an initial position $i$:↵
↵
- if $s_i=1$ and $s_{i+1}=0$, the team owning $i$ scores;↵
- if $s_i=s_{i+1}=1$, the other team scores.↵
↵
Scan the cycle once. The implementation is zero-indexed: even positions belong to red and odd positions to blue. Their scores are printed in that order.↵
↵
The time complexity is $O(n)$ and the space complexity is $O(1)$.↵
↵
</spoiler>↵
↵
[2255B-A Ribbon for Tomorrow](https://codeforces.me/contest/2255/problem/B) / [2256D](https://codeforces.me/contest/2256/problem/D) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Check whether a valid reversal can change either run count or the first character.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
In $x^ay^bx^c$, choosing one endpoint in each $x$-run lets us redistribute the total length of those two runs.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
Operations redistribute run lengths but do not change the order of run colors.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Split the string into maximal runs. The two endpoints of an operation contain the same character. Internal adjacencies are only reversed, and the endpoint character on either boundary stays unchanged. Hence the numbers of 0-runs and 1-runs are invariant, as are the character counts.↵
↵
If the reversal contains the first position, the new first character is the old right endpoint, equal to the old first character. Otherwise it is untouched. Thus the first character is invariant. Since run colors alternate, the run counts and first character determine their entire order.↵
↵
Conversely, consider $x^ay^bx^c$. A reversal with one endpoint in each $x$-run can split the total $a+c$ into any two positive lengths while leaving the middle run unchanged. Repeating this between adjacent runs of the same color realizes any positive composition of all 0s, and independently any positive composition of all 1s. These invariants are therefore sufficient.↵
↵
If character $x$ occurs $cnt_x$ times in $seg_x$ nonempty runs, its run lengths can be chosen in $\binom{cnt_x-1}{seg_x-1}$ ways. The two colors are independent, so the answer is $\binom{cnt_0-1}{seg_0-1}\binom{cnt_1-1}{seg_1-1}$.↵
↵
An absent character contributes a factor of $1$.↵
↵
We can precompute inverses without binary exponentiation. Let the prime modulus be $P$. Since every required $i<P$, its inverse exists. From $P=\left\lfloor\frac Pi\right\rfloor i+(P\bmod i)$ we obtain $i^{-1}=-\left\lfloor\frac Pi\right\rfloor(P\bmod i)^{-1}\pmod P$.↵
↵
Because $P\bmod i<i$, enumerating $i$ in increasing order computes each inverse from an earlier one. Factorials and inverse factorials follow in the same loop.↵
↵
Each test case takes $O(n)$ time. Preprocessing uses $O(N)$ time and space, where $N=10^6$.↵
↵
</spoiler>↵
↵
[2255C-Even If the World Turns](https://codeforces.me/contest/2255/problem/C) / [2256E](https://codeforces.me/contest/2256/problem/E) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Let $w$ be the number of black cells and $S_r,S_c$ their coordinate sums modulo $n$. Observe how they change after a shift.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Since $\gcd(w,n)=1$, $(w^{-1}S_r,w^{-1}S_c)$ behaves like the center of mass of the picture.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
Swapping a black cell $p$ with a white cell $p+\delta$ increases the coordinate sum by $\delta$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
↵
In the first run, move the center to the target. In the second run, recompute it from the transformed picture.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Identify coordinates $1,2,\ldots,n$ with $0,1,\ldots,n-1$ in $\mathbb Z_n$. Let $S=(S_r,S_c)$ be the sum of black-cell coordinates. A shift by $d$ changes it to $S+wd$. Define $C=w^{-1}S$. Then $C$ changes to $C+d$, exactly as an ordinary cell does.↵
↵
Every rotation or reflection is an affine map $p\mapsto Mp+t$. It changes the sum to $MS+wt$ and therefore changes the center to $MC+t$, again exactly like a cell.↵
↵
After color inversion, $w'=n^2-w\equiv-w\pmod n$. The coordinate sum of the whole board is $0$ modulo $n$, so the new black-cell sum is $S'=-S$. Hence the new center is $(-w)^{-1}(-S)=C$. Color inversion does not affect it.↵
↵
In the first run, we want the sum after swapping to be $wx$. Let $\delta=wx-S$. If $\delta=0$, swap one cell with itself. Otherwise find a black cell $p$ for which $p+\delta$ is white and swap them.↵
↵
Such a cell must exist. Otherwise the black-cell set would be invariant under translation by nonzero $\delta$. Every orbit of this translation has length $L>1$ with $L\mid n$. The black cells would be a union of complete orbits, so $L\mid w$, contradicting $\gcd(w,n)=1$.↵
↵
The swap makes the center equal to the target. All later transformations move them together. In the second run, recompute $w,S_r,S_c$ and output $w^{-1}S$. Since $n\le800$, enumerate $1\le t<n$ until $wt\equiv1\pmod n$; no extended Euclidean algorithm is needed.↵
↵
Each run takes $O(n^2)$ time and $O(n^2)$ space.↵
↵
</spoiler>↵
↵
[2255D-How Long Until Nothing Remains?](https://codeforces.me/contest/2255/problem/D) / [2256F](https://codeforces.me/contest/2256/problem/F) Idea: [user:Error_yuan,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
Fix the chosen index in every second and work backward from the final zero array. A current upper bound $x$ becomes either $2x+1$ or $2x$ after one backward step.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
If index $i$ is selected in the seconds in $S$, it can end at zero after $T$ seconds exactly when $a_i\le\sum_{s\in S}2^{s-1}$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
For fixed $T$, distribute $1,2,4,\ldots,2^{T-1}$ among the demands. Process them in decreasing order and always choose the largest remaining demand.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Fix all choices during the $T$ seconds and consider position $i$. Working backward, if values at most $x$ can already reach zero, then a preceding selected step allows $y$ exactly when $\lfloor y/2\rfloor\le x$, or $y\le2x+1$. A nonselected step gives $\lceil y/2\rceil\le x$, or $y\le2x$. Repeating this proves the condition in Hint 2.↵
↵
Thus feasibility in $T$ seconds is equivalent to assigning every capacity $1,2,\ldots,2^{T-1}$ to one demand so that demand $a_i$ receives total capacity at least $a_i$.↵
↵
Process capacities from largest to smallest. Let the current capacity be $p$ and the largest remaining demand be $x$. If $x>p$, all smaller capacities sum to only $p-1$, so every feasible assignment must give $p$ to $x$. If $x\le p$, let $p$ finish $x$. In any feasible assignment giving $p$ to some $y\le x$ and a set of smaller capacities to $x$, swapping those two assignments remains feasible. Hence the greedy rule is correct.↵
↵
Every positive number must be selected at least once, since repeated ceiling division alone never reaches zero. Thus $T\ge n$. Also $a_i<2^{30}$, so $T=n+30$ is always sufficient. Binary-search $T$ in this interval.↵
↵
Every capacity at least $2^{30}$ can finish one demand alone. Remove the largest $T-30$ demands with these capacities. At most $30$ demands remain; put them in a max-heap and simulate only $2^{29},\ldots,1$.↵
↵
Sorting takes $O(n\log n)$. Each check takes $O(30\log30)$, there are $O(\log30)$ checks, and the space complexity is $O(n)$.↵
↵
</spoiler>↵
↵
[2255E1-What Will Remain at the End? (Easy Version)](https://codeforces.me/contest/2255/problem/E1) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
For each position, its values over all versions form a sequence. Maintain its sum, maximum prefix, maximum suffix, and maximum subarray when appending a segment.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
A value is always in $\{-1,0,1\}$. For each possible initial value, a sequence of operations can store its final value and the summary of the generated history.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
This representation is closed under concatenating operation sequences, so it can serve as a lazy segment-tree tag.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
↵
Range updates only compose tags. A position's history is materialized when that position is queried by pushing its root-to-leaf tags.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
For a nonempty sequence segment, store $(S,P,Q,M)$: its sum, maximum prefix sum, maximum suffix sum, and maximum nonempty subarray sum. Two adjacent summaries merge in $O(1)$; a crossing maximum subarray is the left maximum suffix followed by the right maximum prefix.↵
↵
Fix one array position. Its value lies in $V=\{-1,0,1\}$. For an operation segment $T$, let $f_T(s)$ be the final value from initial state $s$, and let $H_T(s)$ summarize the values recorded while executing $T$. There are only three states, so this representation has constant size.↵
↵
If $A$ is followed by $B$, then $f_{AB}(s)=f_B(f_A(s))$ and $H_{AB}(s)=H_A(s)\mathbin{\Vert}H_B(f_A(s))$, where $\Vert$ concatenates two histories and merges their summaries. Tags therefore compose in $O(1)$.↵
↵
Each segment-tree node stores the unpushed operation segment applying to its whole interval. A range update composes tags in $O(\log n)$ nodes. After each operation, a record-current-value event is applied to the whole tree to create the new version.↵
↵
A query at $p$ pushes the tags on its root-to-leaf path and materializes all history since the previous query. If the old history has maximum suffix $Q_0$ and maximum subarray $M_0$, while the new segment has $(S,P,Q,M)$, then $M'=\max(M_0,M,Q_0+P)$ and $Q'=\max(Q,Q_0+S)$.↵
↵
Only these two old values need to persist at each position.↵
↵
Record version $0$ initially. A type-4 operation at time $i$ queries versions $0$ through $i-1$, so answer it before recording version $i$, which equals version $i-1$. Other operations update first and record afterward. Decode online input modulo $2^{64}$ exactly as specified.↵
↵
The total time complexity is $O((n+q)\log n)$ and the space complexity is $O(n)$.↵
↵
</spoiler>↵
↵
[2255E2-What Will Remain at the End? (Hard Version)](https://codeforces.me/contest/2255/problem/E2) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
The segment tree and historical maximum-subarray framework are unchanged from G1. Only the constant-size operation tag changes.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Before the first assignment, after fixing the sign of the initial $x$, every value is one of $-|x|,0,|x|$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
The first assignment removes all dependence on $x$. Split a tag into a coefficient prefix depending on $|x|$ and a fixed numeric suffix.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
↵
To compose $A$ followed by $B$, distinguish whether an assignment has occurred in either segment.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
**Solution 1**↵
↵
Without assignments, negation changes only the sign and $\max(x,0)$ only replaces a negative value with zero. For each of the three initial signs, store the summary of the coefficient sequence and the final coefficient in $\{-1,0,1\}$. Substituting the real input multiplies the sequence by $|x|$.↵
↵
The first assignment is a dividing point. Before it, values still depend on $x$; from it onward, they are fixed. Represent an operation segment by:↵
↵
- a coefficient prefix depending on $|x|$, stored for all three initial signs;↵
- a fixed numeric suffix and the final actual value.↵
↵
This representation has constant size. It is also closed under concatenation.↵
↵
If $A$ contains an assignment, its output is constant. Feeding that constant into $B$ fixes all history produced by $B$, so concatenate the fixed histories.↵
↵
If neither segment contains an assignment, compose their three coefficient states exactly as in G1.↵
↵
If only $B$ contains an assignment, append the part of $B$ before its first assignment to each coefficient prefix of $A$. The fixed suffix of $B$ becomes the fixed suffix of the result. Every case takes $O(1)$.↵
↵
Assignment, negation, $\max(x,0)$, and recording a version all have direct tags of this form. The remaining segment-tree logic and version ordering are identical to G1.↵
↵
The total time complexity is $O((n+q)\log n)$ and the space complexity is $O(n)$.↵
↵
**Solution 2**↵
↵
There is also an amortized solution that performs operation $3$ directly on the segment tree. Store the current minimum $mn$ and maximum $mx$ in every node. Range assignment and range negation use ordinary lazy tags. For operation $3$:↵
↵
- if $mn\ge0$, do nothing;↵
- if $mx\le0$, assign zero to the whole node;↵
- otherwise the node contains both positive and negative values, so recurse into its children.↵
↵
Thus operation $3$ never has to appear in a historical tag. It is materialized as several range assignments to zero.↵
↵
Call a segment-tree node bad if $mn<0<mx$.↵
↵
Let the potential $\Phi$ be the number of bad nodes. When a fully covered node is negated, $(mn,mx)$ becomes $(-mx,-mn)$, so the bad status of that node and every node below it is preserved. Assignment can only remove bad nodes. A range assignment or negation recomputes nodes only on its two boundary paths, so it creates at most $O(\log n)$ new bad nodes.↵
↵
Now consider operation $3$. Apart from $O(\log n)$ nodes on the two boundary paths, every internal node into which the recursion continues was bad before the operation. After the operation, its interval contains no negative value, so that bad node has disappeared. A recursion tree has at most one more terminal node than internal nodes. Hence one operation costs $O(\log n+D)$, where $D$ is the number of bad nodes destroyed by this operation. Operation $3$ creates no bad nodes. The initial potential is $O(n)$, while all other operations increase it by only $O(q\log n)$ in total. Therefore all operation-3 recursions take $O(n+q\log n)$ time altogether.↵
↵
The historical part still uses the four-value sequence summary from G1. After every operation, append one record-current-value event at the root. Since every clamp has already been materialized as assignment to zero, pending historical actions contain only assignment, negation, and recording.↵
↵
Before the first assignment, an initial value $x$ can only become $x$ or $-x$. It is therefore enough to keep two initial states, negative and nonnegative, storing the generated coefficient-sequence summary and the final sign. After the first assignment, all later values are independent of the initial input, so keep a fixed numeric suffix and the final value. Two such tags still compose in $O(1)$ in chronological order.↵
↵
For a query at $p$, push all tags on the root-to-leaf path and append the new history summary to the already materialized history of that position. Version $0$ and type-4 recording are handled in the same order as in Solution 1.↵
↵
The total time complexity is $O(n+q\log n)$ and the space complexity is $O(n)$.↵
↵
</spoiler>↵
↵
[2255F-Who Will Witness the End?](https://codeforces.me/contest/2255/problem/F) Idea: [user:paulzrm,2026-08-10]↵
↵
<spoiler summary="Hint 1">↵
↵
View each factor $a_u+a_v$ as choosing one endpoint of edge $(u,v)$. Every exponent is $0$, $1$, or $2$. The numbers of vertices with exponents $0$ and $2$ are equal, and these two types alternate after all other vertices are removed.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
The coefficient of a monomial type depends only on the number of variables appearing twice. Express the answer using $e_re_{n-r}$, where $e_r$ is the $r$-th elementary symmetric polynomial.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
Coefficient comparison gives a linear system that can be eliminated from high indices to low indices. Direct elimination is $O(n^2)$; use the ratio of adjacent $c_k$ and Pascal's identity to derive a short recurrence.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
↵
Adjacent equations give a second-order recurrence in $h_r,h_{r+1},h_{r+2}$. All $e_r$ are coefficients of $\prod_{i=1}^n(1+a_ix)$ and can be computed by divide-and-conquer NTT.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Expand the weight of one cyclic ordering. Choosing one term from $a_u+a_v$ is equivalent to orienting edge $(u,v)$ toward the chosen endpoint.↵
↵
Every vertex has degree two, so its exponent is $0$, $1$, or $2$. The exponent sum is $n$, hence the numbers of vertices with exponents $0$ and $2$ are equal; call both numbers $k$.↵
↵
Fix these two sets. An exponent-0 vertex has both edges directed outward, an exponent-2 vertex has both directed inward, and every ordinary vertex has one edge in and one out. After ordinary vertices are removed, the two special types must alternate. Conversely, alternation uniquely determines the orientations of all paths between them.↵
↵
For $k\ge1$, the $2k$ special vertices have $(2k-1)!$ relative cyclic orders. Fix one exponent-0 vertex as the start. The exponent-2 vertices can be permuted arbitrarily, as can the remaining exponent-0 vertices, giving $k!(k-1)!$ alternating orders. Inserting the other $n-2k$ vertices does not change this ratio. Therefore the coefficient of this monomial type over all cyclic orders is↵
↵
$$↵
c_k=\frac{(n-1)!k!(k-1)!}{(2k-1)!}.↵
$$↵
↵
For $k=0$, every vertex has one edge in and one out. The whole cycle must be consistently clockwise or counterclockwise, so↵
↵
$$↵
c_0=2(n-1)!.↵
$$↵
↵
Now consider a symmetric-polynomial representation. Let $e_r$ be defined by↵
↵
$$↵
\prod_{i=1}^n(1+a_ix)=\sum_{r=0}^n e_rx^r.↵
$$↵
↵
In $e_re_{n-r}$, fix a monomial with $k$ variables appearing twice and $k$ absent. Repeated variables must be chosen from both factors and absent variables from neither. Choose $r-k$ of the remaining $n-2k$ variables for the first factor, so its coefficient is↵
↵
$$↵
\binom{n-2k}{r-k}.↵
$$↵
↵
Let $m=\lfloor n/2\rfloor$ and write the answer as↵
↵
$$↵
\sum_{r=0}^m h_re_re_{n-r}.↵
$$↵
↵
Comparing each monomial type gives↵
↵
$$↵
c_k=\sum_{r=k}^m\binom{n-2k}{r-k}h_r↵
\qquad(0\le k\le m).↵
$$↵
↵
Equation $k$ contains only $h_k,h_{k+1},\ldots,h_m$, with coefficient $1$ on $h_k$. Thus the variables can be solved from large indices to small indices, but doing so directly takes $O(n^2)$.↵
↵
For $k\ge1$, divide two adjacent coefficients:↵
↵
$$↵
\begin{aligned}↵
\frac{c_{k+1}}{c_k}↵
&=\frac{(k+1)!k!}{(2k+1)!}↵
\frac{(2k-1)!}{k!(k-1)!}\\↵
&=\frac{k(k+1)}{(2k)(2k+1)}\\↵
&=\frac{k+1}{2(2k+1)}.↵
\end{aligned}↵
$$↵
↵
The $k=0$ case follows directly from $c_0,c_1$. Hence↵
↵
$$↵
(4k+2)c_{k+1}-(k+1)c_k=0.↵
$$↵
↵
Define↵
↵
$$↵
L_k=(k+1)c_k-(4k+2)c_{k+1}=0↵
\qquad(0\le k<m).↵
$$↵
↵
Fix $k$, set $N=n-2k$ and $j=r-k$, and let $A_t=\binom{N-2}{t}$, with out-of-range binomial coefficients equal to zero.↵
↵
Using Pascal's identity twice,↵
↵
$$↵
\binom Nj=A_j+2A_{j-1}+A_{j-2},↵
$$↵
↵
Now use↵
↵
$$↵
jA_j=(N-j-1)A_{j-1},\qquad↵
(N-j)A_{j-2}=(j-1)A_{j-1},↵
$$↵
↵
together with $r=k+j$ and $n=N+2k$. The entire coefficient calculation can be displayed as↵
↵
$$↵
\begin{aligned}↵
[h_r]L_k↵
&=(k+1)\binom Nj-(4k+2)\binom{N-2}{j-1}\\↵
&=(k+1)(A_j+2A_{j-1}+A_{j-2})-(4k+2)A_{j-1}\\↵
&=(k+1)A_j-2kA_{j-1}+(k+1)A_{j-2}\\↵
&=(r+1)A_j-(n-2)A_{j-1}+(n-r+1)A_{j-2}.↵
\end{aligned}↵
$$↵
↵
Substituting into $L_k$ and shifting the latter two indices gives↵
↵
$$↵
0=L_k=\sum_{r=k}^m\binom{n-2k-2}{r-k}↵
\left((r+1)h_r-(n-2)h_{r+1}+(n-r-1)h_{r+2}\right),↵
$$↵
↵
where out-of-range $h$ values are zero. Define↵
↵
$$↵
E_r=(r+1)h_r-(n-2)h_{r+1}+(n-r-1)h_{r+2}.↵
$$↵
↵
Then↵
↵
$$↵
\sum_{r=k}^m\binom{n-2k-2}{r-k}E_r=0.↵
$$↵
↵
Equation $k$ contains only $E_k,E_{k+1},\ldots,E_m$, with coefficient $1$ on $E_k$. Apart from the top boundary, backward elimination gives $E_r=0$, or↵
↵
$$↵
(r+1)h_r=(n-2)h_{r+1}-(n-r-1)h_{r+2}.↵
$$↵
↵
The highest two terms come directly from the original system:↵
↵
$$↵
h_m=c_m,\qquad↵
h_{m-1}=c_{m-1}-(n-2m+2)h_m.↵
$$↵
↵
If $n=2m+1$ is odd, these values satisfy $E_{m-1}=-E_m$. Their binomial coefficients in every sum are equal, so they cancel. The remaining equations give $E_{m-2},E_{m-3},\ldots,E_0=0$. Apply the second-order recurrence starting from $m-2$.↵
↵
If $n=2m$ is even, the first two values give $E_{m-1}=0$, but $E_m$ has no matching boundary term. Compute one more value from the original system:↵
↵
$$↵
h_{m-2}=c_{m-2}-4h_{m-1}-6h_m.↵
$$↵
↵
It satisfies $E_{m-2}=-E_m$. Again their coefficients are equal and they cancel, giving $E_{m-3},E_{m-4},\ldots,E_0=0$. Apply the recurrence starting from $m-3$.↵
↵
Finally compute all $e_r$ by multiplying the $n$ linear polynomials $1+a_ix$ with divide and conquer, using NTT for every convolution. Substitute the resulting coefficients into $\sum_{r=0}^m h_re_re_{n-r}$.↵
↵
The time complexity is $O(n\log^2 n)$ and the space complexity is $O(n\log n)$.↵
↵
</spoiler>↵
↵
