下面记第 $i$ 列的前 $k-1$ 个数字之和为 $S_i$，第 $k$ 个数字为 $d_i$。

考虑竖式加法从低位到高位进行。

如果某一列右侧传来的进位是 $c$，左侧产生的进位是 $c'$，那么它必须满足 $S_i+c=d_i+10c'$，这是因为最多是 $k-1$ 个一位数相加，而 $k\le 6$，所以所有进位只可能是 $0,1,\ldots,k-2$。

于是每一列都可以看成一条进位状态的有向边 $c\to c'$，并且合法的 $c$ 至多只有一个；如果某一列找不到这样的 $c$，我们直接宣判无解

从最低位开始读列时，初始进位是 $0$；读完最高位后，最终进位也必须是 $0$。所以我们需要把所有边排列成一条从 $0$ 出发又回到 $0$ 的欧拉回路。

还需要注意最高位不能有前导零。若从低位到高位看，最高位对应的是这条欧拉回路的最后一条边。因此最后一条边必须是某条 $s\to 0$，并且这一列的 $k$ 个数字全部非零。

如果原图不存在欧拉回路（或者说，存在某个点入度不等于出度），显然无解。

下面固定最后一条边是某条 $s\to 0$ 的边。

删去“最后一步”的视角后，剩下的过程可以理解为从 $0$ 走到 $s$，并且用完其余所有边。考虑每个点最后一次离开它时走的边。

除了终点 $s$ 以外，每个有出边的点都必须选择一条“最后出边”。这些最后出边不能形成一个不经过 $s$ 的环，否则一旦走进这个环，就无法在最后离开环到达 $s$。因此它们必须形成一棵所有边都指向 $s$ 的有向树。

反过来，如果已经选好了这样一棵指向 $s$ 的有向树，那么对每个点，把不是最后出边的出边任意排序，最后再放上它的最后出边，就可以唯一地对应到一种合法走法。

接下来的部分怎么做都可以，你可以 BEST 定理，也可以直接搜索一下，反正图很小。

于是固定根 $s$ 时，贡献为

$$T_s\prod_v(\operatorname{out}(v)-1)!,$$

其中 $T_s$ 表示原图中指向 $s$ 的有向生成树数量，乘积只对有边的点计算。

若可以作为最高位的 $s\to 0$ 边共有 $\operatorname{good}_{s,0}$ 条，那么答案为

$$\left(\prod_v(\operatorname{out}(v)-1)!\right) \sum_s \operatorname{good}_{s,0}T_s.$$

这里所有边都是有编号的原始列，所以重边自然会被当作不同的边计数。

由于状态数最多只有 $5$，求 $T_s$ 的方法非常随意。

可以直接枚举每个非根点选择哪一条最后出边，检查是否都能走到根；也可以使用有向图矩阵树定理。若使用矩阵树定理，建立矩阵

$$L_{u,u}=\sum_{v\ne u}cnt_{u,v},\qquad L_{u,v}=-cnt_{u,v}\quad(u\ne v),$$

删去根 $s$ 对应的行和列，行列式就是 $T_s$。自环不会影响生成树，但会影响出边数量，所以仍然要计入阶乘部分。

---

本题的部分分围绕“列重排计数”的不同难点展开。最小数据保证 $n\le 8$，可以直接枚举所有列排列，检查加法等式和前导零限制。$k=3$ 的部分分降低了竖式加法中每一列的状态复杂度，选手可以先写出较简单的进位 DP。特殊性质 C 保证忽略前导零时至少存在一种合法重排，用于弱化无解判断的干扰。特殊性质 D 保证每一列都可以作为某种进位状态下的合法列，使得主要难点集中在排列计数本身。满分数据需要把每一列视为进位状态之间的有向边，并对这些边的排列方式进行整体计数。