F. Function

Codeforces

IDCF10225F

Time1000ms

Memory128MB

Difficulty—

English · Original

Formal · Original

You are given a permutation $a$ obtained from $0$ to $(n -1)$, and a permutation $b$ obtained from $0$ to $(m -1)$. Let's define a function $f$, which maps each integer between $0$ and $(n -1)$, to an integer between $0$ and $(m -1)$. Please calculate the number of different functions $f$ satisfying that $f (i) = b_{f (a_i})$ for each $i$. Two functions are considered different if and only if there exists at least one integer mapped to different integers in these functions. The answer can be a bit large, so you should output it modulo $(10^9 + 7)$ instead. The input contains multiple test cases. For each test case, the first line contains two integers $n$, $m$ ($1 <= n, m <= 10^5$). The second line contains $n$ integers, the $i$-th number of which is $a_{i -1}$ ($0 <= a_{i -1} <= n -1$). The third line contains $m$ integers, the $i$-th number of which is $b_{i -1}$ ($0 <= b_{i -1} <= m -1$). It is guaranteed that the sum of $n$ and the sum of $m$ in all test cases are no more than $10^6$ respectively. For each test case, output "_Case #x: y_" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case. ## Input The input contains multiple test cases.For each test case, the first line contains two integers $n$, $m$ ($1 <= n, m <= 10^5$).The second line contains $n$ integers, the $i$-th number of which is $a_{i -1}$ ($0 <= a_{i -1} <= n -1$).The third line contains $m$ integers, the $i$-th number of which is $b_{i -1}$ ($0 <= b_{i -1} <= m -1$).It is guaranteed that the sum of $n$ and the sum of $m$ in all test cases are no more than $10^6$ respectively. ## Output For each test case, output "_Case #x: y_" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of students. Let $ S = \{s_1, s_2, \dots, s_n\} $ be the set of distinct student names. Let $ \mathcal{P} $ be a partition of $ S $, initially $ \mathcal{P} = \{ \{s\} \mid s \in S \} $. Let $ q \in \mathbb{Z}^+ $ be the number of queries. **Constraints** 1. $ 2 \leq n \leq 10^5 $ 2. $ 1 \leq q \leq 10^5 $ 3. Each student name $ s_i $ is a string of length $ 2 \leq |s_i| \leq 10 $, with first letter uppercase, rest lowercase, all distinct. 4. For each query $ i $: - $ t_i \in \{1, 2\} $ - $ s_x, s_y \in S $, $ s_x \neq s_y $ - If $ t_i = 1 $, merge the sets containing $ s_x $ and $ s_y $ in $ \mathcal{P} $ (if not already in same set). - If $ t_i = 2 $, query whether $ s_x $ and $ s_y $ belong to the same set in $ \mathcal{P} $. 5. At least one query of type $ 2 $ exists. **Objective** For each query of type $ 2 $, output: $$ \begin{cases} \text{"yes"} & \text{if } \exists\, P \in \mathcal{P} \text{ such that } s_x \in P \text{ and } s_y \in P \\ \text{"no"} & \text{otherwise} \end{cases} $$

API Response (JSON)

{
  "problem": {
    "name": "F. Function",
    "description": {
      "content": "You are given a permutation $a$ obtained from $0$ to $(n -1)$, and a permutation $b$ obtained from $0$ to $(m -1)$. Let's define a function $f$, which maps each integer between $0$ and $(n -1)$, to a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10225F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a permutation $a$ obtained from $0$ to $(n -1)$, and a permutation $b$ obtained from $0$ to $(m -1)$.\n\nLet's define a function $f$, which maps each integer between $0$ and $(n -1)$, to a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of students.  \nLet $ S = \\{s_1, s_2, \\dots, s_n\\} $ be the set of distinct student names.  \nLet $ \\mathcal{P} $ be a partition of $ S $, init...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments