$\displaystyle \sum_{i=a}^{b}{i \choose a}$ を求めてください。
・$1 \le a, b \le 10^{5}$
$\displaystyle {a \choose b}$ は二項係数の意味で使っている。
階乗の乗法逆元はたまに出る。
$\displaystyle \frac{1}{i!} = \frac{1}{(i+1)!} \times (i+1)$ なので、
$b!$ の乗法逆元を求めてから、小さい方に向かって順に計算すれば計算量を抑えられる。今回の制約ならやる必要ないけど。
ちなみに、
$\begin{matrix}
&\displaystyle {a \choose a} &+&\displaystyle {a+1 \choose a} &+&\displaystyle {a+2 \choose a} &+& \displaystyle {a+3 \choose a} &+& \cdots &+&\displaystyle {b-1 \choose a} &+&\displaystyle {b \choose a} \\
=&\displaystyle {a \choose {\color{blue}0}} &+&\displaystyle {a+1 \choose {\color{blue}1}} &+&\displaystyle {a+2 \choose {\color{blue}2}} &+& \displaystyle {a+3 \choose {\color{blue}3}} &+& \cdots &+&\displaystyle {b-1 \choose {\color{blue}b-a-1}} &+&\displaystyle {b \choose {\color{blue}b-a}} \\
=& {\color{blue}1} &+& {\color{blue}a+1} &+&\displaystyle {a+2 \choose 2} &+& \displaystyle {a+3 \choose 3} &+& \cdots &+&\displaystyle {b-1 \choose b-a-1} &+&\displaystyle {b \choose b-a} \\
=& && {\color{blue}a+2} &+&\displaystyle {a+2 \choose 2} &+& \displaystyle {a+3 \choose 3} &+& \cdots &+&\displaystyle {b-1 \choose b-a-1} &+&\displaystyle {b \choose b-a} \\
=& && {\color{blue}\displaystyle {a+2 \choose 1}} &+&\displaystyle {a+2 \choose 2} &+& \displaystyle {a+3 \choose 3} &+& \cdots &+&\displaystyle {b-1 \choose b-a-1} &+&\displaystyle {b \choose b-a} \\
=& && && {\color{blue}\displaystyle {a+3 \choose 2}} &+& \displaystyle {a+3 \choose 3} &+& \cdots &+&\displaystyle {b-1 \choose b-a-1} &+&\displaystyle {b \choose b-a} \\
=& && && && {\color{blue}\displaystyle {a+4 \choose 3}} &+& \cdots &+&\displaystyle {b-1 \choose b-a-1} &+&\displaystyle {b \choose b-a} \\
=& && && && && && && {\color{blue}\displaystyle {b+1 \choose b-a}} &= {\color{blue}\displaystyle {b+1 \choose a+1}}
\end{matrix}$
とできるので、それでもいい。
#!/usr/bin/env python3
# †
M = 1000000007
###
if __name__ == '__main__':
a, b = map(int, input().split())
fac = [None] * (b+1)
fac[0] = 1
for i in range(b):
fac[i+1] = fac[i] * (i+1) % M
inv = [None] * (b+1)
inv[b] = pow(fac[b], M-2, M)
for i in reversed(range(b)):
inv[i] = inv[i+1] * (i+1) % M
res = 0
for i in range(a, b+1):
res += fac[i] * inv[i-a] * inv[a] % M
res %= M
print(res)
(ΦωΦ)＜おしまい