AT_abc288_f [ABC288F] Integer Division

题目描述

给定一个用十进制表示的 $N$ 位正整数 $X$，其中 $X$ 的每一位都不是 $0$。
对于 $\lbrace 1,2,\ldots,N-1 \rbrace$ 的任意子集 $S$，定义 $f(S)$ 如下：

将 $X$ 的十进制表示看作长度为 $N$ 的字符串。对于每个 $i \in S$，且仅当 $i \in S$ 时，在字符串的第 $i$ 位和第 $i+1$ 位之间插入一个分隔符，将其分割成 $|S|+1$ 个字符串。
将这 $|S|+1$ 个字符串分别视为十进制整数，$f(S)$ 定义为这些整数的乘积。

$S$ 的所有可能取法（包括空集）共有 $2^{N-1}$ 种。请计算所有 $f(S)$ 之和，并对 $998244353$ 取模后输出。

输入格式

输入从标准输入读入，格式如下：

$N$ $X$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
234

输出 #1

418

输入输出样例 #2

输入 #2

4
5915

输出 #2

17800

输入输出样例 #3

输入 #3

9
998244353

输出 #3

258280134

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $X$ 是一个 $N$ 位的十进制整数，且每一位都不是 $0$
• 输入均为整数

样例解释 1

当 $S = \emptyset$ 时，$f(S) = 234$。
当 $S = \lbrace 1 \rbrace$ 时，$f(S) = 2 \times 34 = 68$。
当 $S = \lbrace 2 \rbrace$ 时，$f(S) = 23 \times 4 = 92$。
当 $S = \lbrace 1, 2 \rbrace$ 时，$f(S) = 2 \times 3 \times 4 = 24$。
因此 $234 + 68 + 92 + 24 = 418$，输出 $418$。

由 ChatGPT 4.1 翻译