マスの集合\(S\)が区間に覆われないような数え上げを考える。

\(|S|=k\)なる\(S\)についての個数の和が求まれば、包除原理により元の問題も解ける。よって、以降はこの問題を考える。

\(S\)に\(0\)と\(M+1\)を追加し、\(S\)の要素を昇順に\(S_1<S_2<\dots<S_k\)とすると開区間\((S_i,S_{i+1})\)に含まれる区間の個数を\(c\)として\(2^c\)の積が個数となる。

\(dp[n][k]:=マスnまで選ぶか決まっていて、k個選ばないSについての個数の総和\)

として、\(k\)についてin-placeにdpを行うことを考えると、区間乗算区間和の遅延セグ木で\(O(NM \log M)\)で解ける。