题解 | #丛林木马#

1. 问题分析

本题描述了一种非标准的“乘法”运算。在标准的大数乘法算法中，数值 $a$ 和 $b$ 被拆解为位权表达式： $a = \sum_{i=0}^{n-1} a_i 10^i, \quad b = \sum_{j=0}^{m-1} b_j 10^j$

标准的乘法逻辑遵循分配律： $a \times b = \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} (a_i \cdot 10^i) \times (b_j \cdot 10^j) = \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} (a_i \cdot b_j) \cdot 10^{i+j}$

根据题目描述，ZM 将所有的乘法运算误算成了加法运算。这意味着在处理每一位的组合时，原本的 $(a_i \cdot 10^i) \times (b_j \cdot 10^j)$ 被替换为了 $(a_i \cdot 10^i) + (b_j \cdot 10^j)$ 。

2. 代数展开与线性归约

2.1 原始公式

令新运算结果为 $S$ 。根据题意，我们将所有的部分乘积替换为部分和：

$S = \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} (a_i \cdot 10^i + b_j \cdot 10^j)$

利用求和符号的线性性质，我们可以跨项展开这个双重循环：

$S = \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i \cdot 10^i + \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} b_j \cdot 10^j$

2.2 双重求和简化

观察第一项：

$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i \cdot 10^i = \sum_{i=0}^{n-1} (a_i \cdot 10^i \cdot \sum_{j=0}^{m-1} 1)$

由于 $\sum_{j=0}^{m-1} 1$ 的结果即为 $b$ 的位数 $m$ ，该项简化为：

$m \cdot \sum_{i=0}^{n-1} a_i \cdot 10^i = m \cdot a$

同理，观察第二项：

$\sum_{j=0}^{m-1} \sum_{i=0}^{n-1} b_j \cdot 10^j = \sum_{j=0}^{m-1} (b_j \cdot 10^j \cdot \sum_{i=0}^{n-1} 1) = n \cdot b$

2.3 最终算法

通过代数化简，我们得到了极其简洁的线性表达式：

$S \equiv (m \cdot a + n \cdot b) \pmod{998244353}$

其中：

$n = |a|$ （ $a$ 的长度）
$m = |b|$ （ $b$ 的长度）
$a, b$ 为原大数对 $998244353$ 取模后的数值。

3. 复杂度分析与策略对比

时间复杂度： $O(\sum |a| + \sum |b|)$ 。对于每组测试数据，我们只需遍历一次字符串计算其模值。在总位数为 $10^6$ 的约束下，这是最优的线性时间复杂度。
空间复杂度： $O(\max |a|, \max |b|)$ 。主要消耗在于存储输入的字符串。

4. 代码实现

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

static constexpr ll MOD = 998244353;

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

    auto s2l = [&](const string & s) -> ll {
        ll val = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            val = (val * 10LL + s[i] - '0') % MOD;
        }
        return val;
    };

    int T;
    cin >> T;

    while (T--) {
        string a, b;
        cin >> a >> b;
        ll m = a.length();
        ll n = b.length();
        ll ans = (n * s2l(a) + m * s2l(b)) % MOD;
        cout << ans << "\n";
    }
}