{"problem":{"name":"[PA 2020] Malowanie płotu","description":{"content":"**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 4 [Malowanie płotu](https://sio2.mimuw.edu.pl/c/pa-2020-1/mal/)** 今年的秋季天气已经完全破坏了 Potyczek 先生的围栏上的漆。围栏需要尽快用特殊的蓝色防水剂进行处理，以免即将到来的","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9108"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 4 [Malowanie płotu](https://sio2.mimuw.edu.pl/c/pa-2020-1/mal/)**\n\n今年的秋季天气已经完全破坏了 Potyczek 先生的围栏上的漆。围栏需要尽快用特殊的蓝色防水剂进行处理，以免即将到来的冬季对其造成不可弥补的破坏。Potyczek 先生请他邻居的勤劳儿子 Bytie 来做这件事。这个男孩今天早上完成了任务，但做得相当粗心，因为他急着参加下一轮 PA。\n\nPotyczek 先生的围栏由 $n$ 根木条组成，每根木条分为长度相等的 $m$ 段。Bytie 只把每根木条从上到下用防水剂涂了一遍，不幸的是，这可能还不足以把栅栏全部涂满。然而，在每根木条上涂防水剂的段都是连续的，每个段要么完全涂上，要么根本不涂。进一步看来，男孩所涂的那部分栅栏是一致的，即每两个连续的木条上所涂的段都存在一个非空的相交区间。\n\n例如，涂完的围栏可能如下图所示。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/2ov15dzh.png)\n\n由于以下三个原因，下图所示情况是不可能的。\n\n- 编号为 $1$ 的木条根本没涂防水剂。\n- 编号为 $3$ 的木条一致的段没有涂防水剂。\n- 编号 $5,6$ 的木条涂防水剂的部分相交区间为空。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/9f315wbr.png)\n\n编写一个程序，计算 Bytie 按照上述规则可以用多少种不同的方式来涂围栏。如果有一段围栏在其中一种方式中被涂上了颜色，而在另一种方式中没有被涂上颜色，那么就称这两种方式是不同的。方法的数量可能相当多，所以只要输出它除以质数 $p$ 的余数就可以了。\n\n## Input\n\n输入一行三个整数 $n,m,p$。分别表示木条个数，每根木条上段的个数和质数 $p$。\n\n## Output\n\n输出一个整数表示 Bytie 按照上述规则给围栏涂色的方案数对 $p$ 取模后的值。\n\n[samples]\n\n## Note\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n对于 $100\\%$ 的数据，保证 $1\\le n\\times m\\le 10^7$，$10^8\\le p\\le 10^9$，$p\\in \\mathbb{P}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9108","tags":["动态规划 DP","2020","前缀和","PA（波兰）"],"sample_group":[["3 2 100000007","17"],["6 9 813443923","57"]],"created_at":"2026-03-03 11:09:25"}}