题目来源：AIsing Programming Contest 2020 F – Two Snuke

已知：$s_2>s_1,n_2>n_1,u_2>u_1,k_2>k_1,e_2>e_1$ 且均为非负整数，计算：

$$\begin{aligned} \sum_{s_1 + s_2 + n_1 + n_2 + u_1 + u_2 + k_1 + k_2 + e_1 + e_2 \leq N}(s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 – k_1)(e_2 – e_1) \end{aligned}$$

$N\leq 10^9$ 。

构造多项式 $f=\sum_{s_2>s_1\geq 0}(s_2-s_1)$ ，那么本题的答案显然就是 $\sum_{i=0}^N [x^i] f^5$ 。但是这个式子无法在 $N=10^9$ 的数据范围下求解，因此我们还需要进行一些变形。

首先我们发现，多项式 $f$ 的各项系数计算是一个 $O (N^2)$ 的式子，最好能够将其转化为封闭形式的生成函数。打个表不难发现闭式为 $\frac {x}{(1-x)^3 (1+x)}$ 。

因此本题答案就是：

由于我们需要求 $x^0,x^1,x^2,\ldots,x^N$ 的系数之和，因此不妨转化为 $[x^N]\frac {f^5}{1-x}$ ，这是因为 $\frac {1}{1-x}$ 的展开式就是 $1+x+x^2+\cdots$ ，于是本题就转化为了一个多项式的远点求值：

由于 $N$ 很大，该式仍然无法在规定时间内解出，但是这类由有理分式构成的多项式闭式，他的各项系数必然有线性递推公式，因此采用 Berlekamp Massey 算法暴力找到递推式，然后通过特征多项式线性递推求解（当然也可以矩阵快速幂），时间复杂度 $O (k^2+k^2\log N)$ ，其中 $k$ 是递推数列的元素个数。

AC 代码。