ちょっと図を書いてみると格子状になることが分かるので、xy座標それぞれで部分和の種類数をDP+bitsetで求めていい感じに掛け合わせることでマス数を数えます。
O(N2max(D)wordsize)O(\frac{N^2\max(D)}{\mathrm{wordsize}})O(wordsizeN2max(D))