No.1548 [Cherry 2nd Tune B] 貴方と私とサイクルとモーメント
タグ : / 解いたユーザー数 28
作問者 :
Kazun
/ テスター :
PCTprobability
問題文
$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$
$1$ $U$ $V$ $W$
$2$ $U$ $V$ $W$
$3$ $U$ $V$ $W$
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。