AGC017-F ZigZag - のいみのいみのいみのいみ

https://atcoder.jp/contests/agc017/tasks/agc017_f

$M \times \dfrac{N - 2}{4} \times 2 ^ {N-1}$ で解きます。

左に曲がったら 0, 右に曲がったら 1 として折れ線を 2 進数に変換します。隣りあった折れ線に対応する整数について、01 の列の累積和を取ったものが、どの index についても右の方が大きいことが必要十分です。

今、右側の折れ線を固定し、一個左の折れ線としてあり得るものはどんなものなのかを観察します。右の折れ線に対応する 2 進数に 1 が登場する回数を $s$ 回とします。左側で登場できる 1 の個数は明らかに $s$ 回以下です。左側で登場する 1 の個数を $t \le s$ 回とするとき、右側の 1 は前から $t$ 個のみを考慮すればいいことがわかります。