D. Dice

Codeforces

IDCF10270D

Time6000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Diego has bought $n$ dices to play with, all dices have $k$ sides numbered $1, 2,..., k$, also as Diego wants to trick his friends, all dices are loaded, meaning that the probability of rolling the dice is not the same for all sides. In particular, Diego loaded the dice so that all sides which are multiple of $m$ have zero probability of appearance, while all other sides have the equal probability of appearance. Diego thinks that this will be enough to win any game betting against multiples of $m$. Ivan, a friend of Diego, knows the dices are loaded and he thinks that after summing the values of the dices we can still get a good probability of having a multiple of $m$. For example, if Diego has 2 dices with 6 sides loaded, such that multiples of 3 cannot appear, then each dice could roll into 1, 2, 4 or 5 with probability 1/4 each. After throwing both dices Diego has the following possible outcomes for multiples of 3: Help Ivan to calculate the probability of having a multiple of $m$ after summing the result of rolling all $n$ loaded dices. The input consists of 3 integers $n$ ($1 <= n <= 2 * 10^6$), $k$ ($2 <= k <= 2 * 10^6$) and $m$ ($2 <= m <= 200$) — The number of dices, the number of sides in each dice and the multiple chosen to load the dices, respectively Let p/q be the probability of having a multiple of $m$ after rolling the dices. Print just a single integer: $p * q^(-1) mod 1000000007$. ## Input The input consists of 3 integers $n$ ($1 <= n <= 2 * 10^6$), $k$ ($2 <= k <= 2 * 10^6$) and $m$ ($2 <= m <= 200$) — The number of dices, the number of sides in each dice and the multiple chosen to load the dices, respectively ## Output Let p/q be the probability of having a multiple of $m$ after rolling the dices. Print just a single integer: $p * q^(-1) mod 1000000007$. [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be the number of people. Let $ D = (d_1, d_2, \dots, d_N) $ be a sequence where each $ d_i \in \{L, R\} $ represents the direction the $ i $-th person is facing in the photo. **Constraints** $ 1 \leq N \leq 10^5 $ **Objective** Compute the number of clumps $ C $, where a clump is a maximal contiguous subsequence of identical directions: $$ C = 1 + \sum_{i=2}^{N} \mathbb{I}[d_i \neq d_{i-1}] $$

API Response (JSON)

{
  "problem": {
    "name": "D. Dice",
    "description": {
      "content": "Diego has bought $n$ dices to play with, all dices have $k$ sides numbered $1, 2,..., k$, also as Diego wants to trick his friends, all dices are loaded, meaning that the probability of rolling the di",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10270D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Diego has bought $n$ dices to play with, all dices have $k$ sides numbered $1, 2,..., k$, also as Diego wants to trick his friends, all dices are loaded, meaning that the probability of rolling the di...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of people.  \nLet $ D = (d_1, d_2, \\dots, d_N) $ be a sequence where each $ d_i \\in \\{L, R\\} $ represents the direction the $ i $-th person is f...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments