Integer Division

题目描述

你被给定一个正整数 $X$，其十进制表示有 $N$ 位。$X$ 的任何一位都不是 $0$.
对于子集 $S \subseteq \lbrace 1,2, \ldots, N-1 \rbrace$，令 $f(S)$ 如下定义。

将 $X$ 的十进制表示看作一个长度为 $N$ 的字符串，当且仅当 $i \in S$ 时在第 $i$ 个和第 $(i + 1)$ 个字符之间进行分割，从而将其分解成 $|S| + 1$ 个字符串。
然后，将这 $|S| + 1$ 个字符串视为十进制表示的整数，令 $f(S)$ 为这 $|S| + 1$ 个整数的乘积。

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

输入格式

输入从标准输入给出，格式如下： $N$ $X$

输出格式

输出答案。

3
234

418

4
5915

17800

9
998244353

258280134

提示

$2 \leq N \leq 2 \times 10^5$ $X$ 的十进制表示有 $N$ 位，且每一位都不是 $0$.
输入中的所有数值都是整数。当 $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$.

标签: AtCoder|abc288F

来源

AtCoder|abc288F