发现题目将 $k$ 个数取平均数后合并成一个数的操作可以看作一棵 $k$ 叉树，每一个节点的儿子数都是 $0$ 或 $k$。

其中叶子节点是 $0$ 或 $1$ 表示给定的 $n+m$ 个数，而非叶子节点的值就是其儿子的平均值，代表在操作后新产生的点。

假设所有的叶子节点从左到右排列的值依次是 $a_1,a_2,\cdots ,a_{n+m}$，那么对于第 $i$ 个叶子节点其贡献可以写作 $\dfrac{a_i}{k^{dep(i)}}$，其中 $dep(i)$ 表示第 $i$ 个叶子节点的深度（$dep(rt)=0$）。所以在确定了 $a$ 数组之后，剩余平均值就是 $\sum\limits_{i=1}^n \dfrac{a_i}{k^{dep(i)}}$。

设 $d$ 为有 $n+m$ 个点的 $k$ 叉树的深度的最大值，容易得到 $d=\dfrac{n+m-1}{k-1}$。

因为对于 $\forall i\in[1,n+m]\cap\mathbb{N}$ 满足 $k^{dep(i)}\mid k^{d}$，所以答案答案一个可以写成 $\dfrac{S}{k^{d}}$ 的形式，其中 $S$ 是一个整数。

发现直接统计答案会有重复，因为如果第 $x$ 层有 $k$ 个 $1$，那么其贡献等于在 $x-1$ 层有 $1$ 个 $1$，考虑将这 $k$ 个 $1$ 合并上去。注意，这 $k$ 个 $1$ 的父亲不一定是相同的。

考虑对于所有一层出现的 $1$ 超过 $k$ 次的情况全部处理掉，假设处理了 $l$ 次，那么 $m'\gets m-l\times(k-1),d'\gets d-l$。

注意 $d'$ 表示的 $n+m'$ 个点可以组的 $k$ 叉树的最大深度，虽然可以构造出进行一次操作之后树的深度不减小的情况，但是这一定不是深度最深的情况。

如果将 $S$ 看作一个 $d$ 进制数，上面的操作就相当于给 $S$ 进行进位操作。

假设现在的答案可以写作 $\dfrac{S'}{k^{d'}}$，另 $v$ 将 $S'$ 写作 $d'$ 进制数之后各位的值的和，那么需要满足 $v=m'$，也就是满足 $v \equiv m \pmod{k-1}$。

考虑使用 DP 进行求解方案数，设 $f_{i,j}$ 表示一共 $i$ 层一共选择了 $j$ 个 $1$ 的方案数，模拟背包直接进行转移即可，时间复杂度为 $O(n^2)$。

Submission #58023415 - Japan Russia Exchange Programming Contest 2017