Train Tracking 2

题目描述

每天，特快列车都会经过农场。它有 $N$ 节车厢（$1 \leq N \leq 10^5$），每节车厢都有一个正整数标签，取值在 $1$ 到 $10^9$ 之间；不同车厢可能有相同的标签。 通常，Bessie 会看着火车经过，记录车厢标签。但今天雾太大了，Bessie 看不清任何标签！幸运的是，她从城里一个可靠的来源获得了这串车厢标签序列的滑动窗口最小值。具体来说，她有一个正整数 $K$，以及 $N-K+1$ 个正整数 $c_1,\dots,c_{N+1-K}$，其中 $c_i$ 是车厢 $i, i+1, \dots, i+K-1$ 的最小标签。 请帮助 Bessie 求出：给每节车厢赋予一个标签、并与这些滑动窗口最小值一致的方案数。由于这个数量可能非常大，你只需输出其对 $10^9 + 7$ 取模的结果。 Bessie 的信息完全可靠；也就是说，保证至少存在一种一致的赋值方案。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $K$。 接下来的若干行包含滑动窗口最小值 $c_1,\dots,c_{N+1-K}$，每行一个。

输出格式

输出一个整数：将不超过 $10^9$ 的正整数分配给每节车厢的方案数（对 $10^9 + 7$ 取模），使得对每个 $1 \leq i \leq N-K+1$，车厢 $i, i+1, \dots, i+K-1$ 的最小标签为 $c_i$。

4 2
999999998
999999999
999999998

3

提示

题目来源署名：Dhruv Rohatgi

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum