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≤N≤105), each with a positive integer label between?11and?109109; 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?Kc1,…,cN+1?K, where?cici?is the minimum label among carriages?i,i+1,…,i+K?1i,i+1,…,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+7109+7.

Bessie's information is completely reliable; that is, it is guaranteed that there is at least one consistent way to assign labels.

OUTPUT FORMAT (file tracking2.out):

A single integer: the number of ways, modulo?109+7109+7, to assign a positive integer not exceeding?109109?to each carriage, such that the minimum label among carriages?i,i+1,…,i+K?1i,i+1,…,i+K?1?is?cici?for each?1≤i≤N?K+11≤i≤N?K+1.

SAMPLE INPUT:

4 2 999999998 999999999 999999998

SAMPLE OUTPUT:

3

Problem credits: Dhruv Rohatgi

以上就是關于【USACO 2019 January Contest Platinum Problem 3 Train Tracking 2】的解答，如需了解學校/賽事/課程動態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

NOAI人工智能奧賽 2026-2027 活動章程出爐：新規(guī)則必看！

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學申請的“核武器”來了！