#PU1283. USACO 2023 January Contest, Gold — Problem 3. Moo Route

    ID: 1538 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan23来源:usaco.orgscoring:equal_test_cases动态规划

USACO 2023 January Contest, Gold — Problem 3. Moo Route

USACO 2023 January Contest, Gold — Problem 3. Moo Route

题目描述

Farmer Nhoj dropped Bessie in the middle of nowhere! At time t=0t=0, Bessie is located at x=0x=0 on an infinite number line. She frantically searches for an exit by moving left or right by 11 unit each second. However, there actually is no exit and after TT seconds, Bessie is back at x=0x=0, tired and resigned. Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses x=.5,1.5,2.5,…,(N−1).5x=.5, 1.5, 2.5, \ldots, (N-1).5, given by an array A0,A1,…,AN−1A_0,A_1,\dots,A_{N-1} (1≤N≤1051\leq N \leq 10^5, 1≤Ai≤1061 \leq A_i \leq 10^6). Bessie never reaches x>Nx>N nor x<0x<0. In particular, Bessie's route can be represented by a string of T=∑i=0N−1AiT = \sum_{i=0}^{N-1} A_i LLs and RRs where the iith character represents the direction Bessie moves in during the iith second. The number of direction changes is defined as the number of occurrences of LRLRs plus the number of occurrences of RLRLs. Please help Farmer Nhoj count the number of routes Bessie could have taken that are consistent with AA and minimize the number of direction changes. It is guaranteed that there is at least one valid route.

输入格式

The first line contains NN. The second line contains A0,A1,…,AN−1A_0,A_1,\dots,A_{N-1}.

输出格式

The number of routes Bessie could have taken, modulo 109+710^9+7.

数据范围

Inputs 2-4: N≤2N\le 2 and max⁡(Ai)≤103\max(A_i)\le 10^3 Inputs 5-7: N≤2N\le 2 Inputs 8-11: max⁡(Ai)≤103\max(A_i)\le 10^3 Inputs 12-21: No additional constraints. Problem credits: Brandon Wang, Claire Zhang, and Benjamin Qi

样例

样例 1

2
4 6
2
Bessie must change direction at least 5 times. There are two routes 
corresponding to Bessie changing direction exactly 5 times:
RRLRLLRRLL
RRLLRRLRLL