rahul_1234's blog

Game of ways
By rahul_1234, history, 6 years ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

Unable to parse markup [type=CF_MATHJAX]

The answer is

Unable to parse markup [type=CF_MATHJAX]

The transition is

Unable to parse markup [type=CF_MATHJAX]

Now when you see the transition you can use matrix expo to achieve

Unable to parse markup [type=CF_MATHJAX]

complexity.
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it’s matrix expo, you don’t define the whole array.

      → Reply