和上一题类似不过这道题不能再使用Lucas定理了。
即\(m\)组询问 \(\sum_{i=0}^kC(n,i)\%\ 1e9+7,n,m,k\le 100000\)
这是一个很经典的莫队求组合数的和的问题。
因为有两个指针\(l,r\)
显然需要处理四种情况:
\(l,r->l+1,r\)此时加上\(C(r,l+1)\)即可。
\(l,r->l-1,r\)此时减去\(C(r,l)\)即可。
\(l,r->l,r+1\)此时加上\(\sum_{i=0}^{l-1}C(r,i)\)即可。
\(l,r->l,r-1\)此时减去\(\sum_{i=0}^{l-1}C(r-1,i)\)即可。