{"problem":{"name":"『MdOI R5』Many Minimizations","description":{"content":"小 L 遇到了一个经典题：给定一个长度为 $n$ 的**整数**序列 $a$，你需要在所有**单调不降**的**实数**序列中选出一个作为 $b$，最小化 $\\sum\\limits_{i=1}^n |a_i-b_i|$。可以证明答案是整数。 他一眼就秒了这个题：这不是保序回归板子吗！ 他觉得这题太水了，于是决定加强一下： 对于所有长度为 $n$ 的且满足 $\\forall i\\in[1,n]","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8923"},"statements":[{"statement_type":"Markdown","content":"小 L 遇到了一个经典题：给定一个长度为 $n$ 的**整数**序列 $a$，你需要在所有**单调不降**的**实数**序列中选出一个作为 $b$，最小化 $\\sum\\limits_{i=1}^n |a_i-b_i|$。可以证明答案是整数。\n\n他一眼就秒了这个题：这不是保序回归板子吗！\n\n他觉得这题太水了，于是决定加强一下：\n\n对于所有长度为 $n$ 的且满足 $\\forall i\\in[1,n],a_i\\in[1,m]$ 的**整数**序列 $a$，求出上面这个问题的答案的总和对**质数** $p$ 取模后的结果。其中 $n,m,p$ 是给定的常数。\n\n这下小 L 不会了。为了不让你看出来他根本就不会，他随便写了一个数据范围就把这题扔给你做了。\n\n现在压力来到了你这边，你能否顺利切掉这个题呢？\n\n## Input\n\n共一行，三个整数，依次表示 $n,m,p$。\n\n## Output\n\n共一行，一个整数，表示答案。\n\n[samples]\n\n## Background\n\n本题不是多项式题，建议先做 E。\n\n[![2.gif](https://i.postimg.cc/3JN9j60M/2.gif)](https://postimg.cc/xcrKn6Pg)\n\n## Note\n\n对于 $100\\%$ 的数据，$1\\le n\\le 5\\times 10^3$，$1\\le m\\le 10^9$，$10^9<p\\le 1.01\\times 10^9$，保证 $p$ 是质数。\n\n$\\operatorname{Subtask} 1(10\\%)$：$n,m\\le 7$。\n\n$\\operatorname{Subtask} 2(10\\%)$：$m\\le 2$。\n\n$\\operatorname{Subtask} 3(10\\%)$：$n,m\\le 50$。\n\n$\\operatorname{Subtask} 4(10\\%)$：$n\\le 50$。\n\n$\\operatorname{Subtask} 5(10\\%)$：$n,m\\le 500$。\n\n$\\operatorname{Subtask} 6(10\\%)$：$n\\le 500$。\n\n$\\operatorname{Subtask} 7(10\\%)$：$m\\le 5\\times 10^3$。\n\n$\\operatorname{Subtask} 8(30\\%)$：无特殊限制。\n\n#### 样例说明 1\n\n有以下 $8$ 种可能的情况：\n\n$a=(1,1,1),b=(1,1,1),ans=0$。\n\n$a=(1,1,2),b=(1,1,2),ans=0$。\n\n$a=(1,2,1),b=(1,1,1),ans=1$。\n\n$a=(1,2,2),b=(1,2,2),ans=0$。\n\n$a=(2,1,1),b=(1,1,1),ans=1$。\n\n$a=(2,1,2),b=(1,1,2),ans=1$。\n\n$a=(2,2,1),b=(2,2,2),ans=1$。\n\n$a=(2,2,2),b=(2,2,2),ans=0$。\n\n因此答案为 $0+0+1+0+1+1+1+0=4$。\n\n注意，对于一个固定的 $a$，最优的 $b$ 不一定唯一。上面只给出了一种可能的解。\n\n$\\operatorname{Bonus}$：在 $p$ 为 NTT 模数的情况下做到 $O(n\\log n)$。实际上在本题正解的基础上这一部分并不困难。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8923","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3 2 1000000007","4"],["5 5 1000000007","11040"],["50 50 1000000009","875463033"]],"created_at":"2026-03-03 11:09:25"}}