problem
现在有一条数轴，\(t\) 表示当前时刻。在 \(t=0\) 时 Bessie 恰好处在 \(x=0\) 的位置。
接下来，每秒钟 Bessie 会向左或者向右移动一个单位距离，我们保证 Bessie 是在 \(0-N\) 的位置之间移动并最终停在 \(x=0\) 的位置。同时，我们有一个 \(A_0,A_1,A_2\ldots A_{N-1}\) 的数列，分别表示 Bessie 经过 \(0.5,1.5,2.5\ldots (N-1).5\) 这些点的次数。我们可以用一个由 \(\text{L}\) 和 \(\text{R}\) 组成的序列来表示 Bessie 的路径，我们称 Bessie 改变了一次方向为在序列中的相邻两个字符不同。现在我们不知道具体的移动序列是什么，但我们知道 Bessie 采用了让她改变方向次数最少的走法。现在请问 Bessie 的路径有多少种不同的可能情况？（我们称两条路径不同当且仅当这条路径对应序列中的某一位不同）
对 \(10^9+7\) 取模，\(N\le10^5,\max(A_i)\le10^6\)。
明显 \(a_i\) 全为偶数，所以我们将其除以二。
solution
假如求出前 \((i-1)\) 个的答案，现在有 \(a_{i-1}\) 个回路的一端在 \((i-1)\) 处，考虑接到 \(a_i\) 上。
因为 Bessie 采用了让她改变方向次数最少的走法，我们要尽量的让 Bessie 转弯次数尽可能的少。
一个显然的贪心是将尽量多的 \(a_i\) 接到 \(a_{i-1}\) 上，使每一个 \(a_{i-1}\) 的回路都接到 \(i\) 处。
如果 \(a_{i-1}\geq a_i\)，发现接不完，但还是要接，给每一个 \(a_i\) 安排一个 \((i-1)\) 的回路。
因为回路之间是没有区别的，所以方案数为：\(\binom{a_{i-1}}{a_i}\)。
如果 \(a_{i-1}<a_i\)，发现接完了还有剩的。考虑为了贪心，我们先给每一个 \((i-1)\) 的回路安排一个。
此时剩下 \(a_i-a_{i-1}\) 个回路，随便放在 \((i-1)\)，发现是一个经典插板法。
仔细考虑发现不需要插板：考虑第一个 \((i-1)\) 的回路一定是要了 \((i)\) 的一个回路；如果确定了其余每一个 \((i-1)\) 回路接上哪一个回路，那么我们断言：两个匹配的 \((i)\) 之间直接放进去就可以了。
同样可以推出结论为：\(\binom{a_i-1}{a_{i-1}-1}\)。
code
点击查看代码
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
const int P=1e9+7;
LL mod(LL x){return (x%P+P)%P;}
void red(LL&x){x=mod(x);}
LL qpow(LL a,LL b,int p){LL r=1;for(a%=p;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p; return r;}
template<int N,int P> struct C_prime{
LL fac[N+10],ifac[N+10];
C_prime(){
for(int i=fac[0]=ifac[0]=1;i<=N;i++) fac[i]=fac[i-1]*i%P;
ifac[N]=qpow(fac[N],P-2,P);
for(int i=N-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%P;
}
LL operator()(int n,int m){return fac[n]*ifac[n-m]%P*ifac[m]%P;}
};
int n,a[100010];
LL res=1;
C_prime<1000010,P> C;
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]>>=1;
for(int i=2;i<=n;i++){
if(a[i-1]>=a[i]) red(res*=C(a[i-1],a[i]));
else red(res*=C(a[i]-1,a[i-1]-1));
}
printf("%lld\n",res);
return 0;
}