No.1548 [Cherry 2nd Tune B] You, Me, Cycles, and Moments
タグ : / 解いたユーザー数 25
作問者 : 👑
Kazun
/ テスター :
PCTprobability
Problem Statement
There is a cycle with $N$ vertices, numbered $1$ to $N$ in order along the cycle starting from a certain vertex. Initially, the integer $A_i$ is written on vertex $i$. You are given $Q$ Queries; process them in order.
- Type 0: Change the integers written on all vertices on $P(U,V,W)$ to $B$.
- Type 1: Let $\mu_1$ be the 1st central moment of the integers written on the vertices on $P(U,V,W)$. Find $\mu_1 \pmod{998244353}$.
- Type 2: Let $\mu_2$ be the 2nd central moment of the integers written on the vertices on $P(U,V,W)$. Find $\mu_2 \pmod{998244353}$.
- Type 3: Let $\mu_3$ be the 3rd central moment of the integers written on the vertices on $P(U,V,W)$. Find $\mu_3 \pmod{998244353}$.
- Type 4: Let $\mu_4$ be the 4th central moment of the integers written on the vertices on $P(U,V,W)$. Find $\mu_4 \pmod{998244353}$.
Here, for $L$ real numbers $X_1, \dots, X_L$ with (arithmetic, additive) mean $M$, the $k$-th central moment $\mu_k$ is defined as $\displaystyle \mu_k=\dfrac{1}{L} \sum_{i=1}^L (X_i-M)^k$.
Also, $P(U,V,W)$ $(U, V, W$ are pairwise distinct$)$ is defined as follows.
- There are exactly 2 paths on the cycle with $U,V$ as endpoints; it is the one of these that contains vertex $W$. This path is uniquely determined.
Note that under the constraints of this problem, it can be shown that $\mu_1, \mu_2, \mu_3, \mu_4$ are rational numbers.
▶What is (rational number)$\pmod{998244353}$?
Under the constraints of this problem, it is guaranteed that the rational number $H$ to be output can be expressed as $H=\frac{P}{Q}$ using an integer $P$ and an integer $Q$ that is not a multiple of $998244353$. In this case, there exists a unique integer $X$ that is at least $0$ and less than $998244353$ satisfying $P \equiv QX~\pmod{998244353}$, and using this integer $X$, we define $H \pmod{998244353}=X$.
Constraints
- $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$ are pairwise distinct.
- $0 \leq B < 998244353$
- Among the $Q$ Queries, there is at least one Query of Type 1, Type 2, Type 3, or Type 4 in total.
Input
$N$
$A_1$ $\dots$ $A_N$
$Q$
${\rm Query}_1$
$\vdots$
${\rm Query}_Q$
Here, each ${\rm Query}_j$ is given in the following form.
- Type 0
$0$ $U$ $V$ $W$ $B$
$1$ $U$ $V$ $W$
$2$ $U$ $V$ $W$
$3$ $U$ $V$ $W$
$4$ $U$ $V$ $W$
Output
Output the results for the given Type 1, Type 2, Type 3, and Type 4 Queries in order. Do not forget a newline after each one.
Sample
Sample 1
Input
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
Output
598946617 405536752 440707678
- [Query 1] The vertices on $P(1,4,5)$ are $1,4,5,6,7$. For the 2nd central moment of $A_1, A_4, A_5, A_6, A_7$, the mean $M$ is $M=4$, so
$\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}$
and therefore $\mu_2 \pmod{998244353}=598946617$. - [Query 2] The vertices on $P(1,3,2)$ are $1,2,3$. Therefore, $A_1, A_2, A_3$ are all updated to $8$.
- [Query 3] Since $\mu_3=-\dfrac{525}{32}$, we have $\mu_3 \pmod {998244353}=405536752$.
- [Query 4] Since $\mu_4=\dfrac{120698}{2401}$, we have $\mu_4 \pmod{998244353}=440707678$.
Sample 2
Input
4 9 9 9 9 3 2 1 2 3 3 4 2 1 4 1 3 2
Output
0 0 0
Since the integers written on all vertices are equal, $\mu_2, \mu_3, \mu_4$ are all $0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。