题目大意

给定三个长度为 $n$ 的数字字符串 $a, b, c$（可能包含前导零），将它们按列排列。我们可以重新排列这些列的顺序，得到三个新的数字 $x, y, z$，要求：

1. $x + y = z$ 在数值上成立
2. $x, y, z$ 都没有前导零

求满足条件的列排列方案数，对 $10^9+7$ 取模。

解题思路

关键观察

1. 进位分析：对于每一列 $(a_i, b_i, c_i)$，需要考虑是否产生进位和是否需要进位

2. 列分类：根据进位关系，可以将所有列分为四种类型：

   • 类型 0-0：不进位，不被进位
   • 类型 0-1：不进位，但被进位
   • 类型 1-0：产生进位，不被进位
   • 类型 1-1：产生进位，且被进位

3. 必要条件：产生进位的列数必须等于被进位的列数，否则无解

算法步骤

1. 预处理：计算阶乘和逆元阶乘，用于组合数计算

2. 列分类统计：

   • 遍历每一列，判断其属于哪种类型
   • 同时记录该列是否包含数字0（影响前导零约束）

3. 可行性检查：

   • 检查进位平衡条件：产生进位的列数 = 被进位的列数
   • 如果不满足，直接输出0

4. 组合计数：

   • 考虑两种起始情况：以类型0-0的列开始或以类型0-1/1-0的列开始
   • 使用组合数学方法计算合法的排列方案数：
     • 处理相同列的去重（多重集排列）
     • 确保第一列不包含任何0（满足无前导零条件）
     • 维护进位关系的连续性

复杂度分析

• 时间复杂度：$O(n)$，主要开销在遍历列和组合数计算
• 空间复杂度：$O(n)$，用于存储阶乘数组和统计信息

总结

本题是一道结合了数位分析、进位处理和组合计数的综合题目。关键在于将复杂的加法进位条件转化为列的分类和排列问题，然后通过组合数学方法统计合法方案数。算法在保证正确性的同时，也处理了大数据范围下的效率问题。