设两个生成函数：

$$ A(z)=\sum_{i=0}\binom{i+a}{a}(xz)^i=\frac{1}{(1-xz)^{a+1}} $$

$$ B(z)=\sum_{i=0}\binom{i+b}{b}(yz)^i=\frac{1}{(1-yz)^{b+1}} $$

那么：

$$ f_{n,x,y}(a,b)=[z^{n-a-b}]A(z)\cdot B(z)=[z^{n-a-b}]\frac{1}{(1-xz)^{a+1}(1-yz)^{b+1}} $$

当 $x=y$ 时，式子被简化为：

$$ [z^{n-a-b}]\frac{1}{(1-xz)^{a+b+2}}=\binom{(n-a-b)+(a+b+2-1)}{a+b+2-1}x^{n-a-b}=\binom{n+1}{a+b+1}x^{n-a-b} $$

只需要预处理 $C_i=\binom{n+1}{i}$，即可快速回答函数的值。这里的 $i\le \max a+\max b+1$，预处理它时间非常充足。

当 $x\neq y$ 时，令 $G_{a,b}(z)=\frac{1}{(1-xz)^{a+1}(1-yz)^{b+1}}$，简写为 $G(z)$。同理，下文中的 $f_{n,x,y}(a,b)$ 也被简写为 $f(a,b)$。

利用 $\frac{1}{a}-\frac{1}{b}=\frac{b-a}{ab}$ 的思想，可以构造出如下式子：

$$ \frac{1}{(1-xz)^{a+1}(1-yz)^{b}}-\frac{1}{(1-xz)^{a}(1-yz)^{b+1}}=\frac{(1-yz)-(1-xz)}{(1-xz)^{a+1}(1-yz)^{b+1}}=\frac{(x-y)z}{(1-xz)^{a+1}(1-yz)^{b+1}} $$

即：

$$ G(a,b-1)-G(a-1,b)=(x-y)\cdot z\cdot G(a,b) $$

两边同时提取 $z^{n-a-b+1}$ 的系数，得到：

$$ f(a,b)=\frac{f(a,b-1)-f(a-1,b)}{(x-y)} $$

可以递推求解。接下来需要考虑边界情况。

当 $a=b=0$ 时，$f(0,0)=\sum_{i=0}^n x^iy^{n-i}$，容易用等比数列求和相关知识得到结果为 $\frac{x^{n+1}-y^{n+1}}{x-y}$。

当 $a=0$ 或 $b=0$ 时，以 $b=0$ 为例。由于 $G(a,-1)=\frac{1}{(1-xz)^{a+1}}$，其系数为 $\binom{n+1}{a}x^{n-a+1}$。预处理 $C_i$ 也可以快速计算 $\binom{n+1}{a}$。

所以也可以递推递推求得答案。

时间复杂度为 $O(\sum (\max a_i)(\max b_i))$。