【题解】P7481 推柿子时刻
_l_l_
·
·
题解
给定 n，对所有 1\leq a,b\leq m，求：
f(a,b)=\sum\binom bi\binom{n-i}a
显然很难 $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!}$ 计算。
```cpp
#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;
}
```