原题

给定一位数字 a (1<=a<=9) 和正整数 n (1<=n<=10^6)，求

$$ a+aa+aaa+\cdots+\underbrace{aa\cdots a}_{n\text{ 个 }a} $$

对 998244353 取模后的结果。

输入一行两个整数 a,n。输出一行一个整数，表示答案。

样例：

输入
2 3

输出
246

说明：2+22+222=246。

题解

MC0450 小a连数（C++17）

给定一位数字 a 和正整数 n，求 a+aa+aaa+...，最后一项恰有 n 个 a，答案对 998244353 取模。每一项都比前一项多拼了一个 a，可以直接递推，不必处理大整数。

把长度为 i-1 的一项记为 t_{i-1}。在末尾接上一个 a 时，原来的数整体左移一位，因此

$$ t_i=10t_{i-1}+a. $$

也就是说，新加的末位贡献为 a，前面的部分乘以 10。题目只要模 MOD=998244353 的结果，递推时直接取模即可：

$$ t_i=(10t_{i-1}+a)\bmod MOD. $$

设 S_i=Σ_{k=1}^{i}t_k，则

$$ S_i=(S_{i-1}+t_i)\bmod MOD. $$

初始化 t_0=0,S_0=0。循环 n 次后得到 S_n；当 n=1 时第一次递推正好得到 t_1=a。

每一项只在生成时加入一次，不会重算前面各项，故答案恰为原式的和。

时间复杂度为 O(n)，空间复杂度为 O(1)。n<=10^6 时可通过。

代码

#include <iostream>
using namespace std;

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

    const long long mod = 998244353;
    long long digit;
    int n;
    cin >> digit >> n;

    long long cur = 0;
    long long ans = 0;

    for (int i = 1; i <= n; ++i) {
        cur = (cur * 10 + digit) % mod;
        ans = (ans + cur) % mod;
    }

    cout << ans << '\n';
    return 0;
}

实现核对

cur 对应 t_i，ans 对应 S_i，循环变量 i 对应当前项的位数。