#P11700. [ROIR 2025] 寻找宝藏
[ROIR 2025] 寻找宝藏
题目背景
翻译自 ROIR 2025 D1T4。
题目描述
为了寻找有用的矿产资源,科学家们开发了一种特殊的扫描仪。
假设搜索区域是一个包含 行和 列的表格。行号从上到下编号为 到 ,列号从左到右编号为 到 。每个单元格中可能含有矿产资源。
扫描仪的工作原理如下:它可以从第 列启动,并返回扫描区域内包含矿产资源的单元格数。扫描区域包括第 列的所有单元格、第 列的前 个单元格、第 列的前 个单元格,以此类推。下图展示了当 , 时,所有可能的 值的扫描区域。
现在,给定扫描仪返回的每个 值的结果,记为 ,即在第 列的扫描区域内,矿产资源的数量。如果一个表格的矿产资源分布能匹配扫描仪的返回值,则称这个表格是“合法的”。比如,若扫描仪返回值为 ,则其中一个合法的表格可能如下所示(含有矿产的单元格用黑色三角形表示):
你需要根据给定的扫描结果,确定合法表格的数量,并输出其对 取模的结果。注意,扫描仪可能存在故障,导致没有任何合法的表格,这种情况下应输出 。
输入格式
第一行输入两个整数 ,分别表示列数和行数()。
第二行输入 个整数 ,表示扫描仪返回的每个列的矿产数量()。
输出格式
输出一个整数,表示正确表格的数量对 取模的结果。如果没有正确的表格,输出 。
5 3
2 1 2 3 2
24
提示
本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。
子任务 | 分数 | 特殊性质 |
---|---|---|
无 |