06783. 中转通道 · 林老师的题库

题目描述

有n个车站在一条直线上，从左到右编号为1到n。每个车站可以有一个发射器和一个接收器。

第i个车站的发射器频道为 $p_{i}$ ，接收器频道为 $r_{i}$ 。频道是1到k之间的整数； $p_{i} = 0$ 表示没有发射器， $r_{i} = 0$ 表示没有接收器。发射和接收的频道可以不同。

你从1号车站出发，想以最少的行动次数到达n号车站。每次行动可以选择以下一种：

出发时可以立即传送。连续两次行动不能都是传送；两次传送之间至少要有一次步行。每次步行或传送都算一次行动。传送目的地可以是当前车站，这仍算一次传送。允许重复经过车站；到达终点时没有必须再步行的要求。

除了最少行动次数，还请计算使用最少行动次数的行程有多少种，答案对1000000007取模。如果两个行程在某一步的行动方式不同，或者该步的目的车站不同，就视为不同。例如从同一车站步行到某个相邻车站，与传送到那个相邻车站，是两种不同的行动。

从文件transit.in读入数据。

第一行包含两个正整数n、k。第二行包含n个整数 $p_{1}$ 、 $p_{2}$ 、…、 $p_{n}$ 。第三行包含n个整数 $r_{1}$ 、 $r_{2}$ 、…、 $r_{n}$ 。

输出到文件transit.out。

输出一行两个整数，分别表示最少行动次数，以及最短行程数量对1000000007取模的结果。相邻车站之间始终可以步行，因此一定能到达终点。

样例输入：

6 2
1 0 2 0 0 0
0 1 1 2 2 0

样例输出：

4 3

一种最短行程是：从1传送到2，步行到3，从3传送到5，步行到6。不能从1传送到3后立刻传送到5，因为连续两次传送不合法。

样例输入：

8 2
1 0 2 0 2 0 0 0
0 1 0 1 0 0 0 2

样例输出：

3 4

到达8号车站至少需要3次行动。一条行程为：从1传送到4，步行到5，再传送到8。

样例输入：

1 1
0
0

样例输出：

0 1

出发点已经是终点，不做任何行动。这是唯一一种最短行程。

对于所有测试数据： $1 \leq n \leq 200000$ ， $1 \leq k \leq n$ ， $0 \leq p_{i}$ 、 $r_{i} \leq k$ 。

共20个测试点，每点5分，独立计分。