自动搬运

查看原文

来自洛谷，原作者为

	l_l *　*

搬运于2025-08-24 22:30:18，当前版本为作者最后更新于2023-05-01 13:22:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

给定 $n$，对所有 $1\leq a,b\leq m$，求：

$$f(a,b)=\sum\binom bi\binom{n-i}a$$

$n\leq10^9,m\leq5\times10^3$。

显然很难 $O(1)$ 在线求出每个 $f$ 的值，因此考虑递推。

首先看到上面有个常数项 $b$，考虑将其拆开：

$$\begin{aligned} f(a,b)=&\sum\binom bi\binom{n-i}a\\ =&\sum\binom{b-1}i\binom{n-i}a+\sum\binom{b-1}{i-1}\binom{n-i}a\\ =&f(a,b-1)+\sum\binom{b-1}{i}\binom{n-i-1}a\\ \end{aligned} $$

可以看见我们莫名其妙的把 $n-i$ 变为了 $n-i-1$，考虑变回去：

$$\begin{aligned} &\sum\binom{b-1}{i}\binom{n-i-1}a\\ =&\sum\binom{b-1}{i}\binom{n-i}a-\sum\binom{b-1}{i}\binom{n-i-1}{a-1}\\ =&f(a,b-1)-\sum\binom{b-1}{i}\binom{n-i-1}{a-1}\\ \end{aligned} $$

无论怎么变，都无法将 $n-i-1$ 变没，但是我们已经把右下角 $a$ 变为 $a-1$，这是个突破性的进展（确信），因此考虑将 $\sum\binom{b-1}{i}\binom{n-i-1}{a-1}$ 左下方的 $i$ 变为 $i+1$：

$$\begin{aligned} &\sum\binom{b-1}{i}\binom{n-i-1}{a-1}\\ =&\sum\binom b{i+1}\binom{n-i-1}{a-1}-\sum\binom {b-1}{i+1}\binom{n-i-1}{a-1}\\ =&\sum\binom bi\binom{n-i}{a-1}-\sum\binom {b-1}i\binom{n-i}{a-1}\\ =&f(a-1,b)-f(a-1,b-1) \end{aligned} $$

然后就推完了，总结下就是：

$$\begin{aligned} f(a,b)=&2f(a,b-1)-(f(a-1,b)-f(a-1,b-1))\\ =&2f(a,b-1)+f(a-1,b-1)-f(a-1,b) \end{aligned}$$

边界就 $f(a,0)=\binom na$，$f(0,b)=\sum\binom bi=2^b$。

$\binom na$ 可以直接使用 $O(a+\log \text{mod})$ 的公式 $\frac{n\times(n-1)\times\cdots\times(n-a+1)}{a!}$ 计算。

#include <cstdio>
using namespace std;
const int MAXN = 5005;
const int mod = 998244353;
int f[MAXN][MAXN];
int qkpow(int a, int b) {
    int ans = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ans = 1ll * ans * a % mod; return ans;
}
int main() {
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 0; i <= m; i++) {
        int ans1 = 1, ans2 = 1;
        for (int j = n - i + 1; j <= n; j++) ans1 = 1ll * ans1 * j % mod;
        for (int j = 1; j <= i; j++) ans2 = 1ll * ans2 * j % mod;
        f[i][0] = 1ll * ans1 * qkpow(ans2, mod - 2) % mod;
    }
    for (int i = 0; i <= m; i++) f[0][i] = qkpow(2, i);
    for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) {
        f[i][j] = (2ll * f[i][j - 1] + f[i - 1][j - 1] + mod - f[i - 1][j]) % mod;
    }
    int ans = 0; for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) {
        ans ^= f[i][j];
    }
    printf("%d\n", ans); return 0;
}