「校内模拟20201118C」张士超你到底把我家钥匙放在哪了？

有 $m$ 个随机数生成器，每一个生成器会在 $[0,a_i] \cap \mathbb N^*$ 中均匀随机得到 $x_i$，再会有 $p_i$ 的概率令 $y_i=1$，否则 $y_i=0$ 。另外会有一个常数 $d$，保证 $d|(a_i+1)$。

考虑 $s_0=\sum_{i=1}^n x_iy_i,\ s_1 = \sum_{i=1}^n x_i$，对于一种局面，若 $s_1 =n$，则称其是合法的；对于一种合法的局面，若 $s_0 \geq l$，则称其是好的。求得到好的情况的概率。

对 $998244353$ 取模，且你只需要输出答案乘合法方案数的结果。

$1 \leq m \leq 100,\ 1 \leq l \leq n \leq \sum a_i,\ 1 \leq n ,a_i \leq 10^9,\ 1 \leq d \leq 10^7$，保证 $n \leq 100d$。

题解（个人做法）

考虑 $x_i = b_id + c_i$，我们通过 DP 统计 $db_i$ 的贡献，这样就把问题转换为了所有 $a_i = d-1$ 的情况，且我们已经知道其中 $k$ 个位置 $y_i=1$，其余 $m-k$ 个位置 $y_i=0$，且可以得到新的限制下的 $l$ 和 $n$。

考虑生成函数来统计合法但不好的方案数：

$$\sum_{i=0}^{t} [x^iy^n] \left(\sum_{i=0}^\infty (xy)^i \right)^k \left( \sum_{i=0}^\infty y^i \right)^{m-k}$$

推导一下生成函数

$$[x^ty^n] \frac {(1-y^d)^{m-k} (1-(xy)^d)^{k}} {(1-x) (1-y)^{m-k} (1-xy)^k}$$

将上半部分用二项式定理展开，并 $O(m^2)$ 的复杂度暴力枚举：

$$\sum_{i=0}^{m-k}\binom{m-k}{i}(-1)^i\sum_{j=0}^k\binom{k}{j}(-1)^j[x^{t-dj}y^{n-di-dj}] \left({(1-x) (1-y)^{m-k} (1-xy)^k}\right)^{-1}$$

即我们需要快速计算形如

$$[x^ay^b] \left({(1-x) (1-y)^{m-k} (1-xy)^k}\right)^{-1}$$

的表达式的值。

转换为格路问题，枚举 $(1-x)$ 的贡献，可以得到

$$\sum_{i=0}^a \binom{a\!-\!i+k\!-\!1}{k\!-\!1} \binom{b\!-\!a\!+\!i+m\!-\!k\!-\!1}{m\!-\!k\!-\!1}$$

注意到这是一个关于 $a$ 的多项式，我们可以暴力插值解决。