码蹄杯初赛第一场

5.

给定矩阵$a\in\mathbb{N}^{m\times m},\ b\in\mathbb{N}^{n\times n}\ (m,n\in\mathbb{N^*},\ m\geq n)$，求

$$\left(\sum_{i=0}^{m-n}\sum_{j=0}^{m-n}\sum_{k=0}^{n-1}\sum_{l=0}^{n-1}(a_{i+k,j+l}\oplus b_{k.l})\right)\bmod(10^9+7).$$

保证$m,n\leq10^3,\ (\forall i)\ (\forall j)\ (a_{i,j},b_{i,j}\leq10^9)$。

按位异或对加法不满足分配律，所以直接化简这个和式是不可能的。考虑按位处理。用$x^{(p)}$表示$x$从低到高的第$p$位。

考虑贡献法，$a_{i,j}$与哪些元素进行了异或？于是原和式可以化为

记

按位考虑，则原和式等于

其中$B=\lceil\log(10^9)\rceil$。

对于取定的$i,j,p$，由异或的定义可知，我们只需数出$b$在区域$\mathbb{N}^2\cap([k_{\min},k_{\max}]\times[l_{\min},l_{\max}])$中$0$或$1$的数量即可。当$a_{i,j}^{(p)}=0$时数$1$，当$a_{i,j}=1$时数$0$。这个计数值可以通过$\varTheta(n^2)$预处理二维前缀和来$\varTheta(1)$求出。

7.

给定$a\in(\mathbb{N}^*)^{3\times n}\ (n\in\mathbb{N}^*)$，求

$$(a_{0,\lfloor i/n^2\rfloor}\cdot a_{1,\lfloor i/n\rfloor\bmod n}\cdot a_{2,i\bmod n})_{i=0}^{n^3-1}$$

中最小的$m\in\mathbb{N}^*$项。保证$n\leq10^5,\ m\leq\min\{n^3,2n\},\ (\forall i\in\{0,1,2\})\ (\forall i)\ (\forall j)\ (a_{i,j}\leq10^5)$。

我真傻，真的。

可以先用$a_0,a_1$组合一遍乘积，用最小的$m$个再去与$a_2$组合一遍。这一点我没想到。

用堆维护最小的$m$项是很容易想到的。

但这样还不够！暴力组合两个数组，复杂度仍然高达$\varTheta(n^2\log m)$，我们需要找到更高效的寻找最小$m$个乘积的方式。很容易想到将它们先排序，然后怎么办？

如果我们将这两个数组组合的过程列成表格（以$a_0,a_1$分别作纵轴和横轴，表格中填上乘积），那末每一行、每一列都必定是递增的。现在我们的任务变为一个经典问题（多路归并问题）：如何在这$n$行（从列的视角看当然也可以，这是等价的）已经有序的数列中选出最小的$m$个？很显然只需对各行维护一个从左往右移动的指针，指向下一个待选元素；每次选取所有待选元素中最小的那一个，并移动指针即可；而“选取所有待选元素中最小的那一个”正适合用一个小根堆来维护。进一步地，由于我们/只需求出最小的$m$个元素，我们只需考虑前$\min\{m,n\}$行即可，因为第$m+1$行（如果存在）的首个元素必定比前$m$行的首个元素更大。