You are given an integer $n \leq 10^9$. Your task is to compute the number of ways $n$ can be expressed as the sum of even numbers. Since the answer could be very large, compute it modulo $10^9 + 7$.↵
↵
**Time limit : 1s**↵
↵
**Sample** : $n = 8$↵
↵
$8 = 6 + 2$↵
↵
$8 = 4 + 4$↵
↵
$8 = 4 + 2 + 2$↵
↵
$8 = 2 + 2 + 2 + 2$↵
↵
Therefore for $n = 8$ the answer would be $4$↵
↵
**Do anyone know how to solve this problem? Comment on the solution**↵
↵
**UPDATE**↵
Thanks to [user:Wielomian,2023-12-12] and [user:SebastianMestre,2023-12-12] for sharing some ways to solve this problem↵
↵
<spoiler summary="Solution">↵
I think the classic way this problem can be given will be with $n \leq 2\times 10^5$ since the common solution is about computing $p(\frac{n}{2})$ the partitions of $\frac{n}{2}$ which can be done in $O(N\sqrt{N})$.↵
↵
For further explication check the comments↵
↵
Not that computing $p(n)$ can be done in $O(\sqrt{n})$ but seems a bit too complex for a common problem. Check [this](https://cs.stackexchange.com/questions/149657/best-algorithm-to-calculate-the-integer-partition-number)↵
</spoiler>↵
↵
↵
↵
↵
**Time limit : 1s**↵
↵
**Sample** : $n = 8$↵
↵
$8 = 6 + 2$↵
↵
$8 = 4 + 4$↵
↵
$8 = 4 + 2 + 2$↵
↵
$8 = 2 + 2 + 2 + 2$↵
↵
Therefore for $n = 8$ the answer would be $4$↵
↵
**Do anyone know how to solve this problem? Comment on the solution**↵
↵
**UPDATE**↵
Thanks to [user:Wielomian,2023-12-12] and [user:SebastianMestre,2023-12-12] for sharing some ways to solve this problem↵
↵
<spoiler summary="Solution">↵
I think the classic way this problem can be given will be with $n \leq 2\times 10^5$ since the common solution is about computing $p(\frac{n}{2})$ the partitions of $\frac{n}{2}$ which can be done in $O(N\sqrt{N})$.↵
↵
For further explication check the comments↵
↵
Not that computing $p(n)$ can be done in $O(\sqrt{n})$ but seems a bit too complex for a common problem. Check [this](https://cs.stackexchange.com/questions/149657/best-algorithm-to-calculate-the-integer-partition-number)↵
</spoiler>↵
↵
↵
↵
