不用容斥的做法。
思路
考虑直接刻画 \(S\) 的限制。
首先有 \(S_i-S_{i-1}=A_{i+1}-A_{i}\)，即 \(S\) 的差分数组 \(D_i=S_{i+1}-S_{i}\) 满足奇数项是 \(A\) 的奇数项的差分，偶数项是 \(A\) 偶数项的差分，这启示我们将奇偶分开看。
考虑 \(D,S_N\) 的限制：
- \(\sum\limits_{1\le i\le N,2\mid i}D_i=A_{N+1}-A_2\le M\)
- \(\sum\limits_{1\le i\le N,2\nmid i}D_i=A_N-A_1\le M\)
- \(\sum\limits_{1\le i\le N}D_i=S_N-S_1\le S_N\)
- \(S_N=A_N+A_{N+1}\le 2M\)
显然通过一个 \(D\) 和 \(S_N\) 可以唯一确定一个 \(S\)。显然可以通过构造证明，满足这四个条件的任意 \(D,S_N\) 一定合法。
然后考虑计数。对于一个确定的 \(D\)，\(S_N\) 的取值方案数即为 \(2M+1-\sum D_i\)。设 \(f_0(x)\) 表示 \(D\) 偶数位上和为 \(x\) 的方案数，\(f_1(x)\) 表示 \(D\) 奇数位上和为 \(x\) 的方案数，\(s_i=\sum\limits_{x}f_i(x)\)，总方案数即为：
\[\begin{aligned}
&\sum_{x_0}\sum_{x_1} f_0(x_0)f_1(x_1)(2M+1-x_0-x_1)\\
=&(2M+1)s_0s_1-s_1\sum\limits_{x_0}f_0(x_0)x_0-s_0\sum\limits_{x_1}f_1(x_1)x_1
\end{aligned}
\]
其中 \(f_i(x)=C(x+\frac{n+i-1}{2}-1,\frac{n+i-1}{2}-1)\)。然后就可以 \(O(n+m)\) 统计。