偶然看到的神秘题，感觉有点意思。

首先考虑式子的组合意义，可以理解为共有 $n$ 个球，可以从前 $b$ 个中选任意个涂白，再在剩下的球中选 $a$ 个涂黑的方案数。

考虑转而枚举前 $b$ 个球中涂黑的数量，得到

$f_{a,b}=\sum_{i=0}^b{2^{b-i}C_b^iC_{n-b}^{a-i}}$

注意到这个式子很能卷积，考虑将 $b$ 固定，设 $F_b(x)=\sum{f_{a,b}x^a}$，得到

$F_b=(2+x)^b(1+x)^{n-b}$

此时枚举 $b$ 并动态维护多项式已经可以做了，类似背包和退背包。时间复杂度 $O(m^2)$。

实际上可以直接推出 $f_{a,b}$ 的递推式。考虑

$F_b(x)'=b(2+x)^{b-1}(1+x)^{n-b}+(n-b)(2+x)^b(1+x)^{n-b-1}$

$\quad\quad\;\;\,=bF_{b-1}(x)\frac{1}{1+x}+(n-b)F_b(x)\frac{1}{1+x}$

于是

$(1+x)F_b(x)'=bF_{b-1}(x)+(n-b)F_b(x)$

提取系数即得

$(a+1)f_{a+1,b}+af_{a,b}=bf_{a,b-1}+(n-b)f_{a,b}$

整理一下

$f_{a+1,b}=\frac{1}{a+1}(bf_{a,b-1}+(n-a-b)f_{a,b})$

预处理逆元直接递推，时间复杂度 $O(m^2)$。

“超级无敌神仙炫酷无敌原神大王”豪华套餐特邀嘉宾。