#PU902. USACO 2019 January Contest, Platinum — Problem 3. Train Tracking 2

    ID: 1524 传统题 文件IO:tracking2 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan19来源:usaco.orgscoring:equal_test_cases贪心

USACO 2019 January Contest, Platinum — Problem 3. Train Tracking 2

USACO 2019 January Contest, Platinum — Problem 3. Train Tracking 2

题目描述

Every day the express train goes past the farm. It has NN carriages (1≤N≤1051 \leq N \leq 10^5), each with a positive integer label between 11 and 10910^9; different carriages may have the same label. Usually, Bessie watches the train go by, tracking the carriage labels. But today is too foggy, and Bessie can't see any of the labels! Luckily, she has acquired the sliding window minimums of the sequence of carriage labels, from a reputable source in the city. In particular, she has a positive integer KK, and N−K+1N-K+1 positive integers c1,…,cN+1−Kc_1,\dots,c_{N+1-K}, where cic_i is the minimum label among carriages i,i+1,…,i+K−1i, i+1, \dots, i+K-1. Help Bessie figure out the number of ways to assign a label to each carriage, consistent with the sliding window minimums. Since this number may be very large, Bessie will be satisfied if you find its remainder modulo 109+710^9 + 7. Bessie's information is completely reliable; that is, it is guaranteed that there is at least one consistent way to assign labels.

输入格式

The first line consists of two space-separated integers, NN and KK. The subsequent lines contain the sliding window minimums c1,…,cN+1−Kc_1,\dots,c_{N+1-K}, one per line.

输出格式

A single integer: the number of ways, modulo 109+710^9 + 7, to assign a positive integer not exceeding 10910^9 to each carriage, such that the minimum label among carriages i,i+1,…,i+K−1i, i+1, \dots, i+K-1 is cic_i for each 1≤i≤N−K+11 \leq i \leq N-K+1.

数据范围

(见题面原文)

样例

样例 1

4 2
999999998
999999999
999999998
3
Problem credits: Dhruv Rohatgi