{"problem":{"name":"D. Almost Identity Permutations","description":{"content":"A permutation _p_ of size _n_ is an array such that every integer from 1 to _n_ occurs exactly once in this array. Let's call a permutation an _almost identity permutation_ iff there exist at least _","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF888D"},"statements":[{"statement_type":"Markdown","content":"A permutation _p_ of size _n_ is an array such that every integer from 1 to _n_ occurs exactly once in this array.\n\nLet's call a permutation an _almost identity permutation_ iff there exist at least _n_ - _k_ indices _i_ (1 ≤ _i_ ≤ _n_) such that _p__i_ = _i_.\n\nYour task is to count the number of _almost identity_ permutations for given numbers _n_ and _k_.\n\n## Input\n\nThe first line contains two integers _n_ and _k_ (4 ≤ _n_ ≤ 1000, 1 ≤ _k_ ≤ 4).\n\n## Output\n\nPrint the number of _almost identity_ permutations for given _n_ and _k_.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"一个大小为 $n$ 的排列 $p$ 是一个数组，其中从 $1$ 到 $n$ 的每个整数恰好出现一次。\n\n我们称一个排列为 _几乎恒等排列_，当且仅当至少有 $n - k$ 个下标 $i$（$1 ≤ i ≤ n$）满足 $p_i = i$。\n\n你的任务是计算给定数字 $n$ 和 $k$ 的 _几乎恒等排列_ 的数量。\n\n第一行包含两个整数 $n$ 和 $k$（$4 ≤ n ≤ 1000$，$1 ≤ k ≤ 4$）。\n\n请输出给定 $n$ 和 $k$ 的 _几乎恒等排列_ 的数量。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $k$（$4 ≤ n ≤ 1000$，$1 ≤ k ≤ 4$）。\n\n## Output\n\n请输出给定 $n$ 和 $k$ 的 _几乎恒等排列_ 的数量。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n, k \\in \\mathbb{N} $ with $ 4 \\leq n \\leq 1000 $, $ 1 \\leq k \\leq 4 $.\n\nLet $ S_n $ denote the symmetric group on $ n $ elements, i.e., the set of all permutations of $ \\{1, 2, \\dots, n\\} $.\n\nA permutation $ \\pi \\in S_n $ is an *almost identity permutation* if the number of fixed points satisfies:\n$$\n|\\{ i \\in \\{1, 2, \\dots, n\\} \\mid \\pi(i) = i \\}| \\geq n - k.\n$$\n\nWe are to compute:\n$$\n\\sum_{j = n - k}^{n} \\binom{n}{j} \\cdot D_{n - j}\n$$\nwhere $ D_m $ denotes the number of derangements of $ m $ elements (i.e., permutations of $ m $ elements with no fixed points), and $ D_0 = 1 $.\n\n(Note: $ \\binom{n}{j} $ counts the ways to choose $ j $ fixed points, and $ D_{n-j} $ counts the derangements of the remaining $ n-j $ elements.)","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF888D","tags":["combinatorics","dp","math"],"sample_group":[["4 1","1"],["4 2","7"],["5 3","31"],["5 4","76"]],"created_at":"2026-03-03 11:00:39"}}