P4345 [SHOI2015]超能粒子炮·改

题意

求\(\sum_{i=0}^k\binom{n}{i}\)，\(T\)组数据

范围

\(T\le 10^5,n,j\le 10^{18}\)

---

设\(f(n,k)=\sum_{i=0}^k\binom{n}{i}\)

\[ \begin{aligned} &f(n,k)\\ =&\sum_{i=0}^k\binom{n/p}{i/p}\binom{n\%p}{i\%p}\\ =&\sum_{j=0}^{k/p-1}\binom{n/p}{j}\sum_{i=0}^{p-1}\binom{n\%p}{i}+\binom{n/p}{k/p}\sum_{i=0}^{k\%p}\binom{n\%p}{i}\\ =&f(n/p,k/p-1)f(n\%p,p-1)+\binom{n/p}{k/p}f(n\%p,k\%p) \end{aligned} \]

然后就是注意边界边界边界...wa了好久...

---

Code:

// luogu-judger-enable-o2#include 
    
     #define ll long longconst int mod=2333;int C[mod+10][mod+10],f[mod+10][mod+10],T;ll n,k;void init(){    f[0][0]=C[0][0]=1;    for(int i=1;i
     
      =mod?的特判？    if(n
     
    

---

2019.1.20