P5294 [HNOI2019] 序列

题目背景

HNOI2019 day2t3

题目描述

给定一个长度为$n$的序列$A_1, … , A_n$,以及$m$个操作,每个操作将一个$A_i$修改为$k$。第一次修改之前及每次修改之后,都要求你找到一个同样长度为$n$的单调不降序列$B_1,… ,B_n$,使得$\sum_{i=1}^n(A_i-B_i)^2$最小,并输出最小值。 需要注意的是每次操作的影响都是独立的,也即每次操作只会对当前询问造成影响。为了避免精度问题,我们保证这个最小值是个分数,也即能表示为两个非负整 数相除的形式:$x/y$。那么你将要输出$(x\times y^{p-2}\mod p)$的值,表示模意义下$x/y$的值。其中$P = 998244353$是一个大质数。

输入格式

输出格式

说明/提示

【样例解释】 第一个询问的最优B序列为:{5 5 5 5 5}。 第二个询问的最优B序列为:{1 2 4 5 5}。 第三个询问的最优B序列为:{3 3 4 5 5}。 第四个询问的最优B序列为:{5 5 5 6 6}。 样例是存在最优方案使$B_i$皆为整数的特殊情况。 【数据范围】 对于前 10%的数据,保证$n,m\le 10$,$k,A_i\le 1000$ ,且存在一种最优方案,使得$B_i$皆为整数。 对于前 30%的数据,保证 $n,m\le 100$。 对于另外 20%的数据,保证 $m = 0$ 。 对于另外 20%的数据,保证 $n,m \le 3 \times 10^4$。 对于所有数据,保证 $3 \le n \le 10^5,0 \le m \le 10^5,1 \le k, A_i \le 10^9$。 【编译命令】 对于 c++语言: g++ -o sequence sequence.cpp –lm –O2 对于 c 语言: gcc -o sequence sequence.c –lm –O2 对于 pascal 语言: fpc sequence.pas –O2