| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11714 | Ponds |
|
| 12254 | Thanos' Dilemma |
|
Description
HT Chen gives you a map sized m ✕ n consists of only two symbols '~' and'.', representing water and land, respectively. He wonders how many ponds (consecutive position of water) are there on the map. He has a thought that if he can write a recursive function, the problem may be very easy to solve!
Input
The first line contains two integer m, n, representing the size of the map Frank gives to you.
The next m lines contain n characters, either '~' or '.', representing the status of position aij.
It is guaranteed that :
- 1 ≤ m, n ≤ 1000
Output
Please output the number of ponds on the map.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In "Avengers 3", we know that Thanos wants to eliminate half of the world to keep the world in a good balance. But, have you ever wondered about how he choose "1/2" ? Why don't he choose "1/3", "1/4", or "253/502" ?
He knows that the population of this world would just keep growing, so he calculated the formula of population of this world:
On the i-th year from the start of the world, the population of this world P(i) would be: P(i-1) + 2 * P(i-2) + P(i-3).
From this formula, he concluded that P(1)=1, P(2)=12, P(3)=13.
According to this formula, he could estimate the populations of the world on every year, so that he could choose the percentage of the population he would like to eliminate. (We don't know how he choose)
Because Thanos has a lot of planets to conquer, he asks you to calculate P(x), while x is given by him.
The world has lived for so many years, so he might ask you P(x) where x would be very large. And in case of P(x) is super large, the number should mod 109+7.
"Thanos Thinking About This Problem"
If you click on this picture, something might happen...
- Given t, indicates the number of testcases.
- P(i) = P(i-1) + 2*P(i-2) + P(i-3)
- P(1)=1, P(2)=12, P(3)=13
- Given x, you are going to calculate P(x)%(109+7) of every testcase.
Hint: use fpw(快速冪) to solve this problem!
If we rewrite the equation into matrix form, we could get the following formula:
With this formula, we can do something more:
Now, we can implement fpw(快速冪) method on the matrix power part. For those n<=3, just output the answer.
Note that you are encouraged to implement a "matrix" struct to solve this easier.
Input
The first line contains one integer t, indicates the number of testcases.
There are t lines below, each line contains one integer x.
1 <= t <= 20, 1 <= x <= 1018.
Output
For each testcase, output exactly one integer P(x)%(109+7).
Remember to output a '\n' at the end of every testcase.