记 $a_{1,2,3,4}$ 表示输入的 $a,b,c,d$。

$$ P_k(x)=\sum_{j=0}^k\frac{x^j}{j!} $$

那么根据对相邻四个的容斥，我们不难得到答案可表述为如下求和：

$$ \sum_{k=0}^{\min(\min \{a_i\}, \lfloor n/4\rfloor)} \frac{(n-3k)!}{k!}[x^{n-4k}]\prod_{i=1}^4 P_{a_i-k}(x) $$

首先我们考虑 $\prod P_{a_i-k}$ 这个东西如何直接计算，考虑微分方程可得：

$$ P_k(x)'=P_k(x)-\frac{x^k}{k!} $$

记 $\Pi_S(x) = \prod_{i\in S} P_{a_i-k}(x)$，那么求导可得

$$ \begin{aligned} \Pi_S(x)' &= \Pi_S(x) \cdot \sum_{i\in S} \frac{P'_{a_i-k}(x)}{P_{a_i-k}(x)}\\ &= \Pi_S(x) \cdot \sum_{i\in S} \frac{P_{a_i-k}(x)-\dfrac{x^{a_i-k}}{(a_i-k)!}}{P_{a_i-k}(x)}\\ &= |S|\Pi_{S}(x) - \sum_{i\in S}\frac{x^{a_i-k}}{(a_i-k)!}\cdot \Pi_{S\backslash \{i\}}(x) \end{aligned} $$

寻此微分方程，我们可以在 $\Theta(n)$ 时间内完成乘积的计算。

然后我们不妨考虑分块，我们注意上述过程中已经算出了所有子集，不妨考虑计算 $\prod(A_i -B_i)$，令 $A_i=P_{a_i-r},B_i=P_{a_i-r}-P_{a_i-l}$，那么 $B_i$ 的所有子集乘积可以在 $\Theta(r-l)$ 的时间内维护出，因为有值项只是这么长的一段区间，其微分方程类似。因此如果我们每 $S$ 个 $l$ 重构一次 $A$，那么复杂度即为 $\Theta(n\cdot \frac nS + S\cdot n) \ge \Theta(n^{3/2})$。

更精细地分析，如果认为总共有 $K$ 项（本题中 $K=4$），那么复杂度为 $\Theta(K2^Kn \cdot \frac nS + K^22^KS\cdot n) \ge \Theta((nK)^{3/2}2^K)$。