この問題は次のように読み替えられます。

「\(S\) 段の階段があります。あなたは \(1\) 回の移動で奇数段の階段を登ることができます。階段のうち \(N\) 段は壊れていて、その段に足を踏み入れることはできません。階段の登り方は何通りありますか？」

これは ABC129C とよく似た問題です。なのでとりあえずまずは ABC129C と同じDPを考えてみましょう。

\(DP[i]=\) \(i\) 段目にたどり着く方法の数

DPテーブルをこのように決めると、遷移は \(DP[i]=DP[i-1]+DP[i-3]+DP[i-5]+\ldots\) となります。これは ABC178D と似た形の式になっているので、同様に累積和

\(EP[i]=DP[i-1]+DP[i-3]+DP[i-5]+\ldots\)

を考えることで、\(EP[i]=DP[i]=DP[i-1]+EP[i-2]\) となることがわかります。

したがってこの問題は壊れている階段がなければ \(DP[i],EP[i],EP[i-1]\) を持つ 行列累乗により \(O(\log S)\) で解くことができます。壊れている階段がある場合、そのような \(i\) については \(EP\) の遷移はそのままで \(DP[i]=0\) とすればよく、壊れている段が現れるごとにそこまでの計算結果に手を加えればよいので、全体で\(O(N\log S)\) で解くことができます。

実装例(C++)

なお、この問題を Dynamic にした問題として みんプロ2019決勝D があります。