{"problem":{"name":"[PA 2018] Skwarki","description":{"content":"**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 5 [Skwarki](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/skw/)** 。 求有多少种长度为 $ N $ 的满足以下条件的序列 ： * $ 1 \\sim N $ 这 $ N $ 个数在序列中各出现了一次","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9084"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 5 [Skwarki](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/skw/)** 。\n\n求有多少种长度为 $ N $ 的满足以下条件的序列 ：\n\n* $ 1 \\sim N $ 这 $ N $ 个数在序列中各出现了一次；\n* 进行恰好 $K$ 次操作后，该序列才只含有 $1$ 个元素。\n\n下面对操作进行描述：\n\n设 $A_i$ 为序列中的第 $i$ 个元素（$1 < i < \\mathrm{len}$ ， $\\mathrm{len}$ 为序列长度），若 $A_{i-1} > A_{i}$ 或 $A_{i+1} > A_{i}$ 则标记 $A_i$ 。 若 $A_2 > A_1$ 则标记 $A_1$ ， 若 $A_{\\mathrm{len}-1} > A_{\\mathrm{len}}$ 则标记 $A_{\\mathrm{len}}$ 。\n\n然后，将有标记的元素从序列中删除。\n\n满足条件的序列可能很多，所以请将结果对 $P$ 取模。\n\n## Input\n\n输入仅一行，包含三个整数 $N,K,P$。\n\n## Output\n\n输出一行一个整数，表示满足条件的序列个数对 $P$ 取模的结果。\n\n[samples]\n\n## Note\n\n#### 样例 1 解释\n\n所有满足条件的序列列举如下：\n\n- $(4,1,3,2,5)$\n- $(4,2,3,1,5)$\n- $(5,1,3,2,4)$\n- $(5,2,3,1,4)$\n\n------------\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n对于 $100\\%$ 的数据，保证 $1 \\le K,N \\le 1000$ , $N \\ge 2$ , $10^8 \\le P \\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9084","tags":["动态规划 DP","2018","笛卡尔树","PA（波兰）"],"sample_group":[["5 3 100000007","4"]],"created_at":"2026-03-03 11:09:25"}}