問題一覧 > 通常問題

No.1839 Concatenation Matrix

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

問題文

各要素が 1 から 9 の整数であるような項数 N の数列 a1,a2,,aN が与えられます。

整数 i,j (1iN,1jN) に対して、 Xi,j を次のように i=1,2,,N の順に定めます。

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

整数 j (1jN) のそれぞれに対して、XN,j998244353 で割った余りを求めてください。

入力

N
a1  a2    aN

  • 2N105
  • 1ai9
  • 入力は全て整数である。

出力

N 行出力してください。
j 行目には、XN,j998244353 で割った余りを出力してください。

サンプル

サンプル1
入力
3
1 2 3
出力
1223
2331
3112

X1,1=1,X1,2=2,X1,3=3
X2,1=12,X2,2=23,X2,3=31
X3,1=1223,X3,2=2331,X3,3=3112

となります。

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

X5,1=X5,2=X5,3=X5,4=X5,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もしくは右上の雲マークをクリックしてアカウントを作成してください。