102885: [AtCoder]ABC288 F - Integer Division

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $500$ points

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

Input

题意翻译

给定一个 $n$ 位数 $X$,把 $X$ 分成若干段,得分为每一段的乘积(可以不分割,得分为 $X$)。求所有分法得分之和,取模 $998244353$。 Translate by [xionglangqi](https://www.luogu.com.cn/user/555345)

Output

分数:500分

问题描述

给你一个十进制表示下有$N$位正整数$X$。$X$的各位数字都不为0。

将$X$的十进制表示视为一个长度为$N$的字符串,并在仅当$i \in S$时在第$i$位和第$(i + 1)$位之间将其分解为$|S| + 1$个字符串。然后,将这$|S| + 1$个字符串视为十进制表示下的整数,并将$f(S)$定义为这些$|S| + 1$个整数的乘积。

有$2^{N-1}$个可以为$S$的$\lbrace 1,2, \ldots, N-1 \rbrace $的子集,包括空集。求所有这些$S$的$f(S)$的和,对$998244353$取模。

约束

  • $2 \leq N \leq 2 \times 10^5$
  • $X$的十进制表示有$N$位,且各位都不为0。
  • 输入中的所有值都是整数。

输入

输入通过标准输入给出,格式如下:

$N$
$X$

输出

打印答案。


样例输入1

3
234

样例输出1

418

对于$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$。


样例输入2

4
5915

样例输出2

17800

样例输入3

9
998244353

样例输出3

258280134

加入题单

上一题 下一题 算法标签: