官方题解只能做到 $O(S(N + M))$？玩的太差了。令 $g=\gcd(A_1,\ldots,A_N)$，$a_i=A_i/g$，$S=\sum_i a_i$，$V=\max_i a_i$，$d=\min(S,M)$。这题可以做到确定性的时间复杂度
$$ O\!\left(N+M+S\log(V+d+1)+M\log^2(d+1)\right), $$
空间复杂度为 $O(S+M+d\log(d+1))$。这里将题目的固定模数视为常数。
不仅能去掉普通容斥背包中的 $NS$、逐个处理其他评论时的 $MS$，还可以利用 $A_i\le 100$ 的限制，把生成函数计算中的 $\log S$ 换成 $\log V$。题目对 $B_i$ 没有类似的小值域限制，因此不能开一个覆盖所有 $B_i$ 的数组。([QOJ][1])
从随机删除到一个多项式内积
先把所有权值除以 $g$，自己的权值变成整数 $a_i$，其他评论的权值变成有理数 $b_j=B_j/g$。同时缩放所有权值不会改变删除顺序的分布；实现时，$b_j$ 用 $B_jg^{-1}\bmod p$ 表示。
给每条权值为 $w$ 的评论分配一个独立的指数随机变量，速率为 $w$，然后按这些随机变量从小到大删除评论。最小值属于某条评论的概率恰好是其权值占总权值的比例；由指数分布的无记忆性，删除第一条后，剩余部分仍具有相同性质。因此，这与原过程完全等价。
设自己的评论对应的随机变量为 $T_1,\ldots,T_N$，最后一条自己的评论被删除的时刻为 $T=\max_i T_i$。自己的 $N$ 条评论一定会被删除，所以答案等于 $N$ 加上其他评论在 $T$ 之前被删除的期望数量。
定义 $P(x)=\prod_{i=1}^N(1-x^{a_i})=\sum_{s=0}^S c_sx^s$。对于一条速率为 $b$ 的其他评论，它比自己的全部评论都晚被删除的概率为 $L(b)=\int_0^\infty be^{-bt}\prod_i(1-e^{-a_it}),dt =b\int_0^1x^{b-1}P(x),dx =b\sum_{s=0}^S c_s/(b+s)$。
因此，答案是 $N+M-\sum_jL(b_j)$。直接用背包求出带符号子集和分布 $c_s$，再逐个处理 $b_j$，仍然需要 $O((N+M)S)$ 次运算；公开题解也从这个带符号子集和分布出发。([QOJ][2])
关键是把所有其他评论合并处理。定义 $Q(x)=\prod_{j=1}^M(x+b_j)$，则 $Q'(x)/Q(x)=\sum_j1/(x+b_j)$，从而 $\sum_jb_j/(s+b_j)=M-sQ'(s)/Q(s)$。
又因为 $N\ge1$，有 $\sum_s c_s=P(1)=0$，于是答案化为
$$ \boxed{\operatorname{Ans}=N+M+\sum_{s=1}^S s\,c_s\,\frac{Q'(s)}{Q(s)}}. $$
接下来只需要快速生成 $c_s$，以及同时求出连续整数点上的 $Q(s)$ 和 $Q'(s)$。
这些除法都合法。对于 $0\le s\le S$，有 $g(b_j+s)=B_j+gs$，而 $1\le B_j+gs\le B_j+\sum_iA_i< p$；因此每个 $Q(s)$ 都非零。题面给出的总权值小于模数的条件，正好保证了这一点。([QOJ][1])
把两个多项式步骤都做到近线性
先考虑生成 $P$ 的全部系数。
设权值 $a$ 的出现次数为 $m_a$。由 $\log P(x)=\sum_a m_a\log(1-x^a)$，得到 $[x^k]\log P(x)=-\frac1k\sum_{a\mid k}a m_a$。前 $L$ 项可以通过枚举倍数在 $O(L\log(V+1))$ 时间内求出，再做一次形式幂级数指数，需要 $O(L\log(L+1))$ 时间。
直接取 $L=S$ 已经可以得到 $O(S\log S)$，但还可以进一步优化。
令 $C(x)=\prod_{a:m_a>0}(1-x^a)$，注意每种不同权值只出现一次。记 $D=\deg C=\sum_{a:m_a>0}a$，则 $D\le \min(S,V(V+1)/2)$。再令 $H(x)=-\sum_{a:m_a>0}a m_a x^{a-1}C(x)/(1-x^a)$，便有 $\deg H< D$，以及微分方程 $CP'=HP$。
这个方程只涉及次数为 $O(D)$ 的多项式，可以让我们每次生成 $D$ 个新系数，而不必把整个长度为 $S$ 的多项式反复送进 NTT。
首先用普通幂级数算法求出 $P_0=P\bmod x^D$，并预处理 $J=(CP_0)^{-1}\bmod x^D$。$C$ 可以通过将上述对数公式中的非零 $m_a$ 改为 $1$ 得到，$H$ 则由 $C(\log P)'$ 的前 $D$ 项得到。这些预处理一共需要 $O(D\log(D+1))$ 时间。
现在假设已经知道 $F=P\bmod x^n$，其中 $n\ge D$，希望再求出 $\ell\le D$ 项。写成 $P=F+x^nY\bmod x^{n+\ell}$，代入微分方程，得到 $C(nY+xY')-xHY=E$，其中 $E=(HF-CF')/x^{n-1}\bmod x^\ell$。
令 $Y=PZ$，利用 $CP'=HP$，方程立即简化为 $nZ+xZ'=E/(CP)$。因此，若定义 $\mathcal D_n(\sum_k u_kx^k)=\sum_k u_k(n+k)^{-1}x^k$，这一块的答案就是
$$ Y=P_0\cdot\mathcal D_n(EJ)\pmod{x^\ell}. $$
右侧只用到了 $P$ 的前 $D$ 项，它们已经预处理完成，不存在循环依赖。
还有一个重要的实现细节：计算 $E$ 时，只需要 $F$ 最后的 $D$ 个系数。这是因为 $\deg C=D$、$\deg H< D$，而我们只取 $HF-CF'$ 中从 $x^{n-1}$ 开始的 $\ell$ 项。因此，每一块只需要常数次长度为 $O(D)$ 的卷积，复杂度为 $O(D\log(D+1))$。
总共处理 $O(S/D)$ 块，生成全部 $c_s$ 的复杂度便是 $O(S\log(D+1))=O(S\log(V+1))$。
代码在 $S\le4D$ 时直接做一次幂级数指数，此时 $\log S=O(\log(D+1))$，不影响复杂度。当所有原始 $A_i$ 相等时，约掉公因数后 $P=(1-x)^N$，直接用二项式系数即可。
再考虑同时计算所有 $Q(s)$ 和 $Q'(s)$。
取 $d=\min(S,M)$，建立 $W(x)=\prod_{k=0}^d(x-k)$。我们不一定需要完整的 $Q$，只计算 $R=Q\bmod W^2$。
这里必须模 $W^2$，不能只模 $W$：由 $Q-R=W^2K$ 可知，对于 $k=0,\ldots,d$，同时有 $Q(k)=R(k)$ 和 $Q'(k)=R'(k)$。只模 $W$ 后直接对余式求导，并不能保证后一条成立。
用乘积树计算 $\prod_j(x+b_j)$，在每个节点对 $W^2$ 取模，就能把所有中间多项式的次数限制在 $O(d)$。次数尚未达到限制的低层一共花费 $O(M\log^2(d+1))$；达到限制后的高层，节点数量等比减少，总工作量为 $O(M\log(d+1))$，不会额外留下一个 $\log M$。
然后用多点求值求出 $R,R'$ 在 $0,\ldots,d$ 上的值，需要 $O(d\log^2(d+1))$，这一项已经包含在前面的界内。
当 $M>S$ 时，$d=S$，所有需要的值已经得到。当 $M\le S$ 时，$d=M$，而且 $R$ 就是完整的 $Q$，接下来利用连续整数点的结构扩展求值范围。
对于任意次数不超过 $d$ 的多项式 $F$，已知 $F(0),\ldots,F(d)$，令 $t_i=\sum_{j=0}^i\frac{F(j)}{j!}\frac{(-1)^{i-j}}{(i-j)!}$。 这正好是 $\Delta^iF(0)/i!$，可以用一次卷积计算。
根据牛顿插值公式，对所有 $0\le k\le S$，有 $F(k)=k!\sum_{i=0}^{\min(k,d)}t_i/(k-i)!$。 所以再做一次卷积，就可以得到全部连续点的值。
第二次卷积的两个长度分别为 $O(d)$ 和 $O(S)$。不能直接对总长度做一次大 NTT，然后把复杂度写成 $O(S\log d)$。 正确做法是把长多项式分成长度为 $O(d)$ 的块，复用短多项式的变换结果，分别卷积并累加。这样才真正得到 $O(S\log(d+1))$。下面的乘法实现包含了这个长短卷积优化。
最后对 $Q(1),\ldots,Q(S)$ 使用前缀积批量求逆，只需一次快速幂和 $O(S)$ 次乘法，就能计算答案中的内积。
因此，两部分的复杂度分别为 $O(S\log(V+1))$ 和 $O(M\log^2(d+1)+S\log(d+1))$，合并即得到开头的界。在 $A_i$ 有固定小上界的条件下，这是关于输入规模的近线性算法，而不再含有 $NS$ 或 $MS$ 这样的乘积项。