問題一覧 > 通常問題

No.1548 [Cherry 2nd Tune B] 貴方と私とサイクルとモーメント

レベル : / 実行時間制限 : 1ケース 4.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 25
作問者 : KazunKazun / テスター : PCTprobabilityPCTprobability
0 ProblemId : 6147 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-10 23:55:26

問題文

$N$ 頂点からなるサイクルがあり, ある頂点からサイクルに沿った順に番号が $1$ から $N$ が振られている. 最初, 頂点 $i$ には整数 $A_i$ が書かれている. また, ここで, $Q$ 個のQueryが与えられるので, 順番に処理せよ.

  • Type 0: $P(U,V,W)$ 上にある頂点全てに書かれている整数を $B$ に変更せよ.
  • Type 1: $P(U,V,W)$ 上にある頂点上に書かれている整数の1次中心化モーメントを $\mu_1$ としたとき, $\mu_1 \pmod{998244353}$ を求めよ.
  • Type 2: $P(U,V,W)$ 上にある頂点上に書かれている整数の2次中心化モーメントを $\mu_2$ としたとき, $\mu_2 \pmod{998244353}$ を求めよ.
  • Type 3: $P(U,V,W)$ 上にある頂点上に書かれている整数の3次中心化モーメントを $\mu_3$ としたとき, $\mu_3 \pmod{998244353}$ を求めよ.
  • Type 4: $P(U,V,W)$ 上にある頂点上に書かれている整数の4次中心化モーメントを $\mu_4$ としたとき, $\mu_4 \pmod{998244353}$ を求めよ.

ここで, $L$ 個の実数 $X_1, \dots, X_L$ の (算術, 相加) 平均を $M$ としたとき, $k$ 次中心化モーメント $\mu_k$ は $\displaystyle \mu_k=\dfrac{1}{L} \sum_{i=1}^L (X_i-M)^k$ と定義される.

また, $P(U,V,W)$ $(U, V, W$ は互いに異なる$)$ は以下のようにして定義される.

  • サイクル上には $U,V$ を端点とする道はちょうど2つ存在するが, このうち頂点 $W$ を含む道とする. この道は一意に定まる.

なお, 今回の制約下では, $\mu_1, \mu_2, \mu_3, \mu_4$ は有理数になることが示せる.

▶(有理数)$\pmod{998244353}$ とは

この問題の制約下において, 出力すべき有理数 $H$ は整数 $P$ と $998244353$ の倍数ではない整数 $Q$ を用いて, $H=\frac{P}{Q}$ と表すことができることが保証されている. このとき, $P \equiv QX~\pmod{998244353}$ を満たす $0$ 以上 $998244353$ 未満の整数 $X$ が唯一存在するので, この整数 $X$ を用いて, $H \pmod{998244353}=X$ と定義する.

制約

  • $3 \leq N \leq 2 \times 10^5$
  • $0 \leq A_i < 998244353$
  • $1 \leq Q \leq 2.5 \times 10^4$
  • $1 \leq U, V, W \leq N$
  • $U, V, W$ は互いに異なる.
  • $0 \leq B < 998244353$
  • $Q$ 個のQueryの中にType 1, Type 2, Type 3, Type 4が合わせて一つ以上存在する.

入力

$N$
$A_1$ $\dots$ $A_N$
$Q$
${\rm Query}_1$
$\vdots$
${\rm Query}_Q$

ここで, 各 ${\rm Query}_j$ は以下の形で与えられる.

  • Type 0
  • $0$ $U$ $V$ $W$ $B$
  • Type 1
  • $1$ $U$ $V$ $W$
  • Type 2
  • $2$ $U$ $V$ $W$
  • Type 3
  • $3$ $U$ $V$ $W$
  • Type 4
  • $4$ $U$ $V$ $W$

出力

Type 1, Type 2, Type 3, Type 4が与えられたときの結果を順に出力せよ. ただし, それぞれ改行を忘れないこと.

サンプル

サンプル1
入力
7
1 5 3 6 4 2 7
4
2 1 4 5
0 1 3 2 8
3 6 2 1
4 1 7 4
出力
598946617
405536752
440707678

  • [第1クエリ] $P(1,4,5)$ 上にある頂点は, $1,4,5,6,7$ である. $A_1, A_4, A_5, A_6, A_7$ における2次中心化モーメントは平均 $M$ が $M=4$ なので,
    $\quad \mu_2=\dfrac{1}{5} ((A_1-M)^2+(A_4-M)^2+(A_5-M)^2+(A_6-M)^2+(A_7-M)^2)=\dfrac{1}{5}((-3)^2+2^2+0^2+(-2)^2+3^2)=\dfrac{26}{5}$
    なので, $\mu_2 \pmod{998244353}=598946617$ である.
  • [第2クエリ] $P(1,3,2)$ 上にある頂点は, $1,2,3$ である. よって, $A_1, A_2, A_3$ は全て $8$ に更新される.
  • [第3クエリ] $\mu_3=-\dfrac{525}{32}$ より, $\mu_3 \pmod {998244353}=405536752$ である.
  • [第4クエリ] $\mu_4=\dfrac{120698}{2401}$ より, $\mu_4 \pmod{998244353}=440707678$ である.

サンプル2
入力
4
9 9 9 9
3
2 1 2 3
3 4 2 1
4 1 3 2
出力
0
0
0

全ての頂点に書かれている整数は等しいので, $\mu_2, \mu_3, \mu_4$ は全て $0$ になる.

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