D. Count Paths

Codeforces

IDCF10264D

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given a graph with $n$ vertices (numbered $1$ through $n$) and $m$ *directed* edges. Count paths consisting of $k$ steps (edges) and print the answer modulo $10^9 + 7$. A path can visit the same vertex or edge multiple times. The first line contains three integers $n$, $m$ and $k$ ($1 <= n <= 100$, $0 <= m <= n dot.op (n -1)$, $1 <= k <= 10^9$) — the number of vertices, the number of edges and the length of a path. The following $m$ lines describe edges. The $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 <= a_i, b_i <= n, a_i eq.not b_i$), denoting a directed edge from $a_i$ to $b_i$. There are no self-loops or multiple edges. Print the answer modulo $1000000007$. In the first sample test, we are given the following graph with $n = 3$ vertices and $m = 4$ edges. There are 5 paths of length $k = 2$: ## Input The first line contains three integers $n$, $m$ and $k$ ($1 <= n <= 100$, $0 <= m <= n dot.op (n -1)$, $1 <= k <= 10^9$) — the number of vertices, the number of edges and the length of a path.The following $m$ lines describe edges. The $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 <= a_i, b_i <= n, a_i eq.not b_i$), denoting a directed edge from $a_i$ to $b_i$. There are no self-loops or multiple edges. ## Output Print the answer modulo $1000000007$. [samples] ## Note In the first sample test, we are given the following graph with $n = 3$ vertices and $m = 4$ edges. There are 5 paths of length $k = 2$: $1 arrow.r 2 arrow.r 1$ $1 arrow.r 2 arrow.r 3$ $2 arrow.r 1 arrow.r 2$ $2 arrow.r 3 arrow.r 1$ $3 arrow.r 1 arrow.r 2$

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 1 \leq k \leq n $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of player skill levels. Let $ B = (b_1, b_2, \dots, b_k) $ be a sequence of position weights. **Constraints** 1. $ 1 \leq n \leq 10^3 $ 2. $ 1 \leq k \leq n $ 3. $ 1 \leq a_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $ 4. $ 1 \leq b_j \leq 10^5 $ for all $ j \in \{1, \dots, k\} $ **Objective** Select a strictly increasing sequence of indices $ 1 \leq i_1 < i_2 < \dots < i_k \leq n $ to maximize: $$ \sum_{j=1}^{k} a_{i_j} \cdot b_j $$

API Response (JSON)

{
  "problem": {
    "name": "D. Count Paths",
    "description": {
      "content": "You are given a graph with $n$ vertices (numbered $1$ through $n$) and $m$ *directed* edges. Count paths consisting of $k$ steps (edges) and print the answer modulo $10^9 + 7$. A path can visit the sa",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10264D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a graph with $n$ vertices (numbered $1$ through $n$) and $m$ *directed* edges. Count paths consisting of $k$ steps (edges) and print the answer modulo $10^9 + 7$. A path can visit the sa...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of player skill levels.  \nLet $ B = (b_1, b_2, \\dots, b_k) $ be a sequence of...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments