[题解] P7481
rits_m
·
·
题解
注意到先 \bmod 998244353 再 \oplus 一眼的没有高妙算法，所以看样子要求出所有 F 了。也就是说：
题意：求所有 1 \leq a, b \leq m 的：
F(a,b)=\sum_{i=0}^{b} \binom{b}{i}\binom{n - i}{a}
**题解**：看到乘积，第一眼不能范德蒙德。那我们考虑一下组合数递推，感觉和 [这个](https://www.luogu.com.cn/problem/solution/P9357) 有点像？
把第一个组合数用 **加法** 拆开：
$$F(a,b)=\sum_{i=0}^{b} \binom{b - 1}{i}\binom{n - i}{a} + \sum_{i=0}^{b} \binom{b - 1}{i - 1}\binom{n - i}{a}$$
对照上式的前半部分和 $F$ 的定义：
$$F(a, b) = F(a, b - 1) + \sum_{i=0}^{b} \binom{b - 1}{i - 1}\binom{n - i}{a}$$
后半部分是化不了的，因为我们搞出来一个 $i - 1$，如果你想要提到第二个组合数的上指标上，由于 $n$ 不是参量是常量，所以不能直接化成 $F$。
那么我们再次把组合数用 **减法** 拆开，为了让第一个组合数的下指标和第二个组合数的上指标形式相同。
但是这里拆开第一个组合数会很尴尬：
$$F(a, b) = F(a, b - 1) + \sum_{i=0}^{b} \binom{b}{i}\binom{n - i}{a} - \sum_{i=0}^{b} \binom{b - 1}{i}\binom{n - i}{a}$$
你得到了 $F(a, b) = F(a, b - 1) + F(a, b) - F(a, b - 1)$，等于废话。
$$F(a, b) = F(a, b - 1) + \sum_{i=0}^{b} \binom{b - 1}{i - 1}\binom{n - i}{a}$$
所以拆开第二个组合数：
$$F(a, b) = F(a, b - 1) + \sum_{i=0}^{b} \binom{b - 1}{i - 1}\binom{n - (i - 1)}{a} - \sum_{i=0}^{b} \binom{b - 1}{i - 1}\binom{n - i}{a - 1}$$
也即：
$$F(a, b) = F(a, b - 1) + \sum_{i=0}^{b - 1} \binom{b - 1}{i}\binom{n - i}{a} - \sum_{i=0}^{b} \binom{b - 1}{i - 1}\binom{n - i}{a - 1}$$
$$F(a, b) = 2F(a, b - 1) - \sum_{i=0}^{b} \binom{b - 1}{i - 1}\binom{n - i}{a - 1}$$
虽然后面这个式子很尴尬，我们又回到了原来的起点，但是 **对照一下一开始的式子**：
$$F(a, b) - F(a, b - 1) = \sum_{i=0}^{b} \binom{b - 1}{i - 1}\binom{n - i}{a}$$
所以有：
$$F(a, b) = 2F(a, b - 1) - F(a - 1, b) + F(a - 1, b - 1)$$
我们要 $a, b$ 均从小到大递推，这只需要我们知道边界情况：$\forall 1 \leq b \leq m$ 的 $F(0, b)$ 和 $\forall 1 \leq a \leq m$ 的 $F(a, 0)$ 以及 $F(0, 0) = 1$。
虽然只有 $\mathcal O(m)$ 个点值，暴力带定义算一下处理的好是可以单次 $\mathcal O(m)$ 的，但是事实上直接带回去，可以得到
$$F(a, 0)= \binom{n}{a}$$
$$F(0, b)= 2^b$$
所以最后复杂度就严格 $\mathcal O(m^2)$ 了。
**代码**：随手写了个最优解 rk3。
```cpp
#include <cstdio>
const int MOD = 998244353;
inline void add(int& x, int y) { (x += y) >= MOD && (x -= MOD); }
inline void del(int& x, int y) { (x -= y) < 0 && (x += MOD); }
inline int sum(int x, int y) { return (x += y) < MOD ? x : x - MOD; }
inline int mun(int x, int y) { return (x -= y) >= 0 ? x : x + MOD; }
#define MAXM 5001
int inv[MAXM], F[MAXM][MAXM];
int main() {
int N, M; scanf("%d%d", &N, &M);
inv[1] = 1;
for (int i = 2; i <= M; ++i)
inv[i] = MOD - (long long)(MOD / i) * inv[MOD % i] % MOD;
F[0][0] = 1;
for (int a = 1; a <= M; ++a)
F[a][0] = (long long)F[a - 1][0] * (N - a + 1) % MOD * inv[a] % MOD;
for (int b = 1; b <= M; ++b)
F[0][b] = sum(F[0][b - 1], F[0][b - 1]);
int ans = 0;
for (int a = 1; a <= M; ++a) for (int b = 1; b <= M; ++b)
ans ^= (F[a][b] = sum(sum(F[a][b - 1], F[a][b - 1]), mun(F[a - 1][b - 1], F[a - 1][b])));
// for (int a = 0; a <= M; ++a) for (int b = 0; b <= M; ++b)
// printf("%d%c", F[a][b], " \n"[b == M]);
return printf("%d\n", ans), 0;
}
```