問題一覧 > 通常問題

No.1839 Concatenation Matrix

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : SumitacchanSumitacchan / テスター : 👑 hitonanodehitonanode 👑 ygussanyygussany
1 ProblemId : 7455 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-15 16:09:15

問題文

各要素が $1$ から $9$ の整数であるような項数 $N$ の数列 $a_1,a_2,\dots,a_N$ が与えられます。

整数 $i,j\ (1\le i\le N, 1\le j \le N)$ に対して、 $X_{i,j}$ を次のように $i=1,2,\dots,N$ の順に定めます。

  • $i=1$ のとき、$X_{1,j}=a_j$
  • $i>1$ のとき、$X_{i,j}$ は $X_{i-1,j},X_{i-1,j+1}$ の十進数表記をこの順に繋げて得られる数とする。ただし、$X_{i-1,N+1}$ は $X_{i-1,1}$ とみなす。
    (例えば、$X_{i-1,j}=1234,X_{i-1,j+1}=5678$ のときは $X_{i,j}=12345678$ になります。)

整数 $j\ (1\le j \le N)$ のそれぞれに対して、$X_{N,j}$ を $998244353$ で割った余りを求めてください。

入力

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

  • $2 \le N \le 10^5$
  • $1\le a_i \le 9$
  • 入力は全て整数である。

出力

$N$ 行出力してください。
$j$ 行目には、$X_{N,j}$ を $998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
3
1 2 3
出力
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$

となります。

サンプル2
入力
5
1 1 1 1 1
出力
260339166
260339166
260339166
260339166
260339166

$X_{5,1}=X_{5,2}=X_{5,3}=X_{5,4}=X_{5,5}=1111111111111111$ です。

サンプル3
入力
9
1 4 1 4 2 1 3 5 6
出力
95048781
200520263
743817659
355269523
183551074
780741532
611502941
938834353
526612559

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