SOLUTION FROM WUMIN4
题意
若长度为 \(n\) 的数组 \(a\) 排序后为 \(b\)，定义 \(a\) 的权值为 \(\sum_{i=1}^n \lfloor\frac{b_i\cdot i^k}{w}\rfloor \bmod 998244353\)。
有 \(q\) 次操作，每次操作修改一个 \(a_i\)，随后输出 \(a\) 的权值。
\(n,a_i\le 10^5,1\le k,w\le 5\)
思路
将式子拆成 \(\frac{\sum_{i=1}^n (b_i\cdot i^k-(b_i\cdot i^k) \bmod w)}{w}\)。
于是我们要维护 \(\sum_{i=1}^n b_i\cdot i^k\) 和 \(\sum_{i=1}^n (b_i\cdot i^k) \bmod w\)。
由于 \(a_i\le 10^5\)，可以在权值线段树上维护。
- \(\sum_{i=1}^n b_i\cdot i^k\)
假设左节点为 \(b_1 1^k+b_2 2^k+\cdots+b_l l^k\)，右节点为 \(b'_1 1^k+b'_2 2^k+\cdots+b'_r r^k\)。
则合并后有 \(b_1 1^k+b_2 2^k+\cdots+b_l l^k+b'_1 (l+1)^k+b'_2 (l+2)^k+\cdots+b'_r (l+r)^k\)。
问题在于如何计算
\[\sum_{i=1}^r b'_i (l+i)^k
\]
二项式定理拆开得到
\[\sum_{i=1}^r \sum_{j=0}^{k} b'_ii^j\binom{k}{j}l^{k-j}
\]
换个位置
\[\sum_{j=0}^{k} \sum_{i=1}^r b'_ii^j\binom{k}{j}l^{k-j}
\]
于是维护该节点的 \(f_j=\sum_{i=1}^r b'_ii^j\)。由于 \(\binom{k}{j}l^{k-j}\) 与 \(i\) 无关，则有
\[\sum_{j=0}^{k} \binom{k}{j}l^{k-j} f_j
\]
因为 \(k\le 5\)，直接转移。
- \(\sum_{i=1}^n (b_i\cdot i^k) \bmod w\)