I. In the clouds

Codeforces

IDCF10162I

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Tiago lives in a street with N houses, numbered from 1 to N, in which the first one is his. He decided to get out of Codeforces and visit a friend, but his head is stuck in a problem for several days. Because of that, he is bit distracted and is not paying attention to where he is going. The walk can be represented by K steps, where if he is in house i in a step, is the probability of him being at house j in the next step. He wants to know what is the expected value of the house where he'll stop, but he is too distracted to solve this problem. The first line of input consists of two integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 109). The next N lines contain each N integers, where the j-th number in the i-th line is Aij (0 ≤ Aij ≤ 106) and the sum in each line is 106. The answer can be represented as an irreducible fraction . Print the integer P * Q - 1 modulo 109 + 7 (Q - 1 is the modular inverse of Q modulo 109 + 7). ## Input The first line of input consists of two integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 109). The next N lines contain each N integers, where the j-th number in the i-th line is Aij (0 ≤ Aij ≤ 106) and the sum in each line is 106. ## Output The answer can be represented as an irreducible fraction . Print the integer P * Q - 1 modulo 109 + 7 (Q - 1 is the modular inverse of Q modulo 109 + 7). [samples]

**Definitions** Let $ N, K \in \mathbb{Z}^+ $ with $ 1 \leq N \leq 100 $, $ 1 \leq K \leq 10^9 $. Let $ A \in \mathbb{R}^{N \times N} $ be a transition matrix where $ A_{ij} \in [0, 10^6] $ and $ \sum_{j=1}^N A_{ij} = 10^6 $ for all $ i \in \{1, \dots, N\} $. Define the normalized transition matrix $ P \in \mathbb{R}^{N \times N} $ by $ P_{ij} = \frac{A_{ij}}{10^6} $. Let $ \mathbf{v}_0 = (1, 0, \dots, 0) \in \mathbb{R}^N $ be the initial state vector (Tiago starts at house 1). **Constraints** 1. $ A_{ij} \in \mathbb{Z} $, $ 0 \leq A_{ij} \leq 10^6 $ 2. $ \sum_{j=1}^N A_{ij} = 10^6 $ for all $ i \in \{1, \dots, N\} $ 3. $ P $ is a right-stochastic matrix: $ \sum_{j=1}^N P_{ij} = 1 $ for all $ i $ **Objective** Compute the expected house index after $ K $ steps: $$ \mathbf{v}_K = \mathbf{v}_0 \cdot P^K $$ Let $ \mathbb{E} = \sum_{i=1}^N i \cdot (\mathbf{v}_K)_i $ be the expected value. Express $ \mathbb{E} = \frac{P}{Q} $ in lowest terms. Output $ P \cdot Q^{-1} \mod (10^9 + 7) $, where $ Q^{-1} $ is the modular multiplicative inverse of $ Q $ modulo $ 10^9 + 7 $.

API Response (JSON)

{
  "problem": {
    "name": "I. In the clouds",
    "description": {
      "content": "Tiago lives in a street with N houses, numbered from 1 to N, in which the first one is his. He decided to get out of Codeforces and visit a friend, but his head is stuck in a problem for several days.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10162I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Tiago lives in a street with N houses, numbered from 1 to N, in which the first one is his. He decided to get out of Codeforces and visit a friend, but his head is stuck in a problem for several days....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, K \\in \\mathbb{Z}^+ $ with $ 1 \\leq N \\leq 100 $, $ 1 \\leq K \\leq 10^9 $.  \nLet $ A \\in \\mathbb{R}^{N \\times N} $ be a transition matrix where $ A_{ij} \\in [0, 10^6] $ and $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments