泉暖涵窗镜(Mirror)

2026 年青岛市中小学程序设计竞赛高中组 T3

给定一个长度为 $n$ 的序列 $A$ 和长度为 $m$ 的序列 $B$ （保证 $m\le n$ ）。保证 $B$ 严格单调递增。

一个序列的前缀最大值序列 $M$ 定义如下：

$M_1=A_1$ ；
对于一个位置 $i\ge 2$ ，若 $\forall 1\le j < i,a_i>a_j$ ，则设 $A_1,A_2,\cdots,A_{i-1}$ 组成的序列的前缀最大值序列的长度为 $k$ ，令 $M_{k+1}=A_i$ 。

简单来说，其意义为所有大于前面所有位置的元素的元素组成的序列。

现在，请你计算序列 $A$ ，有多少个子序列满足其前缀最大值序列等于 $B$ 。答案对 $10^9+7$ 取模。

第一行两个整数 $n,m$ ，含义见题目描述。

接下来一行 $n$ 个整数，第 $i$ 个整数表示 $A_i$ 。

接下来一行 $m$ 个整数，第 $i$ 个整数表示 $B_i$ 。

一行一个整数，表示子序列数量，答案对 $10^9+7$ 取模。

15 5
2 6 10 2 2 2 14 18 2 2 2 2 2 2 6
2 6 10 14 18

对于所有数据，保证 $1\le A_i \le 10^9$ 。

测试点编号	$N$	$M$	$A_i$	特殊性质
1 ~ 4	$\le 15$	$\le 5$	$\le 100$	无
5 ~ 6	$\le 2 \times 10^5$	$= 1$	$\le 10^9$
7 ~ 11	$\le 2000$
12 ~ 16	$\le 2 \times 10^5$			$A$ 单调不降
17 ~ 25	$\le 2 \times 10^5$			无

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

Subtask	分值	测试点编号	说明
0	10	1	样例
1	25	2~8	小规模与边界测试数据
2	30	9~16	中等规模测试数据
3	35	17~25	满规模极限测试数据

出处：原题链接

#R1149. 泉暖涵窗镜(Mirror)