题解

思路

若 $N=1$，列最大值序列 $B$ 可以任取，$A_1$ 随之唯一确定，答案是 $K^M$；$M=1$ 时同理为 $K^N$。

做法

下面设 $N,M\ge2$。任意网格都满足 $A_i\le B_j$，所以必须有 $\max A\le\min B$；反过来，只要该不等式成立，就能把各行最小值与各列最大值放在前两行、前两列的交叉位置，再用对应的行最小值填充其余格子，从而构造出所需网格，因此这也是充分条件。

枚举 $x=\max A$。所有元素不超过 $x$ 且至少一个等于 $x$ 的序列 $A$ 有 $x^N-(x-1)^N$ 个，而序列 $B$ 的每个元素都可在 $x$ 到 $K$ 中选择，共有 $(K-x+1)^M$ 个。答案即 $\sum_{x=1}^{K}(x^N-(x-1)^N)(K-x+1)^M$。

复杂度

用二进制快速幂计算每一项，时间复杂度为 $O(K\log(N+M))$，额外空间复杂度为 $O(1)$。