問題一覧 > 通常問題

No.2966 Simple Plus Minus Problem

レベル : / 実行時間制限 : 1ケース 2.567秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : ねしん / テスター : 遭難者
1 ProblemId : 11520 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-16 14:58:29

ストーリー

ネタ切れ 　　

まあ、ストーリーはモン〇トの時点で相当ネタ切れだったんだけど… 　　

ヒント置いておきます→ヒント

問題文

整数 N,KN,K と長さ NN の整数列 AA が与えられます。

次の操作を整数列 AA に対して KK 回行います。

  • (A1,A2,⋯ ,AN)(A_1,A_2,\cdots,A_N) を (∑i=11(−1)i+1Ai,∑i=12(−1)i+1Ai,⋯ ,∑i=1N(−1)i+1Ai)(\sum_{i=1}^{1}(-1)^{i+1}A_i,\sum_{i=1}^{2}(-1)^{i+1}A_i,\cdots,\sum_{i=1}^{N}(-1)^{i+1}A_i) に置き換える。

    KK 回置き換えた後の整数列 AA の各要素を mod\text{mod} 998244353998244353 で求めてください。

    • 入力

    NN KK
A1A_1 A2A_2 ⋯\cdots ANA_{N}

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤K≤1081 \leq K \leq 10^8
  • 1≤Ai≤108 (1≤i≤N)1 \leq A_i \leq 10^8 \ (1 \leq i \leq N)
  • 入力はすべて整数

    • 出力

    KK 回置き換えた後の整数列 AA の各要素を mod\text{mod} 998244353998244353 で空白区切りで 11 行に出力してください。

    サンプル

    サンプル1
    入力
    5 1
1 2 3 4 5
    出力
    1 998244352 2 998244351 3

    整数列 AA に操作を 11 回行うと、(1,1−2,1−2+3,1−2+3−4,1−2+3−4+5)=(1,−1,2,−2,3)(1,1-2,1-2+3,1-2+3-4,1-2+3-4+5)=(1,-1,2,-2,3) となります。

    サンプル2
    入力
    3 7
96 58 74
    出力
    96 38 400

    サンプル3
    入力
    1 100000000
622
    出力
    622

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