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.
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.
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.
it’s matrix expo, you don’t define the whole array.