Sum functions Sum

$f(x,0)$ から $f(y,M)$ への寄与を求めることを考えます。 このとき、$f(x,0)$ が $f(y,M)$ に寄与する回数は、$n,m$ を$-an-bm=y-x,n+m=M$ を満たす非負整数とすると、 ${}_{n+m} C_n$ となることが分かります。
この事実は、$f(x,y)$ の値を動的計画法などによって求めることを考え、それぞれの遷移を図に起こすことで分かります。
この値は $y-x$ の値によって決まるので、累積和などを用いて $y-x$ の値ごとにまとめて寄与を求めることでこの問題を解くことが出来ました。