問題一覧 > 通常問題

No.1548 [Cherry 2nd Tune B] You, Me, Cycles, and Moments

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 4.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 25
作問者 : 👑 Kazun / テスター : PCTprobability
お気に入りにしたユーザー ProblemId : 6147 / 自分の提出
問題文最終更新日: 2021-06-10 23:55:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 299 (BANNED CONTEST) (順位表) の他の問題:

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$
  • Type 1
  • $1$ $U$ $V$ $W$
  • Type 2
  • $2$ $U$ $V$ $W$
  • Type 3
  • $3$ $U$ $V$ $W$
  • Type 4
  • $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もしくは右上の雲マークをクリックしてアカウントを作成してください。