E. Game of Dice

Codeforces

IDCF10153E

Time3000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

It is always fun to play with dice, here is one interesting game: You are given n fair dice with 6 faces, the faces does not necessarily have values from 1 to 6 written on them. instead, they can have any values from 1 to 100 written on them. Suppose you threw the n dice one after another, let us define the result of the throws as the multiplication of the numbers you get from each dice mod 109 + 7. You task is to find how many different ways you can get the result of the dice throws equal to x. The first line contains an integer T, where T is the number of test cases. The first line of each test case contains two integers n and x (1 ≤ n ≤ 14) (0 ≤ x < 109 + 7), where n is the number of the dice and x is the required result from the throws. Then n lines follow, the ith line contains 6 integers fi1, fi2, ..., fi6 (1 ≤ fij ≤ 100), giving the values of ith dice's faces. For each test case, print a single line containing how many different ways you can get the result of the dice throws equal to x ## Input The first line contains an integer T, where T is the number of test cases.The first line of each test case contains two integers n and x (1 ≤ n ≤ 14) (0 ≤ x < 109 + 7), where n is the number of the dice and x is the required result from the throws.Then n lines follow, the ith line contains 6 integers fi1, fi2, ..., fi6 (1 ≤ fij ≤ 100), giving the values of ith dice's faces. ## Output For each test case, print a single line containing how many different ways you can get the result of the dice throws equal to x [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ n_k \in \mathbb{Z} $ be the number of dice, with $ 1 \leq n_k \leq 14 $. - Let $ x_k \in \mathbb{Z} $ be the target result modulo $ M = 10^9 + 7 $, with $ 0 \leq x_k < M $. - Let $ F_k = (F_{k,1}, F_{k,2}, \dots, F_{k,n_k}) $ be a tuple of dice, where each $ F_{k,i} = \{f_{i,1}, f_{i,2}, \dots, f_{i,6}\} \subseteq \{1, 2, \dots, 100\} $ is the multiset of face values of the $ i $-th die. **Constraints** 1. $ 1 \leq T \leq \text{unspecified} $ 2. For each $ k \in \{1, \dots, T\} $: - $ 1 \leq n_k \leq 14 $ - $ 0 \leq x_k < 10^9 + 7 $ - $ 1 \leq f_{i,j} \leq 100 $ for all $ i \in \{1, \dots, n_k\} $, $ j \in \{1, \dots, 6\} $ **Objective** For each test case $ k $, compute the number of tuples $ (v_1, v_2, \dots, v_{n_k}) $ such that: $$ v_i \in F_{k,i} \quad \text{for all } i \in \{1, \dots, n_k\}, \quad \text{and} \quad \prod_{i=1}^{n_k} v_i \equiv x_k \pmod{10^9 + 7} $$

API Response (JSON)

{
  "problem": {
    "name": "E. Game of Dice",
    "description": {
      "content": "It is always fun to play with dice, here is one interesting game: You are given n fair dice with 6 faces, the faces does not necessarily have values from 1 to 6 written on them. instead, they can hav",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10153E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "It is always fun to play with dice, here is one interesting game:\n\nYou are given n fair dice with 6 faces, the faces does not necessarily have values from 1 to 6 written on them. instead, they can hav...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ be the number of dice, with $ 1 \\leq n_k \\leq 14 ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments