/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
10 進表記で N 桁の正整数 X が与えられます。X の各桁は 0 ではありません。
\lbrace 1,2, \ldots, N-1 \rbrace の部分集合 S に対し、f(S) を以下のように定義します。
X を 10 進表記したものを長さ N の文字列とみなし、i \in S のとき、またそのときに限り文字列の i 文字目と i + 1 文字目に区切りを入れることで |S| + 1 個の文字列に分解する。
このようにして得られた |S|+1 個の文字列を 10 進表記された整数とみなし、f(S) をこれら |S|+1 個の整数の積で定める。
S としてあり得るものは空集合を含めて 2^{N-1} 通りありますが、これら全てに対する f(S) の総和を 998244353 で割った余りを求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- X は 10 進表記で 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 であるため、418 を出力します。
入力例 2
4 5915
出力例 2
17800
入力例 3
9 998244353
出力例 3
258280134
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