codeforces-scrape

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

2256.md (22893B)


      1 Source: https://codeforces.com/blog/entry/155840
      2 
      3 [2256A-Three Numbers on the Blackboard](https://codeforces.com/contest/2256/problem/A) Idea: [paulzrm](/profile/paulzrm "Grandmaster paulzrm")
      4 
      5 **Hint 1**
      6 
      7 Sort the numbers as $a\le b\le c$.
      8 
      9 **Hint 2**
     10 
     11 After at least one operation, consider the median.
     12 
     13 **Hint 3**
     14 
     15 Doing nothing gives $c-a$; replacing $c$ with $a+b$ gives $b$.
     16 
     17 **Tutorial**
     18 
     19 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.
     20 
     21 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$.
     22 
     23 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)$.
     24 
     25 The time and space complexities are both $O(1)$.
     26 
     27 [2256B-Domino Tiles](https://codeforces.com/contest/2256/problem/B) Idea: [paulzrm](/profile/paulzrm "Grandmaster paulzrm")
     28 
     29 **Hint 1**
     30 
     31 Cancel the common term in the inequality between two adjacent dominoes.
     32 
     33 **Hint 2**
     34 
     35 The condition is equivalent to $s_i\ne s_{i+2}$ for every $i$.
     36 
     37 **Hint 3**
     38 
     39 Once the first two characters are fixed, the rest are determined.
     40 
     41 **Tutorial**
     42 
     43 Adjacent dominoes have different weights exactly when $s_i+s_{i+1}\ne s_{i+1}+s_{i+2}$.
     44 
     45 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$.
     46 
     47 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.
     48 
     49 The time complexity is $O(n)$ and the space complexity is $O(1)$.
     50 
     51 [2255A-Hot Potatoes at the Fairy Warehouse](https://codeforces.com/contest/2255/problem/A) / [2256C](https://codeforces.com/contest/2256/problem/C) Idea: [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan")
     52 
     53 **Hint 1**
     54 
     55 Split the 1s on the cycle into maximal runs. Unless a run covers the whole cycle, initially only its last potato can move.
     56 
     57 **Hint 2**
     58 
     59 Passing too early gives the next opportunity to players of the other team.
     60 
     61 **Hint 3**
     62 
     63 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.
     64 
     65 **Tutorial**
     66 
     67 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.
     68 
     69 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.
     70 
     71 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$:
     72 
     73 * if $s_i=1$ and $s_{i+1}=0$, the team owning $i$ scores;
     74 * if $s_i=s_{i+1}=1$, the other team scores.
     75 
     76 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.
     77 
     78 The time complexity is $O(n)$ and the space complexity is $O(1)$.
     79 
     80 [2255B-A Ribbon for Tomorrow](https://codeforces.com/contest/2255/problem/B) / [2256D](https://codeforces.com/contest/2256/problem/D) Idea: [paulzrm](/profile/paulzrm "Grandmaster paulzrm")
     81 
     82 **Hint 1**
     83 
     84 Check whether a valid reversal can change either run count or the first character.
     85 
     86 **Hint 2**
     87 
     88 In $x^ay^bx^c$, choosing one endpoint in each $x$-run lets us redistribute the total length of those two runs.
     89 
     90 **Hint 3**
     91 
     92 Operations redistribute run lengths but do not change the order of run colors.
     93 
     94 **Tutorial**
     95 
     96 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.
     97 
     98 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.
     99 
    100 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.
    101 
    102 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}$.
    103 
    104 An absent character contributes a factor of $1$.
    105 
    106 We can precompute inverses without binary exponentiation. Let the prime modulus be $P$. Since every required $i \lt 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$.
    107 
    108 Because $P\bmod i \lt i$, enumerating $i$ in increasing order computes each inverse from an earlier one. Factorials and inverse factorials follow in the same loop.
    109 
    110 Each test case takes $O(n)$ time. Preprocessing uses $O(N)$ time and space, where $N=10^6$.
    111 
    112 [2255C-Even If the World Turns](https://codeforces.com/contest/2255/problem/C) / [2256E](https://codeforces.com/contest/2256/problem/E) Idea: [paulzrm](/profile/paulzrm "Grandmaster paulzrm")
    113 
    114 **Hint 1**
    115 
    116 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.
    117 
    118 **Hint 2**
    119 
    120 Since $\gcd(w,n)=1$, $(w^{-1}S_r,w^{-1}S_c)$ behaves like the center of mass of the picture.
    121 
    122 **Hint 3**
    123 
    124 Swapping a black cell $p$ with a white cell $p+\delta$ increases the coordinate sum by $\delta$.
    125 
    126 **Hint 4**
    127 
    128 In the first run, move the center to the target. In the second run, recompute it from the transformed picture.
    129 
    130 **Tutorial**
    131 
    132 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.
    133 
    134 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.
    135 
    136 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.
    137 
    138 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.
    139 
    140 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 \gt 1$ with $L\mid n$. The black cells would be a union of complete orbits, so $L\mid w$, contradicting $\gcd(w,n)=1$.
    141 
    142 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 \lt n$ until $wt\equiv1\pmod n$; no extended Euclidean algorithm is needed.
    143 
    144 Each run takes $O(n^2)$ time and $O(n^2)$ space.
    145 
    146 [2255D-How Long Until Nothing Remains?](https://codeforces.com/contest/2255/problem/D) / [2256F](https://codeforces.com/contest/2256/problem/F) Idea: [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan")
    147 
    148 **Hint 1**
    149 
    150 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.
    151 
    152 **Hint 2**
    153 
    154 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}$.
    155 
    156 **Hint 3**
    157 
    158 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.
    159 
    160 **Tutorial**
    161 
    162 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.
    163 
    164 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$.
    165 
    166 Process capacities from largest to smallest. Let the current capacity be $p$ and the largest remaining demand be $x$. If $x \gt 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.
    167 
    168 Every positive number must be selected at least once, since repeated ceiling division alone never reaches zero. Thus $T\ge n$. Also $a_i \lt 2^{30}$, so $T=n+30$ is always sufficient. Binary-search $T$ in this interval.
    169 
    170 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$.
    171 
    172 Sorting takes $O(n\log n)$. Each check takes $O(30\log30)$, there are $O(\log30)$ checks, and the space complexity is $O(n)$.
    173 
    174 [2255E1-What Will Remain at the End? (Easy Version)](https://codeforces.com/contest/2255/problem/E1) Idea: [paulzrm](/profile/paulzrm "Grandmaster paulzrm")
    175 
    176 **Hint 1**
    177 
    178 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.
    179 
    180 **Hint 2**
    181 
    182 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.
    183 
    184 **Hint 3**
    185 
    186 This representation is closed under concatenating operation sequences, so it can serve as a lazy segment-tree tag.
    187 
    188 **Hint 4**
    189 
    190 Range updates only compose tags. A position's history is materialized when that position is queried by pushing its root-to-leaf tags.
    191 
    192 **Tutorial**
    193 
    194 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.
    195 
    196 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.
    197 
    198 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)$.
    199 
    200 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.
    201 
    202 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)$.
    203 
    204 Only these two old values need to persist at each position.
    205 
    206 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.
    207 
    208 The total time complexity is $O((n+q)\log n)$ and the space complexity is $O(n)$.
    209 
    210 [2255E2-What Will Remain at the End? (Hard Version)](https://codeforces.com/contest/2255/problem/E2) Idea: [paulzrm](/profile/paulzrm "Grandmaster paulzrm")
    211 
    212 **Hint 1**
    213 
    214 The segment tree and historical maximum-subarray framework are unchanged from G1. Only the constant-size operation tag changes.
    215 
    216 **Hint 2**
    217 
    218 Before the first assignment, after fixing the sign of the initial $x$, every value is one of $-|x|,0,|x|$.
    219 
    220 **Hint 3**
    221 
    222 The first assignment removes all dependence on $x$. Split a tag into a coefficient prefix depending on $|x|$ and a fixed numeric suffix.
    223 
    224 **Hint 4**
    225 
    226 To compose $A$ followed by $B$, distinguish whether an assignment has occurred in either segment.
    227 
    228 **Tutorial**
    229 
    230 **Solution 1**
    231 
    232 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|$.
    233 
    234 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:
    235 
    236 * a coefficient prefix depending on $|x|$, stored for all three initial signs;
    237 * a fixed numeric suffix and the final actual value.
    238 
    239 This representation has constant size. It is also closed under concatenation.
    240 
    241 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.
    242 
    243 If neither segment contains an assignment, compose their three coefficient states exactly as in G1.
    244 
    245 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)$.
    246 
    247 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.
    248 
    249 The total time complexity is $O((n+q)\log n)$ and the space complexity is $O(n)$.
    250 
    251 **Solution 2**
    252 
    253 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$:
    254 
    255 * if $mn\ge0$, do nothing;
    256 * if $mx\le0$, assign zero to the whole node;
    257 * otherwise the node contains both positive and negative values, so recurse into its children.
    258 
    259 Thus operation $3$ never has to appear in a historical tag. It is materialized as several range assignments to zero.
    260 
    261 Call a segment-tree node bad if $mn \lt 0 \lt mx$.
    262 
    263 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.
    264 
    265 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.
    266 
    267 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.
    268 
    269 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.
    270 
    271 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.
    272 
    273 The total time complexity is $O(n+q\log n)$ and the space complexity is $O(n)$.
    274 
    275 [2255F-Who Will Witness the End?](https://codeforces.com/contest/2255/problem/F) Idea: [paulzrm](/profile/paulzrm "Grandmaster paulzrm")
    276 
    277 **Hint 1**
    278 
    279 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.
    280 
    281 **Hint 2**
    282 
    283 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.
    284 
    285 **Hint 3**
    286 
    287 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.
    288 
    289 **Hint 4**
    290 
    291 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.
    292 
    293 **Tutorial**
    294 
    295 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.
    296 
    297 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$.
    298 
    299 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.
    300 
    301 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
    302 
    303 $ c_k=\frac{(n-1)!k!(k-1)!}{(2k-1)!}. $
    304 
    305 For $k=0$, every vertex has one edge in and one out. The whole cycle must be consistently clockwise or counterclockwise, so
    306 
    307 $ c_0=2(n-1)!. $
    308 
    309 Now consider a symmetric-polynomial representation. Let $e_r$ be defined by
    310 
    311 $ \prod_{i=1}^n(1+a_ix)=\sum_{r=0}^n e_rx^r. $
    312 
    313 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
    314 
    315 $ \binom{n-2k}{r-k}. $
    316 
    317 Let $m=\lfloor n/2\rfloor$ and write the answer as
    318 
    319 $ \sum_{r=0}^m h_re_re_{n-r}. $
    320 
    321 Comparing each monomial type gives
    322 
    323 $ c_k=\sum_{r=k}^m\binom{n-2k}{r-k}h_r \qquad(0\le k\le m). $
    324 
    325 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)$.
    326 
    327 For $k\ge1$, divide two adjacent coefficients:
    328 
    329 $ \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} $
    330 
    331 The $k=0$ case follows directly from $c_0,c_1$. Hence
    332 
    333 $ (4k+2)c_{k+1}-(k+1)c_k=0. $
    334 
    335 Define
    336 
    337 $ L_k=(k+1)c_k-(4k+2)c_{k+1}=0 \qquad(0\le k \lt m). $
    338 
    339 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.
    340 
    341 Using Pascal's identity twice,
    342 
    343 $ \binom Nj=A_j+2A_{j-1}+A_{j-2}, $
    344 
    345 Now use
    346 
    347 $ jA_j=(N-j-1)A_{j-1},\qquad (N-j)A_{j-2}=(j-1)A_{j-1}, $
    348 
    349 together with $r=k+j$ and $n=N+2k$. The entire coefficient calculation can be displayed as
    350 
    351 $ \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} $
    352 
    353 Substituting into $L_k$ and shifting the latter two indices gives
    354 
    355 $ 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), $
    356 
    357 where out-of-range $h$ values are zero. Define
    358 
    359 $ E_r=(r+1)h_r-(n-2)h_{r+1}+(n-r-1)h_{r+2}. $
    360 
    361 Then
    362 
    363 $ \sum_{r=k}^m\binom{n-2k-2}{r-k}E_r=0. $
    364 
    365 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
    366 
    367 $ (r+1)h_r=(n-2)h_{r+1}-(n-r-1)h_{r+2}. $
    368 
    369 The highest two terms come directly from the original system:
    370 
    371 $ h_m=c_m,\qquad h_{m-1}=c_{m-1}-(n-2m+2)h_m. $
    372 
    373 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$.
    374 
    375 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:
    376 
    377 $ h_{m-2}=c_{m-2}-4h_{m-1}-6h_m. $
    378 
    379 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$.
    380 
    381 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}$.
    382 
    383 The time complexity is $O(n\log^2 n)$ and the space complexity is $O(n\log n)$.