#PU1283. USACO 2023 January Contest, Gold — Problem 3. Moo Route
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 , Bessie is located at on an infinite number line. She frantically searches for an exit by moving left or right by unit each second. However, there actually is no exit and after seconds, Bessie is back at , tired and resigned. Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses , given by an array (, ). Bessie never reaches nor . In particular, Bessie's route can be represented by a string of s and s where the th character represents the direction Bessie moves in during the th second. The number of direction changes is defined as the number of occurrences of s plus the number of occurrences of s. Please help Farmer Nhoj count the number of routes Bessie could have taken that are consistent with and minimize the number of direction changes. It is guaranteed that there is at least one valid route.
输入格式
The first line contains . The second line contains .
输出格式
The number of routes Bessie could have taken, modulo .
数据范围
Inputs 2-4: and Inputs 5-7: Inputs 8-11: 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