L. Polycarp and Permutations

Codeforces

IDCF10083L

Time3000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Polycarp has set of integers 1, ..., N and parameters M и K. Polycarp is interested in number of permutations {ai} from numbers 1, ..., N, so that every permutation have exactly M inversions and K numbers are in their own place. Inversion is the pair of numbers i, j, so that ai > aj и i < j. Number i is postioned in it's own place if ai = i. Single line contains three integers N, M, K. 1 ≤ N ≤ 14, , 0 ≤ K ≤ N. One integer — number or permutations. ## Input Single line contains three integers N, M, K. 1 ≤ N ≤ 14, , 0 ≤ K ≤ N. ## Output One integer — number or permutations. [samples]

**Definitions** Let $ N, M, K \in \mathbb{Z} $ with $ 1 \leq N \leq 14 $, $ 0 \leq K \leq N $. Let $ S_N $ be the symmetric group on $ \{1, 2, \dots, N\} $, i.e., the set of all permutations of $ [N] $. For a permutation $ \pi \in S_N $: - An **inversion** is a pair $ (i, j) $ with $ i < j $ and $ \pi(i) > \pi(j) $. - A **fixed point** is an index $ i $ such that $ \pi(i) = i $. **Constraints** 1. $ 1 \leq N \leq 14 $ 2. $ 0 \leq K \leq N $ 3. $ M \geq 0 $ **Objective** Compute the number of permutations $ \pi \in S_N $ such that: - The number of fixed points is exactly $ K $, - The number of inversions is exactly $ M $. That is, compute: $$ \left| \left\{ \pi \in S_N \,\middle|\, \#\{i \in [N] : \pi(i) = i\} = K \text{ and } \#\{(i,j) : i < j, \pi(i) > \pi(j)\} = M \right\} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "L. Polycarp and Permutations",
    "description": {
      "content": "Polycarp has set of integers 1, ..., N and parameters M и K. Polycarp is interested in number of permutations {ai} from numbers 1, ..., N, so that every permutation have exactly M inversions and K num",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10083L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp has set of integers 1, ..., N and parameters M и K. Polycarp is interested in number of permutations {ai} from numbers 1, ..., N, so that every permutation have exactly M inversions and K num...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, M, K \\in \\mathbb{Z} $ with $ 1 \\leq N \\leq 14 $, $ 0 \\leq K \\leq N $.  \nLet $ S_N $ be the symmetric group on $ \\{1, 2, \\dots, N\\} $, i.e., the set of all permutations of $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments