{"problem":{"name":"[蓝桥杯 2019 国 B] 排列数","description":{"content":"在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。 对于一个 $1 ∼ n$ 的排列，如果可以将这个排列中包含 $t$ 个折点，则它称为一个 $t + 1$ 单调排列。 例如，排列 $(1, 4, 2, 3)$ 是一个 $3$ 单调排列，其中 $4$ 和 $2$ 都是折点。 给定 $n$ 和 $k$，请问 $1 ∼ n$ 的所有排列中有多少个 $k$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8699"},"statements":[{"statement_type":"Markdown","content":"在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。\n\n对于一个 $1 ∼ n$ 的排列，如果可以将这个排列中包含 $t$ 个折点，则它称为一个 $t + 1$ 单调排列。\n\n例如，排列 $(1, 4, 2, 3)$ 是一个 $3$ 单调排列，其中 $4$ 和 $2$ 都是折点。\n\n给定 $n$ 和 $k$，请问 $1 ∼ n$ 的所有排列中有多少个 $k$ 单调排列？\n\n## Input\n\n输入一行包含两个整数 $n$, $k$。\n\n## Output\n\n输出一个整数，表示答案。答案可能很大，你可需要输出满足条件的排列\n数量除以 $123456$ 的余数即可。\n\n[samples]\n\n## Note\n\n对于 $20 \\%$ 的评测用例, $1 \\leq k \\leq n \\leq 10$;\n\n对于 $40 \\%$ 的评测用例, $1 \\leq k \\leq n \\leq 20$; 对于 $60 \\%$ 的评测用例, $1 \\leq k \\leq n \\leq 100$;\n\n对于所有评测用例， $1 \\leq k \\leq n \\leq 500$ 。 \n\n蓝桥杯 2019 年国赛 B 组 G 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8699","tags":["动态规划 DP","2019","蓝桥杯国赛"],"sample_group":[["4 2\n","12\n"]],"created_at":"2026-03-03 11:09:25"}}