### fanache99's blog

By fanache99, history, 10 months ago,

Solutions to E, H, I, K anyone?

• +65

 » 10 months ago, # |   +48 Here's the official tutorial by tourist.
 » 10 months ago, # |   +49 The editorial of C tells us to find $(1+x+x^2)^k$ using "binary exponentiation and FFT". It may be understood as "multiply the polynomial by itself about log times", but in fact one can do fft, then $x \mapsto x^k$, then inverse fft. Though it still requires binary exponentiation, I believe that it should be faster than binary polynomial exponentiation (though it is kinda the same asymptotically).
•  » » 10 months ago, # ^ | ← Rev. 2 →   +23 Iirc some people commented about some way to find that in O(N), maybe adamant can reply here or make a blog about it.Edit: I'd welcome a blog like that if one doesn't exist, but here's the comment that someone linked: https://codeforces.com/blog/entry/73947?#comment-581173
•  » » » 10 months ago, # ^ | ← Rev. 4 →   +30 For $Q(x) = P^k(x)$ and $\deg P(x) = m$ it is possible to compute first $n$ terms of $Q(x)$ in $O(nm)$: $Q'(x) P(x) = k P^k(x) P'(x) = kQ(x) P'(x).$Hence, $q_i = \frac{1}{i p_0} \sum\limits_{j=1}^{\min(i,m)} p_j q_{i-j} [kj - (i-j)].$This, indeed, provides a way to compute $(1+x+x^2)^k$ in $O(k)$.This approach was also explained in ODE techniques article, section "Exp in Gennady Korotkevich Contest 5".
 » 10 months ago, # |   +5 E: In the tree you can solve with two phases of DP. First, you count the number of reachable vertices in subtree (in bottom-up order), Second, you count the number of reachable vertices not in subtree (in top-down order) with help of the first computed values. In the cactus you just do the same thing. At least it's easier to write than B.K: Do binary search, compute the min/max number of possible zeroes with DP (+ deques to optimize). If the desired number of zeroes fits into the interval, then the answer exists. I didn't prove it, but if you believe it, then you can just backtrack the DP to find the answer.
 » 10 months ago, # |   0 In editorial of F there is a small typo: $f(l, r) = 2f(\lfloor l/2 \rfloor, \lfloor r/2 \rfloor) + (l\%2)$