AT_tenka
AT_tenka1_2014_final_d 高橋君
高橋君 给定若干个 \(n,m\),求 \(\sum\limits_{i=0}^{m} \dbinom{n}{i}\)。为方便,记 \(C(n,m)=\dbinom{n}{m},S(n,m)=\sum\limits_{i=0}^{m} C(n,i)\)。 我们知道 \(C(n,m)=C(n-1,m- ......
高橋君 AT_tenka1_2014_final_d 莫队 组合数求和
和上一题类似不过这道题不能再使用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 ......