Sol
考虑多项式乘法的组合意义，枚举第$i$项被选的次数$b_i$，要求$\sum b_i = m, \sum b_i i = k$，则对应的贡献为
如果$p \mid m$，我们对上面的式子应用Lucas定理，发现：
- 若$p \nmid b_0$则第一项一定为$0$，要使整个式子不为$0$就一定要有$p \mid b_0$
- 于是有$p \mid m - b_0$，于是可以推出$p\mid b_1$
- ……
也就是说，所有的$b_i$都是$p$的倍数。
令
那么就可以把此时的答案写成
这个$B^{\frac{m}{p}}(x)$的意义相当于让原来的$b_i$和$m$都除以$p$，不会影响系数的计算。
考虑到$a_i^p \equiv a_i \pmod p$，所以答案也可以写成
更一般的，对于任意的$m$，设$m = up + v(0\le v < p)$，则有
$[x^{k-i}]A^{up}(x)$直接递归，$[x^i]A^v(x)$可以通过预处理$A(x)$的$0$到$p-1$次幂解决。要对访问到过的状态进行记忆化。
因为当$p\nmid i-k$时$[x^{k-i}]A^{up}(x) = 0$，所以只需要枚举和$k$同余的$i$，这样的$i$会有$\frac{vn}{p} \le n$个。
考虑复杂度：
- 每一次往下递归$m$会变成$\lfloor \frac{m}{p} \rfloor$，$k$会变成$\lfloor \frac{k}{p}\rfloor - i’$，$i’$的范围是$0,lim$；
- 每一层的$m$都是一样的，所以只用考虑$k$会有多少种不同的取值；
- 对于第$i$层，$k$能取到的最大值是$\frac{k}{p^{i-1}}$，最小值则不小于$\frac{\frac{\frac{k}{p}-n}{p}-n}{p}\cdots \approx O(\frac{k}{p^{i-1}} - n \cdot {1\over p-1})$，所以每一层不同的$k$的数量至多是$O(n)$的；
- 状态数$O(n\log_pm)$，转移$O(n)$，所以这里的复杂度是$O(Tn^2\log_p m)$，算上预处理的复杂度就是$O(p^2n^2 + Tn^2\log_p m)$