算法思路分析

问题理解

  • 需要统计满足 A+B=C 且字符串总长度为 n 的不同算式数量
  • 核心约束：A、B、C 均无前导零（数值为0时长度为1）
  • 字符串格式：A的十进制 + + + B的十进制 + = + C的十进制
  • 总长度：len(A) + len(B) + len(C) + 2 = n

关键观察

  1. 复杂度瓶颈：n ≤ 20 看似很小，但若直接枚举 A 和 B（最大可达 10^20），计算量爆炸
  2. 突破口：C 的范围很小（C ≤ 200000，最多6位数），而 n 也很小（≤20）
  3. 逆向思维：先固定 A 的位数 i，则 B 的位数 j = n - i - len(C) - 2 直接确定
  4. 范围剪枝：对于特定的位数分配 (i, j)，A 和 B 的取值范围是连续整数区间，可通过区间交集快速计数，无需枚举每个值

算法步骤

  1. 预处理：

    • 计算 C 的十进制位数 k
    • 预处理10的幂次数组 pow10[i] = 10^i（用于快速计算范围边界）

  2. 枚举位数分配：

    • 遍历 A 的可能位数 i（从 1 到 n-3，因为至少需要1位 B、1位 C 和 2 个符号）
    • 计算 B 的位数：j = n - i - k - 2
    • 合法性检查：若 j < 1，跳过当前 i（位数不合法）

  3. 计算数值范围（针对当前 (i, j)）：

    • A 的取值范围：
      • 下界 A_min = (i == 1) ? 0 : pow10[i-1]（无前导零）
      • 上界 A_max = min(C, pow10[i] - 1)（A 不能超过 C，否则 B 为负）
    • B 的取值范围：
      • 下界 B_min = (j == 1) ? 0 : pow10[j-1]
      • 上界 B_max = min(C, pow10[j] - 1)

  4. 区间交集快速计数：

    • A 必须满足：A ∈ [A_min, A_max] 且 B = C - A ∈ [B_min, B_max]
    • 转化为 A 的有效区间：
      • 左边界：L = max(A_min, C - B_max)
      • 右边界：R = min(A_max, C - B_min)
    • 若 L ≤ R，则当前位数分配贡献的合法算式数为 R - L + 1，累加到答案

  5. 输出结果：遍历结束后输出累计的答案

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll C;
    cin >> n >> C;

    ll ans = 0;
    int k = to_string(C).size();

    vector<ll> pow10(21);
    pow10[0] = 1;
    for (int i = 1; i <= 20; i++)
        pow10[i] = pow10[i - 1] * 10;

    for (int i = 0; i < n - 3; i++) {
        int j = n - i - k - 2;
        if (j < 1)
            break;
        ll A_min = (i == 1) ? 0 : pow10[i - 1];
        ll A_max = min(C, pow10[i] - 1);
        ll B_min = (j == 1) ? 0 : pow10[j - 1];
        ll B_max = min(C, pow10[j] - 1);
        ll L = max(A_min, C - B_max);
        ll R = min(A_max, C - B_min);
        if (L <= R)
            ans += (R - L + 1);
    }

    cout << ans << endl;
}

计算复杂度分析

  • 时间复杂度：O(n)

    • 仅需遍历 A 的位数 i 最多 n-3 ≤ 17 次
    • 每次迭代执行常数级别的数学运算（O(1)）
    • 总体与 C 的大小无关，仅依赖 n

  • 空间复杂度：O(1)

    • 只使用少数几个整型变量存储中间结果
    • 预处理 pow10 数组仅需大小21（0 到 20）

为什么高效？

  • 避免枚举：将 A、B 的取值从点集转化为区间，利用数学公式直接计算合法数量
  • 剪枝充分：位数分配 i 的循环本身范围极小，且每次快速排除非法的 (i, j) 组合
  • 常数操作：区间交集计算仅涉及最大值、最小值和加减法，无复杂数据结构

该算法完美利用了题目约束（特别是 n 极小）和数学性质，将看似需要枚举的问题转化为线性扫描即可解决。