J. Permutation

Codeforces

IDCF10247J

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given a permutation $p_1, p_2, \\dots, p_n$. You can do the following operations repeatedly: You want to know how many distinct permutations you can get using operations. The answer can be large, output the answer modulo $998244353$. The first line contains an integer $T$ denoting the number of test cases ($1 <= T <= 100000$). The first line in a test case contains two integers $n$ and $c$ ($2 <= c <= 500000$, $2 <= n <= 500000$). The sum of $n$ over all test cases does not exceed $500000$. The second line in a test case contains a permutation $p_1, \\dots, p_n$ ($1 <= p_i <= n$). For each test case, output one line containing the answer modulo $998244353$. ## Input The first line contains an integer $T$ denoting the number of test cases ($1 <= T <= 100000$).The first line in a test case contains two integers $n$ and $c$ ($2 <= c <= 500000$, $2 <= n <= 500000$). The sum of $n$ over all test cases does not exceed $500000$.The second line in a test case contains a permutation $p_1, \\dots, p_n$ ($1 <= p_i <= n$). ## Output For each test case, output one line containing the answer modulo $998244353$. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case: - Let $ n, c \in \mathbb{Z} $ with $ 2 \leq c \leq 500000 $, $ 2 \leq n \leq 500000 $. - Let $ p = (p_1, p_2, \dots, p_n) $ be a permutation of $ \{1, 2, \dots, n\} $. **Constraints** 1. $ 1 \leq T \leq 100000 $ 2. $ \sum_{\text{all test cases}} n \leq 500000 $ 3. $ 2 \leq c \leq 500000 $, $ 2 \leq n \leq 500000 $ **Operation** You may repeatedly perform the following: - Choose any contiguous subsequence of length $ c $ and reverse it. **Objective** For each test case, compute the number of distinct permutations reachable from $ p $ via any sequence of such operations, modulo $ 998244353 $.

API Response (JSON)

{
  "problem": {
    "name": "J. Permutation",
    "description": {
      "content": "You are given a permutation $p_1, p_2, \\\\dots, p_n$. You can do the following operations repeatedly: You want to know how many distinct permutations you can get using operations. The answer can be la",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10247J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a permutation $p_1, p_2, \\\\dots, p_n$. You can do the following operations repeatedly:\n\nYou want to know how many distinct permutations you can get using operations. The answer can be la...",
      "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:  \n- Let $ n, c \\in \\mathbb{Z} $ with $ 2 \\leq c \\leq 500000 $, $ 2 \\leq n \\leq 500000 $.  \n- Let $ p = (p_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments