Moo Route (USACO Gold January 2023)

这题初看是没有头绪的，不同走法非常多似乎没有规律。当然可以看到一个重要条件，是Bessie采用了让她改变方向次数最少的走法。同时比较容易看到所有点的经过次数应该都是偶数。另外，来回走路的题目，一般回头点都是要点。

从两个点的最简单情况来看，问题会更容易理解一些。观察回头点的选择，比如题中例子4, 6，这个答案为 $2$ 可以这样理解：从0点出发走到1，然后不应该回头（否则肯定不是最优），接着走到2再回头到1。此时有两种选择，或者接着往前走到0，或者可以回一次头。综合来看，在所有从2回到1的时候（一共3次），在前两次中间选择一次回到2，最后一次必须继续往前走回到0。所以选择回头的时机，就带来结果为2，其它走法都是固定的。

所以仔细在纸上分析各种情况，可以得到 $n=2$ 时，这就是一个组合问题：

\texttt{ans} = \begin{cases} {A_0/2 \choose A_1/2} & A_0 \geq A_1 \\ {A_1/2-1 \choose A_0/2-1} & A_0 < A_1 \\ \end{cases}

当点数大于2的时候，这时比较关键是要看到每两个相邻的点之间的回头的选择都是独立的，所以结果可以直接用乘法原理乘起来。所以最后的结果就是：

\texttt{ans} = \prod_{i = 0..n-2} \begin{cases} {A_i/2 \choose A_{i+1}/2} & A_i \geq A_{i+1} \\ {A_{i+1}/2-1 \choose A_i/2-1} & A_i < A_{i+1} \\ \end{cases}

组合数需要事先算好，需要用到快速幂，以及费马小定理求阶乘数的逆，这个可以参考模与相关运算。

关于第一步算法的正确性证明，可以看官方题解(英文)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;              // 1e5
int a[100005];      // 1e6
int fact[500005], invfact[500005];  // factorial and inverse factorial MOD M
const int M = 1e9 + 7;
 
int C(int a, int b) {
    return (ll)fact[a] * invfact[a-b] % M * invfact[b] % M;
}
 
int modpow(int x, int p) {
    if (p == 0) return 1;
    if (p == 1) return x;
    int y = modpow(x, p/2);
    y = (ll)y * y % M;
    return p % 2 ? (ll)y * x % M : y;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        a[i] /= 2;      // use 1/2 a[i] throughout
    }
    fact[0] = fact[1] = 1;
    invfact[0] = invfact[1] = 1;
    for (int i = 2; i <= 500000; i++) {
        fact[i] = ((ll)fact[i-1] * i) % M;
        invfact[i] = modpow(fact[i], M-2);
    }
    int ans = 1;
    for (int i = 0; i < n-1; i++)
        if (a[i] >= a[i+1]) 
            ans = (ll)ans * C(a[i], a[i+1]) % M;
        else
            ans = (ll)ans * C(a[i+1]-1, a[i]-1) % M;        
    printf("%d", ans);
 
    return 0;
}