## Editorial for Back To School '18: An FFT Problem

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

Subtasks 1 and 2 are intended to reward brute force solutions.

Time Complexity: or

Subtask 3 is troll.

The intended solution for Subtask 4 was dynamic programming. Let represent the sum of all combinations of size for the first books.

Another perspective to take is that this problem is equivalent to finding the coefficients of the expansion of , except the leading coefficient, which is always . This can be proven with Vieta's formulas. The most straightforward implementation of this method yields the same recurrence relation as the first method.

Time Complexity:

## Comments