atcoder#ARC153E. [ARC153E] Deque Minimization

[ARC153E] Deque Minimization

题目描述

どの桁も 0 0 ではないような正整数 X X に対して,次の手順により正整数 Y Y を得ることを考えます:

  • 文字列 S S を空文字列で初期化する.
  • X X の桁数を N N とするとき,i = 1, , N i\ =\ 1,\ \ldots,\ N の順に次を行う:X X 10 10 進法表記の i i 文字目を,S S の先頭または末尾に挿入する.
  • 文字列 S S が表す正整数を Y Y とする.

この手順により X X から得ることが可能な正整数のうちで,最小のものを f(X) f(X) と書くことにします.


どの桁も 0 0 ではないような正整数 Y Y が与えられます.どの桁も 0 0 ではないような正整数 X X であって f(X) = Y f(X)\ =\ Y を満たすものの個数を 998244353 998244353 で割った余りを答えてください.

输入格式

入力は以下の形式で標準入力から与えられます.

Y Y

输出格式

どの桁も 0 0 ではないような正整数 X X であって f(X) = Y f(X)\ =\ Y を満たすものの個数を 998244353 998244353 で割った余りを出力してください.

题目大意

对于一个各位数字均 0\neq 0 的正整数 XX,定义 f(X)f(X) 为如下过程所能得到的最小的 YY

  • 对于初始为空的字符串 SS,依次将 XX 的十进制表示从左到右的每一位插入 SS 的最前端或最后端。设 YYSS 表示的正整数。

给出 YY,问有多少个 XX 满足 f(X)=Yf(X) = Y。答案对 998244353998244353 取模。

1332
3
3312
0
12234433442
153

提示

制約

  • Y Y はどの桁も 0 0 ではないような正整数
  • 1 Y < 10200000 1\leq\ Y\ <\ 10^{200000}

Sample Explanation 1

条件を満たす X X は,1332 1332 , 3132 3132 , 3312 3312 3 3 個です.