rahul_1234's blog

By rahul_1234, history, 2 months ago, ,

Airport has m runways of length n units.

The rules of game are as follows:

• One can start at any runway.

• One can switch from ith runway to jth runway if (i, j) are coprime.

• It is compulsory to switch between runway after every 1 unit.

• One has to reach end of runway.

Find number of ways in which this can be achieved. As answer could be large, print it modulo 1000000007.

1<=n<=1000000000

1<=m<=10

Plz help me in this question.

• +9

 » 2 months ago, # | ← Rev. 2 →   0 There's an obvious DP with $O(nm)$: $dp[i][j]$ is the number of ways to get on the runway $j$ unit $i$.The base is $dp[0][j] = 1$The answer is $\sum dp[n][j]$The transition is $dp[i+1][j] = \sum_{j' and j\ are\ coprime} dp[i][j']$Now when you see the transition you can use matrix expo to achieve $O(m log(n))$ complexity.
•  » » 5 weeks ago, # ^ |   0 But can we even take an array of 10^10? because in this case size of dp will be n*m which is (10^9)*10.
•  » » » 5 weeks ago, # ^ |   0 it’s matrix expo, you don’t define the whole array.