Moo Route

题目描述

农夫 Nhoj 把 Bessie 丢在了荒郊野外！在时间 $t=0$ 时，Bessie 位于一条无限数轴上的 $x=0$。她惊慌失措地寻找出口，每秒向左或向右移动 $1$ 个单位。然而实际上根本没有出口，$T$ 秒后，Bessie 又回到了 $x=0$，疲惫且认命。 农夫 Nhoj 想追踪 Bessie，但他只知道 Bessie 穿过 $x=.5, 1.5, 2.5, \ldots, (N-1).5$ 的次数，这些次数由数组 $A_0,A_1,\dots,A_{N-1}$ 给出（$1\leq N \leq 10^5$, $1 \leq A_i \leq 10^6$）。Bessie 从未到达 $x>N$，也从未到达 $x<0$。

具体来说，Bessie 的路线可以表示为一个由 $T = \sum_{i=0}^{N-1} A_i$ 个 $L$ 和 $R$ 组成的字符串，其中第 $i$ 个字符表示 Bessie 在第 $i$ 秒移动的方向。方向改变次数定义为子串 $LR$ 的出现次数加上子串 $RL$ 的出现次数。 请帮助农夫 Nhoj 计算：在满足数组 $A$ 且方向改变次数最小的前提下，Bessie 可能采取的路线条数。保证至少存在一条合法路线。

输入格式

第一行包含 $N$。 第二行包含 $A_0,A_1,\dots,A_{N-1}$。

输出格式

输出满足条件的路线数量，对 $10^9+7$ 取模。

2
4 6

2

提示

Bessie 至少必须改变方向 5 次。有两条路线对应于 Bessie 恰好改变方向 5 次： RRLRLLRRLL RRLLRRLRLL SCORING: Inputs 2-4: $N\le 2$ and $\max(A_i)\le 10^3$ Inputs 5-7: $N\le 2$ Inputs 8-11: $\max(A_i)\le 10^3$ Inputs 12-21: No additional constraints. Problem credits: Brandon Wang, Claire Zhang, and Benjamin Qi

标签: USACO|2023|Gold

来源

USACO|2023|Gold