P4345 [SHOI2015] 超能粒子炮·改 题解
求
\[\sum_{i = 0}^k \binom{n}{i}\pmod {2333} \]思路
这种模数小的组合数计数问题可以考虑 Lucas 定理，试试呗。
如果按余数分类不好优化，可以按商分类求和，这样一来套个前缀和可以得到一个递推式，注意最后一块商可能是不整的，单独拿出来即可。
递推式很明显最多有 \(O(\log_pn)\) 次递归，但是每次都要套 Lucas 算组合数，所以最后是 \(O(\log_p^2n)\) 的。
// Problem: P4345 [SHOI2015] 超能粒子炮·改
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-01-18 23:07:31
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int N = 2e5 + 10, mod = 2333, M = mod + 5;
int com[M][M];
int lucas(int n, int m) {
if(m < 0) return 0;
if(n < mod) return com[n][m];
return lucas(n / mod, m / mod) * com[n % mod][m % mod] % mod;
}
int s[M][M];
int f(int n, int k) {
if(k <= 0) return (k == 0);
if(n < mod) return s[n][min(n, k)];
int ans = f(n / mod, k / mod - 1) * f(n % mod, mod - 1) % mod + lucas(n / mod, k / mod) * f(n % mod, k % mod) % mod;
return ans % mod;
}
void work() {
int n, k;
cin >> n >> k;
cout << f(n, k) << '\n';
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
com[0][0] = 1;
for(int i = 1; i < M; i ++) {
com[i][0] = 1;
for(int j = 1; j <= i; j ++)
com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]) % mod;
}
s[0][0] = 1; // 没管这个 WA 了好多发
for(int i = 1; i < M; i ++) {
s[i][0] = 1;
for(int j = 1; j <= i; j ++)
s[i][j] = (s[i][j - 1] + com[i][j]) % mod;
}
while (T--) work();
return 0;
}