Блог пользователя rahul_1234

Автор rahul_1234, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
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.