問題一覧 > 通常問題

No.2004 Incremental Coins

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : to-omerto-omer / テスター : hamamuhamamu 👑 ygussanyygussany
8 ProblemId : 7232 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-05 22:14:40

問題文

00 から NN までの番号が付いた N+1N+1 個の箱とたくさんのコインがあります。 はじめ、箱 ii にはコインが AiA_i 枚入っています。 これから、次の操作を KK 回行います。

  • j=1,2,...,Nj=1,2,...,N の順に、箱 jj に入っているコインの枚数だけ箱 Pj (<j)P_j\ (<j) にコインを入れる。

全ての操作が終了した時に各箱に入っているコインの枚数を求めてください。 ただし、コインの枚数は非常に大きくなることがあるので、998244353998244353 で割った余りを求めてください。

制約

  • 入力は全て整数である。
  • 1N2×1051 \le N \le 2\times 10^5
  • 1K10181 \le K \le 10^{18}
  • 0Ai<998244353(0iN)0 \le A_i < 998244353 \quad (0 \le i \le N)
  • 0Pj<j(1jN)0 \le P_j < j \quad (1 \le j \le N)

入力

NN KK
A0A_0 A1A_1 ...... ANA_N
P1P_1 P2P_2 ...... PNP_N

出力

i (1iN+1)i\ (1\le i\le N+1) 行目に全ての操作が終了した時に箱 i1i-1 に入っているコインの枚数を出力してください。

サンプル

サンプル1
入力
3 2
1 1 1 1
0 1 2
出力
4
4
3
1
  • 11 回目の操作の後、各箱に入っているコインの枚数はそれぞれ 2,2,2,12,2,2,1 枚です。
  • 22 回目の操作の後、各箱に入っているコインの枚数はそれぞれ 4,4,3,14,4,3,1 枚です。
サンプル2
入力
3 1415926535
8 9 7 9
0 0 0
出力
459611028
9
7
9

998244353998244353 で割った余りを求めてください。

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