This is for those of you who are struggling with BINOFEV.
As a disclaimer, this time even though I tried all the problems, I did not submit any solution at all, since I was learning efficent implementations of HLD, centroid decomp etc and didn’t want to risk half-solving the problems.
First of all, its fft, a variant of it actually, called NTT.
You can read about it on CP Algorithms (google it). I recommend writing your own implementation though, as the CP one uses vector instead of int* which won’t pass TL here.
Now, many of you would have realised that it’s NTT but were still stuck.
Read this problem and its editorial. The latex does not render well in the editorial, but if you bear with it you’ll realise (if you’ve spent 15-30 min on BINOFEV) that BINOFEV is almost exactly the same as CHEFKNN, except that it has an added summation on top of all that
Though the solution directly based off CHEFKNN won’t pass immediately, I’m sure most of you can find workarounds to it.
Also, how should I do Scoring Pairs? It’s the only problem I couldn’t manage to do. I kind of half solved it, like I got a dp table for the cases when L and R are powers of 10, and using that I extended it to all even L,R and stuff but I couldn’t get the full solution.
This time I feel there were too many ad hoc problems in DEC19A. I don’t mind too much, but still it felt like many of the questions were maybe more math oriented than CS oriented. What do you all feel?
Edit: I have deliberately kept it hand-wavy, like there is still 3-4 lines of math you’ll need to work out before CHEFKNN seems identical. But once you do it, it seems almost the exact same question.
If you couldn’t figure out how, do it like this:
Suppose p^i (p^i - 1) \cdots (p^i - r + 1) = \sum _{j=1} ^r a_j p^{ji}
Then
S = \frac{1}{r!} \sum _{j=1} ^r a_j \frac{p^{N(j+1)} - 1}{p^j - 1}
Also, change variable to j (not r as i wrote by mistake).
So you have to calculate a_j's fast, now refer CHEFKNN.