\(A\) に対し、数列 \(B=(b_1,\ldots,b_N)\) を以下のように定めます。

• \(b_1 = a_1\)
• \(b_i = a_i - a_{i-1} ( i \geq 2)\)

ここで、\(A\) の条件に対応する \(B\) の条件は以下のようになります。

• \(0 \leq b_i\)
• \(b_2,b_3,\ldots,b_N\) を \(3\) で割った余りは \(1\) または \(2\)
• \(\sum b_i \leq M\)

\(A\) と \(B\) は一対一で対応するため、条件を満たす \(B\) の個数を数えられれば良いです。

\(b_i\) を \(3\) で割った余りを \(x_i\) 、\(\lfloor \frac {b_i}{3} \rfloor\) を \(y_i\) とします。\(x_1,x_2,\ldots,x_N\) を決めたとすると、対応する \(y_1,\ldots,y_N\) の個数は \(\sum y_i \leq \lfloor \frac{M-\sum x_i} {3} \rfloor\) を満たす非負整数列 \(y_1,\ldots,y_N\) の個数に等しいです。そして、これは以下の方法により \(\mathrm {O} (1)\) で求められます。

• \(\sum y_i = t\) を満たす非負整数列 \(y_1,\ldots,y_N\) の個数は \(_{N+t-1} C _{N-1}\) に等しいです。これを \(t=0,1,\ldots\) に対しあらかじめ求め、さらに累積和を計算することで \(\sum y_i \leq t\) の場合を高速に求められます。
• また、この値は \(_{N+t} C _{N}\) に等しくなります。
  • 求めるべき値は、\(t\) 個の区別できないボールを持っているすぬけ君から \(0\) 個以上 \(t\) 個以下のボールを受け取って \(N\) 個の区別できる箱に入れる方法の個数に等しいです。ここで、すぬけ君を箱に変えるとこれが \(_{N+t}C_{N}\) に等しいと分かります。
  • 他に、経路数を考えて示すことも出来ます。(参考 https://atcoder.jp/contests/abc154/tasks/abc154_f )

\(x_1,\ldots,x_N\) については、\(x_2,x_3,\ldots,x_N\) がそれぞれ \(1\) または \(2\) であること、および \(\sum x_i\) が等しいものについては \(y_1,\ldots,y_N\) を決める方法の個数が一致することを考えると \(x_1\) の値と \(x_2,\ldots,x_N\) のうち \(1\) であるものが何個かをすべて考えれば十分であり、全体で \(\mathrm{O}(N)\) でこの問題を解くことが出来ます。