{"problem":{"name":"[集训队互测 2023] Permutation Counting 2","description":{"content":"给定 $n$，对于每组 $x,y\\in [0,n)$ 求出有多少个 $1\\sim n$ 的排列 $p$ 满足以下条件： - $\\sum\\limits_{i=1}^{n-1}[p_i<p_{i+1}]=x$。 - $\\sum\\limits_{i=1}^{n-1}[p^{-1}_i<p^{-1}_{i+1}]=y$。 其中 $p^{-1}$ 表示 $p$ 的逆排列，满足 $p^{-1}_{p_i","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10004"},"statements":[{"statement_type":"Markdown","content":"给定 $n$，对于每组 $x,y\\in [0,n)$ 求出有多少个 $1\\sim n$ 的排列 $p$ 满足以下条件：\n\n- $\\sum\\limits_{i=1}^{n-1}[p_i<p_{i+1}]=x$。\n\n- $\\sum\\limits_{i=1}^{n-1}[p^{-1}_i<p^{-1}_{i+1}]=y$。\n\n其中 $p^{-1}$ 表示 $p$ 的逆排列，满足 $p^{-1}_{p_i}=i$。\n\n答案对给定的质数 $MOD$ 取模。\n\n## Input\n\n共一行，两个整数，表示 $n,MOD$。\n\n## Output\n\n共 $n$ 行，每行共 $n$ 个整数，第 $i$ 行第 $j$ 列的数表示 $x=i-1,y=j-1$ 时的答案。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 数据，$1\\le n\\le 500$，$10^9\\le MOD\\le 1.01\\times 10^9$，保证 $MOD$ 为质数。\n\n$\\operatorname{Subtask} 1(10\\%):n\\le 8$。\n\n$\\operatorname{Subtask} 2(15\\%):n\\le 16$。\n\n$\\operatorname{Subtask} 3(25\\%):n\\le 40$。\n\n$\\operatorname{Subtask} 4(25\\%):n\\le 100$。\n\n$\\operatorname{Subtask} 5(25\\%):$ 无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10004","tags":["集训队互测","2023","组合数学","容斥原理"],"sample_group":[["3 1000000007","1 0 0\n0 4 0\n0 0 1"],["5 1000000007","1 0 0 0 0\n0 20 6 0 0\n0 6 54 6 0\n0 0 6 20 0\n0 0 0 0 1"],["10 1000000007","1 0 0 0 0 0 0 0 0 0\n0 165 462 330 55 1 0 0 0 0\n0 462 9273 22023 13750 2266 66 0 0 0\n0 330 22023 147301 203610 75306 6556 66 0 0 \n0 55 13750 203610 592130 423236 75306 2266 1 0\n0 1 2266 75306 423236 592130 203610 13750 55 0\n0 0 66 6556 75306 203610 147301 22023 330 0\n0 0 0 66 2266 13750 22023 9273 462 0\n0 0 0 0 1 55 330 462 165 0\n0 0 0 0 0 0 0 0 0 1"]],"created_at":"2026-03-03 11:09:25"}}