分别求出A、B的值，再计算差

#include <iostream>
#include <algorithm>
#include <cstring>  // 用于 memset初始化数组（本代码未使用）

using namespace std;

typedef long long LL;  // 定义长整型别名，方便使用

const int N = 100010, MOD = 1000000007;  // 数组最大长度和模数

int n;       // 题目中的进制上限N
int ma, mb;  // A和B的位数
int Ma[N], Mb[N];  // 存储A和B的各位数字（逆序存储）
int Jz[N];   // 存储每一位的进制

int main()
{
    // 读取进制上限N
    scanf("%d", &n);

    // 读取A的位数和各位数字（逆序存储，方便从低位到高位处理）
    scanf("%d", &ma);
    for (int i = ma - 1; i >= 0; i --) scanf("%d", &Ma[i]);

    // 读取B的位数和各位数字（同样逆序存储）
    scanf("%d", &mb);
    for (int i = mb - 1; i >= 0; i --) scanf("%d", &Mb[i]);

    // 计算每一位的进制：
    // 取max(2, Ma[i]+1, Mb[i]+1) 保证：
    // 1. 至少是二进制
    // 2. 数字在该进制下合法（digit < base）
    for (int i = ma - 1; i >= 0; i --)
        Jz[i] = max({2, Ma[i] + 1, Mb[i] + 1});

    // 计算A的十进制值（使用秦九韶算法）
    LL res_a = 0;
    for (int i = ma - 1; i >= 0; i --)
        res_a = (res_a * Jz[i] + Ma[i]) % MOD;  // 逐位计算并取模

    // 计算B的十进制值（同样使用秦九韶算法）
    LL res_b = 0;
    for (int i = ma - 1; i >= 0; i --)
        res_b = (res_b * Jz[i] + Mb[i]) % MOD;

    // 输出A-B的结果，并处理可能的负数情况：
    // (res_a - res_b + MOD) % MOD 保证结果在[0, MOD-1]范围内
    printf("%lld\n", (res_a - res_b + MOD) % MOD );

    return 0;
}

为什么需要 (res_a - res_b + MOD) % MOD？

在模运算中，直接计算 res_a - res_b 可能会导致负数，而 C++ 的 % 运算符对负数的处理方式可能不符合预期（例如 -3 % 5 在 C++ 里是 -3，但我们通常希望它映射到 2）。
因此，加上 MOD 再取模 可以确保结果始终是非负的，且仍然符合数学上的模运算定义。

数学解释

我们希望计算的范围是 [0, MOD-1]：
$$(res_a - res_b) \mod MOD$$
但由于 res_a 和 res_b 本身已经是 % MOD 后的结果，所以：

• res_a 的范围是 [0, MOD-1]

• res_b 的范围是 [0, MOD-1]

因此：

• res_a - res_b 的范围是 [-(MOD-1), MOD-1]

• 加上 MOD 后，res_a - res_b + MOD 的范围是 [1, 2*MOD-1]

• 再 % MOD 后，最终结果的范围是 [0, MOD-1]

正确 vs. 错误的例子

假设 MOD = 1000000007，我们来看几种情况：

情况 1：res_a >= res_b（正常情况）

• res_a = 100，res_b = 50

• +MOD计算：
  cpp (100 - 50 + MOD) % MOD = (50 + 1000000007) % 1000000007 = 50

• 不+MOD计算（直接 (res_a - res_b) % MOD）：
  cpp (100 - 50) % MOD = 50 % 1000000007 = 50
  结果相同，这种情况不需要 + MOD。

情况 2：res_a < res_b（关键情况）

• res_a = 50，res_b = 100

• +MOD计算：
  cpp (50 - 100 + MOD) % MOD = (-50 + 1000000007) % 1000000007 = 999999957 % 1000000007 = 999999957
  结果正确（因为 999999957 ≡ -50 ≡ 1000000007 - 50）。

• 不+MOD计算（直接 (res_a - res_b) % MOD）错误计算：
  cpp (50 - 100) % MOD = (-50) % 1000000007 = -50
  结果是负数，不符合模运算的数学定义（我们希望结果在 [0, MOD-1] 范围内）。

总结

关键点：

• + MOD 的作用：防止 res_a - res_b 为负数时，取模后仍然是负数。

• % MOD 的作用：确保结果仍然在 [0, MOD-1] 范围内。

代码优化建议

如果题目保证 A >= B（即 res_a >= res_b），那么可以省略 + MOD：

printf("%lld\n", (res_a - res_b) % MOD);

但如果不能保证（例如 res_a 和 res_b 是中间计算结果），则必须使用：

printf("%lld\n", (res_a - res_b + MOD) % MOD);

推荐写法：

LL ans = (res_a - res_b) % MOD;
if (ans < 0) ans += MOD;  // 如果可能为负数，就加上 MOD
printf("%lld\n", ans);

这样更清晰，且避免不必要的 + MOD 运算。

优化后的动态计算法（y总写法）

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;  // 定义长整型别名

const int N = 100010, MOD = 1000000007;  // 最大位数和模数

int n;       // 最大进制限制
int ma, mb;  // A和B的位数
int Ma[N], Mb[N];  // 存储A和B的各位数字（逆序存储）

int main()
{
    scanf("%d", &n);  // 读取进制上限

    // 读取A的位数和各位数字（逆序存储便于处理）
    scanf("%d", &ma);
    for (int i = ma - 1; i >= 0; i --) scanf("%d", &Ma[i]);

    // 读取B的位数和各位数字（逆序存储）
    scanf("%d", &mb);
    for (int i = mb - 1; i >= 0; i --) scanf("%d", &Mb[i]);

    LL res = 0;  // 初始化结果
    // 从最高位开始处理
    for (int i = ma - 1; i >= 0; i --)
    {
        // 核心计算：动态确定每位进制，并更新结果
        res = (res * (LL)max({2, Ma[i] + 1, Mb[i] + 1}) + Ma[i] - Mb[i]) % MOD;
    }

    printf("%lld\n", res);  // 输出结果

    return 0;
}

核心算法

1. 进制确定原则：

   • 每位进制取max(2, A[i]+1, B[i]+1)，确保：

     • 满足最低二进制限制

     • 数字在该进制下合法（数字 < 进制）

   注意：当B位数不足时，代码中Mb[i]默认为0（因数组未初始化）

2. 差值计算：

   • 使用多项式求值公式： $$res = res \times base + (A_i - B_i)$$

   • 动态维护当前位的权重（进制积）

3. 模数处理：

   • 每步计算后取模1e9+7，防止溢出

分析过程

1. 进制选择策略：

   • 要使A-B最小，需让A尽可能小、B尽可能大

   • 但题目限制A≥B，因此最小化差值等价于最小化A和B的十进制差值

   • 通过选择每位最小合法进制（max(2, digit+1)）实现

2. 数学推导：

   • 设第i位进制为$k_i$，则：

   $$A = \sum_{i=0}^{m-1} A_i \prod_{j=0}^{i-1} k_j$$
   $$B = \sum_{i=0}^{m-1} B_i \prod_{j=0}^{i-1} k_j$$

   • 差值计算时，乘积项会抵消，最终简化为动态维护进制积

3. 边界处理：

   • 当Ma和Mb位数不等时，短的数字高位补0（由数组存储顺序自动实现）

结论

• 关键结论：在保证合法性的前提下，每位取最小可能进制（max(2, digit+1)）时，A-B的十进制值最小

• 算法正确性：通过动态维护进制积和差值，保证了计算过程的高效性和正确性

时间复杂度

• 时间复杂度：$O(max(Ma, Mb))$

  • 单次遍历所有数位，每个数位处理时间为$O(1)$

• 空间复杂度：$O(max(Ma, Mb))$

  • 用于存储输入的数字序列

应用场景

1. 进制转换问题：处理非固定进制的数值计算

2. 大数运算：适用于高精度减法场景

3. 密码学：特殊进制系统的数值分析

4. 注意事项：需确保输入满足A≥B，否则需要额外处理

多项式差值计算与秦九韶算法解析

秦九韶算法原理

秦九韶算法（Horner’s Method） 是一种高效计算多项式值的算法，将多项式：
$$P(x) = a_nx^n + a_{n-1}x^{n-1} + … + a_0$$
转化为嵌套形式：
$$P(x) = a_0 + x(a_1 + x(a_2 + … + x(a_{n-1} + x \cdot a_n)…))$$

算法优势

关键优势：

• 避免重复计算进制连乘积

• 单次遍历即可完成计算