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)$.