组合数问题题解

思路推导

模数 $998244353$ 是质数，并且所有 $n$ 都小于模数。利用 $\binom{n}{m}=\dfrac{n!}{m!(n-m)!}$，可以先处理阶乘与逆阶乘，再常数时间回答每次询问。

做法

先线性计算 $0!$ 到 $N!$。由费马小定理求出 $N!$ 的逆元，然后倒序递推得到全部逆阶乘。每次询问把对应的阶乘和两个逆阶乘相乘并取模，再将结果累积到异或和中。

小规模时也可以枚举子集计数，或按帕斯卡恒等式逐行递推。若所有询问中较小一侧的总和较小，则可逐项计算分子、分母并求逆元。

正确性证明

由于 $N<998244353$，$1,2,\ldots,N$ 在模意义下均可逆，因此预处理得到的逆阶乘均合法。对任意询问，阶乘公式恰好等于二项式系数，模运算保持乘法与除以可逆元的结果。程序逐个得到所有询问的正确答案，并按题意进行按位异或，所以最终输出正确。

复杂度分析

预处理时间复杂度为 $O(N)$，每次询问为 $O(1)$，总时间复杂度为 $O(N+T)$；空间复杂度为 $O(N)$。