Problem #411

Standard Nim
Public 3w:5d 8xp Math 53.8%

Let $C(n, k)$ be the number of integer solutions $(x_1, \ldots, x_k)$ such that $\bigoplus_{i=1}^k x_i = 0$ and $0 \le x_i < n$ for each $i$. Here, $x \oplus y$ means $x$ xor $y$.

Let $F(n)$ be the $n$-th fibonacci number: $F(0) = 0, F(1) = 1$, and $F(i) = F(i - 1) + F(i - 2)$ for $i \ge 2$.

Let $$ S(n) := \sum_{i=1}^{n} \sum_{j=1}^{n} C(F(i), F(j)). $$ You are given $S(6) = 2153296$ and $S(7) = 18998620089329$.

Find $S(92)$ modulo $10^9 + 7$.

[My timing] 0.3 seconds.




You need to be a member to keep track of your progress.
Register


Time may end, but hope will last forever.

Other Challenge Sites

Contact

elasolova
[64][103][109][97][105][108][46][99][111][109]