Score : $500$ points

问题描述

你给定一个正整数 $X$，其在十进制表示中有 $N$ 位数字。$X$ 的任意一位数字都不是 $0$。

对于 $\lbrace 1,2, \ldots, N-1 \rbrace$ 的子集 $S$，定义 $f(S)$ 如下：

将 $X$ 的十进制表示视为长度为 $N$ 的字符串，并通过以下方式将其分解为 $|S| + 1$ 个子字符串：仅当 $i \in S$ 时，在第 $i$ 个和第 $(i + 1)$ 个字符之间进行分割。

然后，将这 $|S| + 1$ 个子字符串视为它们各自的十进制表示的整数，并令 $f(S)$ 为这些 $|S| + 1$ 个整数的乘积。

$\lbrace 1,2, \ldots, N-1 \rbrace$ 的所有子集中，包括空集，都可能是集合 $S$。求所有这些 $S$ 上的 $f(S)$ 的和，对 $998244353$ 取模的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a positive integer $X$ with $N$ digits in decimal representation. None of the digits of $X$ is $0$.
For a subset $S$ of $\lbrace 1,2, \ldots, N-1 \rbrace$, let $f(S)$ be defined as follows.

See the decimal representation of $X$ as a string of length $N$, and decompose it into $|S| + 1$ strings by splitting it between the $i$-th and $(i + 1)$-th characters if and only if $i \in S$.
Then, see these $|S| + 1$ strings as integers in decimal representation, and let $f(S)$ be the product of these $|S| + 1$ integers.

There are $2^{N-1}$ subsets of $\lbrace 1,2, \ldots, N-1 \rbrace$, including the empty set, which can be $S$. Find the sum of $f(S)$ over all these $S$, modulo $998244353$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $X$ has $N$ digits in decimal representation, none of which is $0$.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$

$X$

Output

Print the answer.

Sample Input 1

3
234

Sample Output 1

418

For $S = \emptyset$, we have $f(S) = 234$.
For $S = \lbrace 1 \rbrace$, we have $f(S) = 2 \times 34 = 68$.
For $S = \lbrace 2 \rbrace$, we have $f(S) = 23 \times 4 = 92$.
For $S = \lbrace 1, 2 \rbrace$, we have $f(S) = 2 \times 3 \times 4 = 24$.
Thus, you should print $234 + 68 + 92 + 24 = 418$.

Sample Input 2

4
5915

Sample Output 2

17800

Sample Input 3

9
998244353

Sample Output 3

258280134

update @ 2024/3/10 12:02:47