SHOI2015 超能粒子炮·改

Lucas定理

---

推一下柿子

$$\begin{align} f(n,k)&=\sum\limits_{i=0}^k \binom{n}{i} \bmod p \\ &=\sum\limits_{i=0}^k \binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{i}{p}\rfloor} \binom{n\bmod p}{i \bmod p} \bmod p \\ &=\sum\limits_{i=0}^{\lfloor \frac{k}{p} \rfloor} \binom{\lfloor \frac{n}{p} \rfloor}{i} \sum\limits_{j=0}^{\min\{p-1,k-pi\}} \binom{n \bmod p}{j} \bmod p \\ &=\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor \frac{k}{p} \rfloor} \sum\limits_{j=0}^{k\bmod p} \binom{n\bmod p}{j}+\sum\limits_{i=0}^{\lfloor \frac{k}{p} \rfloor - 1}\binom{\lfloor \frac{n}{p} \rfloor}{i} \sum\limits_{j=0}^{p-1} \binom{n\bmod p}{j} \bmod p \\ &=\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor \frac{k}{p} \rfloor} f(n\bmod p, k\bmod p) + f(\lfloor \frac{n}{p} \rfloor,\lfloor \frac{k}{p}\rfloor - 1) 2^{n\bmod p} \end{align}$$

然后把能预处理的预处理出来，其他的递归计算就行了。

#include <iostream>
#include <cstdio>
typedef long long LL;
#define int LL
const int P = 2333;
int c[2334][2334], f[2334][2334], pow[2334];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
int C(int n, int k) {
  if (n < k) return 0;
  if (n <= P) return c[n][k];
  return C(n / P, k / P) * c[n % P][k % P] % P;
}
int F(int n, int k) {
  if (k < 0) return 0;
  if (n <= P) return f[n][std::min(n, k)];
  return ((F(n / P, k / P - 1) * pow[n % P]) % P + (C(n / P, k / P) * f[n % P][k % P]) % P) % P;
}
signed main() {
  c[0][0] = 1;
  for (int i = 1; i <= P; ++i) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; ++j) {
      c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
      if (c[i][j] >= P) c[i][j] -= P;
    }
  }
  pow[0] = 1;
  for (int i = 1; i <= P; ++i) pow[i] = (pow[i - 1] << 1) % P;
  for (int i = 0; i <= P; ++i) {
    f[i][0] = 1;
    for (int j = 1; j <= P; ++j) {
      f[i][j] = f[i][j - 1] + c[i][j];
      if (f[i][j] >= P) f[i][j] -= P;
    }
  }
  int T = read();
  while (T--) {
    int n = read(), k = read();
    printf("%lld\n", F(n, k));
  }
  return 0;
}