MOON4 - Moon Safari (Extreme)
The first line contains an integer $T$, the number of test cases.
On the next $T$ lines, you will be given three integers $N$, $a$ and $r$.
Output $T$ lines, one for each test case, with $S(N, a, r)$.
Since the answer can get very big, output it modulo $10^9+7$.
3 4 5
6 7 8 Output: 16068
More precise information: there are 6 test cases.
Test #0: $1 \leq T \leq 100000$ and $1 \leq r \leq 1000$.
Test #1: $1 \leq T \leq 10000$ and $1 \leq r \leq 10000$.
Test #2: $1 \leq T \leq 1000$ and $1 \leq r \leq 100000$.
Test #3: $1 \leq T \leq 100$ and $1 \leq r \leq 1000000$.
Test #4: $1 \leq T \leq 10$ and $1 \leq r \leq 10000000$.
Test #5: $T = 1$ and $1 \leq r \leq 100000000$.
Please pay attention to the constraints which may differ from the previous versions.
Also please handle the constraints carefully.
We do not provide the intended time complexity in order to encourage possible various ways of thinking.
My fastest C++ code got AC under in 12.14s. (approx 2.02s per file)
Good luck and have fun :-)
- 4 is a lucky number on the moon.
- This problem is the 4th one in the Moon series.
- 4 is a power of 2, which indicates exponential increasing difficulty starting from 2.
- Moon3 has been used.
which has been used the name of Moon3 or the method of Moon3
This is Extreme. Thanks for this new trip !