Farmer Nhoj dropped Bessie in the middle of nowhere! At time \(t=0\), Bessie is
located at \(x=0\) on an infinite number line. She frantically searches for an
exit by moving left or right by \(1\) unit each second. However, there actually is
no exit and after \(T\) seconds, Bessie is back at \(x=0\), tired and resigned.

Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses
\(x=.5, 1.5, 2.5, \ldots, (N-1).5\), given by an array \(A_0,A_1,\dots,A_{N-1}\)
(\(1\leq N \leq 10^5\), \(1 \leq A_i \leq 10^6\)). Bessie never reaches \(x>N\) nor
\(x<0\).

In particular, Bessie's route can be represented by a string of
\(T = \sum_{i=0}^{N-1} A_i\) \(L\)s and \(R\)s where the \(i\)th character represents
the direction Bessie moves in during the \(i\)th second. The number of direction
changes is defined as the number of occurrences of \(LR\)s plus the number of
occurrences of \(RL\)s.

Please help Farmer Nhoj count the number of routes Bessie could have taken that
are consistent with \(A\) and minimize the number of direction changes. It is
guaranteed that there is at least one valid route.

Problem credits: Brandon Wang, Claire Zhang, and Benjamin Qi

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

The first line contains \(N\). The second line contains \(A_0,A_1,\dots,A_{N-1}\).

The number of routes Bessie could have taken, modulo \(10^9+7\).

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > January > Gold