[SCOI2020模拟2] 矩阵求和

题目链接

本来对于比赛题，我是不太想写题解的。因为比赛题大多是训练思维，新套路不是很多。但是这一道题我必须写个题解，一道题包含了三四个我不会的操作和一系列会一点但是不熟悉的操作（菜死了没救了）。

首先，如何交换行列。我们发现原来的第$i$行$j$列的值是$(i-1) * m+j$，我们可以把它理解成$a_{i}+b_{j}$ 。交换某一行或某一列时，相当于交换$a$或$b$中的两个元素。

然后我们考虑，一个点$(x1,x2)$，在一次前缀和操作中会对答案造成多少贡献。先考虑在一维前缀和上做一次前缀和的情况：显然每个坐标大于等于$x1$的位置都会对答案造成$val$的贡献。所以贡献就是从大于等于$x1$的位置选出一个点的方案数。

接着考虑做两次前缀和的情况。那么显然就有：任意一个$x1$在第一次前缀和产生了贡献的点$P$，对于点$P$第二次前缀和产生了贡献的点，$x1$都会对其产生贡献。所以$x1$造成了的贡献就是从大于等于$x1$的位置选出两个个点的方案数（两个点的位置可以重合）。做多次前缀和的情况同理。

考虑二维怎么做。需要注意的是，我们的做法需要保证选的坐标最小的点做一次前缀和能贡献到其余所有点，而次小点做一次前缀和能贡献到除最小点以外的所有点，以此类推。所以我们需要保证的点的坐标在两个维度上单调递增。而二维的情况，我们分别在两个坐标轴上实现一维的做法。然后将两个轴上的坐标最小点组合乘一个二维平面上的坐标最小点。这样就能保证坐标单调递增了。

同时我们发现，其实这两个轴的贡献是独立的，所以一个点$(i,j)$在坐标轴上的贡献分别为$c_i$和$d_j$，那么这个点在二维前缀和中对别的点的贡献就是$c_i*d_j$。而一个轴的时候 我们可以用隔板法算：自己造成贡献的长度为$x$，做$k$次前缀和的贡献就是$\left(\begin{array}{c}x+k \\ k\end{array}\right)$。（ZJK曾经说过：“一个地方可以插多个板用隔板法，只能插一个用插板法”）

然后我们来推柿子。

最终的答案就是：$\sum_{i=x 1}^{x 2} \sum_{j=y 1}^{y 2} c_{i} d_{j}\left(a_{i}+b_{j}\right)=\left(\sum_{i=x 1}^{x 2} c_{i} a_{i}\right)\left(\sum_{j=y 1}^{y 2} d_{j}\right)+\left(\sum_{i=x 1}^{x 2} c_{i}\right)\left(\sum_{j=y 1}^{y 2} d_{j} b_{j}\right)$

显然有$c_{i}=\left(\begin{array}{c}k+x_{2}-i \\ k\end{array}\right)=\frac{\left(k+x_{2}-i\right) !}{k !(x 2-i) !}=\frac{1}{k !}\left(k+x_{2}-i\right) \frac{k}{ }$后面那个东西是$k$次下降幂，定义就是$\prod_{i=x-k+1}^{x}i$。然后我们知道下降幂的公式：$x^{\underline{n}}=\sum_{i=0}^{n}(-1)^{n-i} s(n, i) x^{i}$。其中$s(n,i)$是第一类斯特林数。

然后我们就接着推柿子，把下降幂带进去：

$\left(k+x_{2}-i\right)^{k}=\sum_{d=0}^{k}(-1)^{k-d} s(k, d)\left(k+x_{2}-i\right)^{d}$

然后二项式定理一下：
$\sum_{d=0}^{k}(-1)^{k-d} s(k, d) \sum_{e=0}^{d}\left(\begin{array}{l}d \\ e\end{array}\right)\left(x_{2}+k\right)^{e} i^{d-e}(-1)^{d-e}$

然后把这个柿子带入原式：

$\sum_{i=x 1}^{x 2} a_{i}\sum_{d=0}^{k}(-1)^{k-d} s(k, d) \sum_{e=0}^{d}\left(\begin{array}{l}d \\ e\end{array}\right)\left(x_{2}+k\right)^{e} i^{d-e}(-1)^{d-e}$

交换一下和号：（这里之所以能交换是因为第一个和号的起始和终止变量和后面和号的变量不相关）

$\sum_{d=0}^{k}(-1)^{k-d} s(k, d) \sum_{e=0}^{d}\left(\begin{array}{l}d \\ e\end{array}\right)\left(x_{2}+k\right)^{e}(-1)^{d-e} \sum_{i=x 1}^{x 2} a_{i}i^{d-e}$

然后我们对于每个$d-e$，都预处理出$\sum_{i=1}^na_ii^{d-e}$

也就是$\sum_{i=1}^na_ii^{d-e}$这个东西可以用树状数组维护一下。这样就能在知道$x1,x2$的情况下$O(log)$的查询任意一个$k$的$\sum_{i=x 1}^{x 2} a_{i}i^{d-e}$。因此一次询问的复杂度是$k^2\log n$

修改的话因为就是交换一下两个$a$和两个$b$，对于每个$k$暴力修改一下树状数组的两个位置即可。复杂度$k\log n$

附赠第一类斯特林数递推公式：
$s(n, r)=(n-1) s(n-1, r)+s(n-1, r-1), n>r \geq 1$

其中边界是$s(0,0)=1$