题解：AT_ndpc2026_j 個数と総和

_jimmywang_ · 2026-05-09 13:58:00 · 题解

写出 GF，题目等价于求求 [x^Sy^T]\prod\frac{1}{1-xy^{A_i}}=\frac{P(x,y)}{Q(x,y)}。二元远处求值，直接先 x 再 y 做一元 BM 是错的，另一个变量的指数会爆炸。

但是你考虑 BM 在干啥，一元 BM 是上下同乘 Q(-x) 使得分母只有偶次项。这题分母有特殊结构，能不能利用一下呢？

能的。上下同乘上 \prod(1+xy^{A_i})，分母就变成 \prod(1-x^2y^{2A_i})，然后就能做到 S,T 都除以 2。做到全除成 0 即可。

进一步的，我们发现 Q 的系数在迭代过程中不变，因此只需要维护 P(x,y) 即可。

其实这个和做一个二进制数位 dp 是等价的：f_{i,j,k} 表示 i 以下低位全部确定和 S,T 相等，当前位（给下一位进位前）在 S 和 T 两个维度上分别有 j,k 个 1，然后枚举本位的取法（比如 j 加上 s，k 加上 t）转移。转移系数等价于上面方法的 [x^sy^t]\prod(1+xy^{A_i})。