问题简述

给定一个长度为 $N$ 的序列（列车车厢），但序列本身未知。已知一个整数 $K$ 以及 $N-K+1$ 个滑动窗口的最小值 $c_i$（每个窗口长度为 $K$）。求有多少种方式为每个位置分配一个 $[1, 10^9]$ 的整数，使得所有窗口的最小值条件成立。答案对 $10^9+7$ 取模。

核心思路与解法

这个问题可以通过 转化约束 并利用 动态规划 与 组合计数 来解决。

1. 关键观察

如果所有 $c_i$ 都相等（设为 $v$），那么问题简化为：

• 序列中每个数 $\ge v$
• 每个长度为 $K$ 的窗口中至少有一个数 等于 $v$

这个简化问题的方案数可以用 DP 求出。

2. 一般情况处理

对于一般的 $c_i$ 序列，我们可以利用 单调栈/单调队列 找出每个位置受哪个 $c_i$ 约束最强，从而将序列分割成若干段，使得每段内部的所有 $c_i$（在对应的滑动窗口中）都相同。然后 分别计算每一段的方案数，最后相乘。

具体来说：

• 如果 $c_{i} > c_{i-1}$，那么位置 $i+K-1$ 的值必须 等于 $c_i$（因为它是新窗口的最小值，且比前一个窗口的最小值大）。
• 如果 $c_i < c_{i-1}$，那么位置 $i-1$ 的值必须 等于 $c_i$（原因对称）。
• 这些“必须等于”的位置将序列分割成多个区间。

3. 核心 DP 设计（对于一段相同最小值的区间）

设当前段的约束值为 $v$，段长度为 $L$，要求：

• 每个数 $\ge v$
• 每 $K$ 个连续位置中至少有一个 $= v$

定义 $dp[i]$ 表示处理到前 $i$ 个位置，且 第 $i$ 个位置的值等于 $v$ 的方案数。

转移：

• 如果第 $i$ 个位置是 $v$，那么前 $i-1$ 个位置只要满足约束即可（但最后 $K-1$ 个位置不能全大于 $v$，这个在转移中自然保证）。
• 更精确的转移需要考虑上一个等于 $v$ 的位置 $j$，且 $i-j \le K$（否则中间 $K$ 个位置没有 $v$）。
• 利用前缀和优化，该 DP 可在 $O(L)$ 时间内完成。

令 $f(L, v)$ 表示长度为 $L$ 的段，约束最小值为 $v$ 时的方案数。 递推式（简化版）： $dp[i] = \sum_{j=\max(0, i-K)}^{i-1} dp[j] \times (X-1)^{i-j-1}$ 其中 $X = 10^9 - v + 1$（即可以选择的数字种类数，$\ge v$），初始 $dp[0] = 1$。 最终 $f(L, v) = dp[L]$。

4. 算法步骤

1. 读入 $N, K$ 和 $c_1 \dots c_{N-K+1}$。
2. 用单调队列/单调栈找出所有“必须等于”某 $c_i$ 的位置，将序列分段。
3. 对每一段用上述 DP 计算方案数 $f(L, v)$。
4. 将所有段的方案数相乘，得到最终答案。

复杂度分析

• 分段：$O(N)$
• 每段 DP：$O(\text{段长度})$，总 $O(N)$
• 总体复杂度：$O(N)$

样例解释

输入：

4 2
999999998
999999999
999999998

• $N=4, K=2$
• $c_1=999999998, c_2=999999999, c_3=999999998$
• 分析可得序列被分割成若干段，最终计算得方案数为 3。

这份题解概括了问题的解决框架，实际实现时需要仔细处理边界条件和模运算。