题目描述
有 $t$ 组数据，每组数据给定 $n,k$，求 $\sum_{i=0}^kC_n^i\mod 2333$ 的值。
$t\le 100000$，$n,k\le 10^{18}$。
算法分析
感觉可能是套路题……
设 $f[n][k]=\sum_{i=0}^kC_n^i\mod 2333$，推一下式子。
由 Lucas 定理得 $f[n][k]=\sum_{i=0}^kC_n^i\mod 2333=\sum_{i=0}^kC_{n/p}^{i/p}C_{n\mod p}^{i\mod p}$，这里的 $/$ 表示的是下取整，$p$ 表示模数 $2333$。
看到 $\sum_{i=0}^k$ 和 $i/p$ 可以考虑数论分块，则 $f[n][k]$
$=\sum_{i=0}^{k/p-1}C_{n/p}^i\sum_{j=0}^{p-1}C_{n\mod p}^j+\sum_{i=0}^{k\mod p}C_{n/p}^{k/p}C_{n\mod p}^{i}$
$=f[n/p][k/p-1]\times f[n\mod p][p-1]+C_{n/p}^{k/p}\times f[n\mod p][k\mod p]$。
其中 $n,k\lt p$ 时 $f[n][k]$ 的值可以直接 $n^2$ 组合数递推枚举出来，$C_{n/p}^{k/p}$ 的值可以直接使用 Lucas 定理求出，而 $f[n/p][k/p-1]$ 的值直接递归下去即可。
时间复杂度是 $O(p^2+t\log_p{max{n,k}})$。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <cstdio>
typedef long long int ll;
const int p=2333;
inline int inc(int x,int y) {x+=y;return x>=p?x-p:x;}
int c[2505][2505],f[2505][2505];
inline int Lucas(ll n,ll k) {
if(n<p&&k<p) return c[n][k];
return Lucas(n/p,k/p)*c[n%p][k%p]%p;
}
inline int calc(ll n,ll k) {
if(n<p&&k<p) return f[n][k];
return inc(calc(n/p,k/p-1)*f[n%p][p-1]%p,f[n%p][k%p]*Lucas(n/p,k/p)%p);
}
int main() {
int t;scanf("%d",&t);
c[0][0]=1;
for(register int i=1;i<p;++i) {
c[i][0]=1;
for(register int j=1;j<=i;++j) c[i][j]=inc(c[i-1][j-1],c[i-1][j]);
}
for(register int i=0;i<p;++i) {
f[i][0]=c[i][0];
for(register int j=1;j<p;++j) f[i][j]=inc(f[i][j-1],c[i][j]);
}
while(t--) {
ll n,k;scanf("%lld%lld",&n,&k);
if(n<2333&&k<2333) printf("%d\n",f[n][k]);
else printf("%d\n",calc(n,k));
}
return 0;
}
|