← 返回题目列表

AtCoder · pakencamp_2021_day2_j

J. 最小-最大序列

中文机器翻译题面 查看原题

配点 : 500 点

問題文

正整数 N,M 和长度 给出了 N 整数序列 我想到了使用 T=(T_1,T_2,\ldots,T_N),A=(A_1,A_2,\ldots,A_N) 。

所有元素都是 长度小于或等于 1 以上 M 长度小于或等于 N+1 的正整数序列 b=(b_1,b_2,\ldots,b_{N+1}) 和所有 对于 i\ (1 \le i \le N) ,计算满足以下条件的项目数。 当 998244353 求余数。

  • T_i=0 时, \min(b_i,b_{i+1})=A_i
  • T_i=1 时, \max(b_i,b_{i+1})=A_i

制約

  • 1 \le N, M \le 2 \times 10^5
  • T_i \in \{0, 1 \}
  • 1 \le A_i \le M
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
T_1 T_2 \ldots T_N
A_1 A_2 \ldots A_N

出力

打印答案。


入力例 1

2 2
0 0
1 2

出力例 1

1

b=(1,2,2) 满足条件。 除以


入力例 2

2 4
0 1
1 2

出力例 2

6

入力例 3

15 509
1 0 1 1 1 1 0 1 1 1 1 1 1 0 0
367 241 241 160 160 156 156 459 395 288 288 408 505 270 270

出力例 3

684062245

998244353 时不要忘记求余数。

原案: 海龟0123__