A5443 | 午枫的填数游戏
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
小午有一个长度为 $n$ 的序列 $a$ ，起初，序列 $a$ 的元素都为 $0$ 。
现在小午给了小枫 $q$ 个数对 $(p_i,v_i)$ ，要求小枫按顺序执行这 $q$ 个数对，其中每个数对可以按照以下两种方式中的一种进行执行：
+ 将序列 $a$ 中 $a_1,a_2,\cdots,a_{p_i}$ 替换为 $v_i$ 。但是在执行这个操作之前，必须保证 $a_1,a_2,\cdots,a_{p_i}$ 所有元素都小于或等于 $v_i$ 。
+ 将序列 $a$ 中 $a_{p_i},a_{p_i+1},\cdots,a_{n}$ 替换为 $v_i$ 。但是在执行这个操作之前，必须保证 $a_{p_i},a_{p_i+1},\cdots,a_{n}$ 所有元素都小于或等于 $v_i$ 。
如果对于存在一个数对无法执行，那小枫就会生气。
小午想知道有多少种不同的执行序列可以把 $q$ 个数对执行完，如果无法全部执行，则输出
现在小午给了小枫 $q$ 个数对 $(p_i,v_i)$ ，要求小枫按顺序执行这 $q$ 个数对，其中每个数对可以按照以下两种方式中的一种进行执行：
+ 将序列 $a$ 中 $a_1,a_2,\cdots,a_{p_i}$ 替换为 $v_i$ 。但是在执行这个操作之前，必须保证 $a_1,a_2,\cdots,a_{p_i}$ 所有元素都小于或等于 $v_i$ 。
+ 将序列 $a$ 中 $a_{p_i},a_{p_i+1},\cdots,a_{n}$ 替换为 $v_i$ 。但是在执行这个操作之前，必须保证 $a_{p_i},a_{p_i+1},\cdots,a_{n}$ 所有元素都小于或等于 $v_i$ 。
如果对于存在一个数对无法执行，那小枫就会生气。
小午想知道有多少种不同的执行序列可以把 $q$ 个数对执行完，如果无法全部执行，则输出
0 。当且仅当有 $1\leq i\leq q$ 使得第 $i$ 个执行方式的选择不同时，两个执行序列不同。
输入格式
第一行输入两个整数 $n,q$ $(2\leq n\leq 5000, 1\leq q\leq 5000)$ ，分别表示序列 $a$ 的长度以及数对数量。
接下来 $q$ 行，每行两个整数 $p_i,v_i$ $(1\leq p_i\leq n,1\leq v_i\leq 10^9)$ ，表示第 $i$ 个数对中的元素。
接下来 $q$ 行，每行两个整数 $p_i,v_i$ $(1\leq p_i\leq n,1\leq v_i\leq 10^9)$ ，表示第 $i$ 个数对中的元素。
输出格式
输出一个整数，表示有多少种不同的执行序列可以把 $q$ 个数对执行完，由于答案可能很大，最终结果对 $998244353$ 取模。
输入输出样例
输入 #1
8 3 1 8 8 1 2 1
输出 #1
1
输入 #2
8 3 8 1 1 8 1 2
输出 #2
0
样例1解释
小枫只能进行以下方式执行：
+ 将 $a_1$ 替换为 $8$
+ 将 $a_8$ 替换为 $1$
+ 将 $a_2,a_3,\cdots,a_8$ 替换为 1
没有其他的执行序列不会让小枫生气。
小枫只能进行以下方式执行：
+ 将 $a_1$ 替换为 $8$
+ 将 $a_8$ 替换为 $1$
+ 将 $a_2,a_3,\cdots,a_8$ 替换为 1
没有其他的执行序列不会让小枫生气。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？