問題一覧 > 通常問題

No.1839 Concatenation Matrix

レベル : / AI推定難易度 : 2125 / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 25
作問者 : Sumitacchan / テスター : 👑 hitonanode ygussany
お気に入りにしたユーザー ProblemId : 7455 / 自分の提出
問題文最終更新日: 2022-01-15 16:09:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 331 (順位表) の他の問題:

Problem Statement

You are given a sequence $a_1,a_2,\dots,a_N$ of length $N$, where each element is an integer from $1$ to $9$.

For integers $i,j\ (1\le i\le N, 1\le j \le N)$, define $X_{i,j}$ as follows, in the order $i=1,2,\dots,N$.

  • When $i=1$, $X_{1,j}=a_j$.
  • When $i>1$, $X_{i,j}$ is the number obtained by concatenating the decimal representations of $X_{i-1,j},X_{i-1,j+1}$ in this order. Here, $X_{i-1,N+1}$ is regarded as $X_{i-1,1}$.
    (For example, if $X_{i-1,j}=1234,X_{i-1,j+1}=5678$, then $X_{i,j}=12345678$.)

For each integer $j\ (1\le j \le N)$, find the remainder when $X_{N,j}$ is divided by $998244353$.

Input

$N$
$a_1\ \ a_2\ \ \cdots\ \ a_N$

  • $2 \le N \le 10^5$
  • $1\le a_i \le 9$
  • All inputs are integers.

Output

Print $N$ lines.
On the $j$-th line, print the remainder when $X_{N,j}$ is divided by $998244353$.

Sample

Sample 1
Input
3
1 2 3
Output
1223
2331
3112

$X_{1,1}=1,X_{1,2}=2,X_{1,3}=3$
$X_{2,1}=12,X_{2,2}=23, X_{2,3}=31$
$X_{3,1}=1223, X_{3,2}=2331, X_{3,3}=3112$

as shown above.

Sample 2
Input
5
1 1 1 1 1
Output
260339166
260339166
260339166
260339166
260339166

We have $X_{5,1}=X_{5,2}=X_{5,3}=X_{5,4}=X_{5,5}=1111111111111111$.

Sample 3
Input
9
1 4 1 4 2 1 3 5 6
Output
95048781
200520263
743817659
355269523
183551074
780741532
611502941
938834353
526612559

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。