P4345 [SHOI2015] 超能粒子炮·改 题解---------Lucas定理

题面：

题目
题意概括： $T$ 次询问，每次给出 $n,k$，求${\sum }_{i=0}^k{C}_n^i\%2333$。$1\le T\le 10^5，1\le n,k\le 10^{18}$。

分析：
       看到 模数是质数 并且组合数的上下标都很大，可以想到 Lucas 定理。我们根据取模后的到的余数对这 $k$ 个位置进行分类，然后计算贡献。

       当 $k\ge mod$ 时：
       $res={\sum }_{u=0}^{mod-1}{\sum }_{i=0}^{\lfloor \frac{k+1}{mod}\rfloor -1}{C}_n^{u+i\times mod}+get(n,\lfloor \frac{k+1}{mod}\rfloor ,\lfloor \frac{k+1}{mod}\rfloor \times mod,k)$
       $={\sum }_{u=0}^{mod-1}{C}_n^u\times {\sum }_{i=0}^{\lfloor \frac{k+1}{mod}\rfloor -1}{C}_{\frac{n}{mod}}^i+get(n,\lfloor \frac{k+1}{mod}\rfloor ,\lfloor \frac{k+1}{mod}\rfloor \times mod,k)$

       其中 $get(n,cnt,st,ed)={\sum }_{i=st}^{ed}{C}_n^i$。$ed-st+1<mod$。$cnt$ 是为了方便计算传上去的。

       我们发现，计算 ${\sum }_{i=0}^{\lfloor \frac{k+1}{mod}\rfloor -1}{C}_{\frac{n}{mod}}^i$ 又转化成了一个子问题。并且上下界都会除以 $mod$，所以减小的会很快。

       当 $k<mod$ 时：
       $res={\sum }_{i=0}^k{C}_n^i$。

       如果按照上面的式子去做，那么时间复杂度是 $O(T\times mod)$ 的。
       因为 $O(T\times mod)$ 是过不去的。 瓶颈在于第一种情况中枚举 $u$ 和计算 $get$ 函数，以及第二种情况中枚举 $i$。它们的复杂度是 $O(mod)$ 的。我们考虑优化。

       现在问题转变成了如何快速的求出 ${\sum }_{i=0}^k{C}_n^i，k<mod$ 以及 快速求出 ${\sum }_{i=st}^{ed}{C}_n^i,ed-st+1<mod$。

1.

       对于 ${\sum }_{i=0}^k{C}_n^i$
       我们考虑用 $Lucas$ 计算的时候， $C_n^i=C_{n\%mod}^{i\%mod}\times C_{\frac{n}{mod}}^{\frac{i}{mod}}$。
       因为 $i<mod$，所以 $C_n^i=C_{n\%mod}^i\times C_{\frac{n}{mod}}^0=C_{n\%mod}^i$。

       我们直接预处理出来 $C_i^j，0\le j\le i<mod$，以及 $S_i^j={\sum }_{k=0}^j{C}_i^k$。

       那么${\sum }_{i=0}^k{C}_n^i=S_{n\%mod}^{min(k,n\%mod)}$， $O(1)$ 调用就可以。

2.

       对于${\sum }_{i=st}^{ed}{C}_n^i,ed-st+1<mod$。
       我们考虑此时 $st$ 一定是 $mod$ 的倍数，因为 $st$ 到 $ed$ 是长度不到 $mod$ 的剩余那段。
       有一个性质是 若 $i,j<mod$，$C_n^{i+k\times mod}$ 与 $C_n^i$ 的比值 和 $C_n^{j+k\times mod}$与$C_n^j$ 的比值相同。 并且这个比值是 $C_{n/mod}^k$。这个可以用 Lucas 轻松证明。
       那么问题就很简单了，我们求出${\sum }_{i=0}^{ed-st}{C}_n^i$，然后再乘上 $C_{n/mod}^k$ 就好了。前面那个东西就是我们上面讨论的，后面那个可以用 $Lucas$ 定理在 $lo{g}_{2}n$ 的时间复杂度内求出。

       然后这道题就做完了，时间复杂度是 $O(T\times lo{g}_{2}n)$。

#include<bits/stdc++.h>// 找规律  好题啊 
using namespace std;
typedef long long LL;
const LL mod = 2333;
int T;
LL n, k, inv[mod + 10], fac[mod + 10], c[mod + 10][mod + 10];
LL sum[mod + 10][mod + 10];
LL C(int n, int m){if(n < m) return 0;else return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
LL Pow(LL x, LL y){LL res = 1, k = x % mod;while(y){if(y & 1) res = (res * k) % mod;y >>= 1;k = (k * k) % mod;}return res % mod;
}
LL Lucas(LL n, LL m){if(n < mod && m < mod) return C(n, m);else return C(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;
}
LL get(LL n, LL k, LL st, LL ed){if(st > ed) return 0;else{LL tmp = Lucas(n / mod, k);return tmp * sum[n % mod][min(ed - st, n % mod)] % mod;}
}
LL calc(LL n, LL k){// calc(n, k) = Σc[n][0] + c[n][1] + ... + c[n][k] k = min(k, n);// 取小的if(k < mod) return sum[n % mod][min(k, n % mod)];// k < mod   根据Lucas定理可知道,  c[n][i] = c[n % mod][i % mod] * c[n / mod][i / mod] = c[n % mod][i] * c[n / mod][0] = c[n % mod][i]	else return (sum[n % mod][n % mod] * calc(n / mod, (k + 1) / mod - 1LL) % mod + get(n, (k + 1) / mod, (k + 1) / mod * mod, k)) % mod;
}
int main(){fac[0] = 1LL;for(int i = 1; i < mod; i++) fac[i] = fac[i - 1] * (1LL * i) % mod;inv[mod - 1] = Pow(fac[mod - 1], mod - 2) % mod;for(int i = mod - 2; i >= 0; i--) inv[i] = inv[i + 1] * (1LL * (i + 1)) % mod;for(int i = 0; i <= mod - 1; i++){for(int j = 0; j <= i; j++){c[i][j] = C(i, j);if(!j) sum[i][j] = c[i][j] % mod;else sum[i][j] = (sum[i][j - 1] + c[i][j]) % mod;}}scanf("%d", &T);while(T--){scanf("%lld%lld", &n, &k);k = min(k, n);if(n < mod) printf("%lld\n", sum[n][k]);else{// n >= modprintf("%lld\n", calc(n, k));}}return 0;
}