矩阵求和

GitHub跳转原题关系图返回列表

把 C[i][j] 恒等变形为 (A[i]+i)(B[j]+j),行列最大值即可分离,再用单调栈统计每个元素被各长度窗口计入的次数、差分还原全部 F[k]。

OJ: roj

题目 ID: 1749

难度:提高+/省选-

标签:单调栈数学计数python

创建: 2026-10-07 21:10

更新: 2026-10-07 21:10

形式化题目

给定长度 nn 的数组 A,BA, B(下标从 11 起,0⩽Ai,Bi⩽1070 \leqslant A_i, B_i \leqslant 10^7),用它们生成 n×nn \times n 矩阵

Cij=AiBj+iBj+Aij+ij.C_{ij} = A_i B_j + i B_j + A_i j + i j .

一个矩阵的价值定义为其中最大元素的值。对每个 k=1,2,…,nk = 1, 2, \dots, n,定义 F[k]F[k] 为

CC 中所有 k×kk \times k 连续子矩阵(行窗 [i,i+k−1][i, i+k-1]、列窗 [j,j+k−1][j, j+k-1])的价值之和。

求 F[1],F[2],…,F[n]F[1], F[2], \dots, F[n] 对 109+710^9+7 取模的结果。

n⩽100000n \leqslant 100000。暴力枚举每个 kk 的每个子矩阵是 O(n4)O(n^4) 级别的,必须另找结构。

正解

思路

第一步:把矩阵"拆开"。 题面给的 CijC_{ij} 四项看起来毫无规律,但把 AiA_i 的两项、BjB_j 的两项各归一类就能看出它是完全平方的展开形式:

Cij=AiBj+iBj+Aij+ij=(Ai+i)(Bj+j).C_{ij} = A_iB_j + iB_j + A_i j + ij = (A_i + i)(B_j + j).

令 Xi=Ai+iX_i = A_i + i、Yj=Bj+jY_j = B_j + j,则 Cij=XiYjC_{ij} = X_i Y_j,整个矩阵是一个"外积矩阵"。

第二步:行列分离。 题目保证 Ai,Bi⩾0A_i, B_i \geqslant 0 且下标从 11 起,所以 Xi,Yj⩾1X_i, Y_j \geqslant 1 恒正。正数乘积有一个关键性质:

max⁡p∈行窗max⁡q∈列窗XpYq=(max⁡p∈行窗Xp)⋅(max⁡q∈列窗Yq).\max_{p \in \text{行窗}} \max_{q \in \text{列窗}} X_p Y_q = \Big(\max_{p \in \text{行窗}} X_p\Big) \cdot \Big(\max_{q \in \text{列窗}} Y_q\Big).

两个因子都取最大时乘积才最大,行与列的选择互不干扰。于是

F[k]=(∑i=1n−k+1max⁡(Xi,…,Xi+k−1))×(∑j=1n−k+1max⁡(Yj,…,Yj+k−1))=SX[k]⋅SY[k].F[k] = \Big(\sum_{i=1}^{n-k+1} \max(X_i, \dots, X_{i+k-1})\Big) \times \Big(\sum_{j=1}^{n-k+1} \max(Y_j, \dots, Y_{j+k-1})\Big) = S_X[k] \cdot S_Y[k].

问题化归为一个经典子问题:给定数组,对每个 kk 求所有长度 kk 子区间最大值之和,两个数组各做一遍即可。

第三步:S[k]S[k] 的贡献计数。 直接对每个 kk 单调队列扫一遍是 O(n2)O(n^2),n=105n = 10^5 时是 101010^{10},不行。改换视角:不看"区间"看"元素",让每个元素去统计自己当了多少次区间最大值。

为了不重不漏,规定每个区间由它最靠右的那个最大值代表。用单调栈求出

  • L[i]L[i]:ii 左侧最近的满足 XL[i]>XiX_{L[i]} > X_i 的位置(严格大于,不存在则为 00);
  • R[i]R[i]:ii 右侧最近的满足 XR[i]⩾XiX_{R[i]} \geqslant X_i 的位置(大于等于,不存在则为 n+1n+1)。

这两侧口径一严一松,正好保证"每个区间恰有一个最右最大值"。记 a=i−L[i]a = i - L[i]、b=R[i]−ib = R[i] - i,那么 ii 是区间 [s,e][s, e] 的最右最大值当且仅当

L[i]<s⩽i⩽e<R[i],L[i] < s \leqslant i \leqslant e < R[i],

也就是 ss 有 aa 种选择、ee 有 bb 种选择。现在数长度恰为 kk 的区间个数:设 e=i+re = i + r(0⩽r<b0 \leqslant r < b),则要求 s=e−k+1⩾i−a+1s = e - k + 1 \geqslant i - a + 1,即 r⩾k−ar \geqslant k - a;同时 r⩽k−1r \leqslant k - 1 与 r⩽b−1r \leqslant b - 1 也要满足。综合起来

cnti(k)=#{r:max⁡(0,k−a)⩽r⩽min⁡(k−1, b−1)}=min⁡(k, a, b, a+b−k),\mathrm{cnt}_i(k) = \#\{r : \max(0, k-a) \leqslant r \leqslant \min(k-1,\, b-1)\} = \min(k,\, a,\, b,\, a+b-k),

要求 1⩽k⩽a+b−11 \leqslant k \leqslant a+b-1,否则为 00。

第四步:把 cnti(k)\mathrm{cnt}_i(k) 变成 O(1)O(1) 次区间加。 设 m=min⁡(a,b)m = \min(a, b)、M=max⁡(a,b)M = \max(a, b),上式关于 kk 分三段是线性的:

cnti(k)={k,1⩽k⩽m,m,m<k⩽M,a+b−k,M<k⩽a+b−1.\mathrm{cnt}_i(k) = \begin{cases} k, & 1 \leqslant k \leqslant m,\\ m, & m < k \leqslant M,\\ a + b - k, & M < k \leqslant a+b-1.\end{cases}

对固定的 ii 这是三条"关于 kk 的直线",而我们要的是所有 ii 叠加后在每个 kk 上的值。开两个差分数组:

  • slope[k]:kk 的系数之和;
  • const[k]:常数项之和。

于是最终 S[k]=(slope 的前缀和)⋅k+(const 的前缀和)S[k] = \big(\text{slope 的前缀和}\big) \cdot k + \big(\text{const 的前缀和}\big)。第一段斜率 +1+1、截距 00,只需 slope 区间加 XiX_i;第二段斜率 00、截距 mm,只需 const 区间加 Xi⋅mX_i \cdot m;第三段斜率 −1-1、截距 a+ba+b,则 slope 区间加 −Xi-X_i、const 区间加 Xi⋅(a+b)X_i \cdot (a+b)。每个 ii 只做 O(1)O(1) 次区间加,最后前缀和扫一遍就得到全部 kk 的答案。

注意全程可以在模 109+710^9+7 下运算:SX[k]S_X[k]、SY[k]S_Y[k] 都只需知道模值,乘积 SX[k]⋅SY[k] mod (109+7)S_X[k] \cdot S_Y[k] \bmod (10^9+7) 就是 F[k]F[k]——模运算对加法、乘法封闭,不必担心"最大值之和"与取模的交换性(取模只作用在最终求和结果上,不参与比较)。

下面用样例展示前两步的分离:

flowchart LR
    A["A = 4 1 9"] --> X["X = A_i + i<br/>= 5 3 12"]
    B["B = 3 4 1"] --> Y["Y = B_j + j<br/>= 4 6 4"]
    X --> SX["S_X = 20, 17, 12"]
    Y --> SY["S_Y = 14, 12, 6"]
    SX --> F["F = 20*14, 17*12, 12*6<br/>= 280, 204, 72"]
    SY --> F

以样例的 k=2k=2 为例验证计数口径:X=[5,3,12]X = [5, 3, 12] 的长度 22 窗口是 [5,3][5,3] 与 [3,12][3,12],最大值 5+12=175 + 12 = 17;Y=[4,6,4]Y = [4, 6, 4] 的两个窗口最大值是 6+6=126 + 6 = 12(两个窗口最大值都是 66,因为 Y2=6Y_2 = 6 同时属于它们);17×12=20417 \times 12 = 204,与样例一致。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 21:05
# update_at: 2026-10-07 21:05

import sys

MOD = 10 ** 9 + 7  # 题目要求的取模数


def add_range(d: list[int], l: int, r: int, v: int) -> None:
    """在差分数组 d 的闭区间 [l, r] 上整体加 v;l > r 时是空区间,直接跳过。"""
    if l > r or v == 0:
        return
    d[l] = (d[l] + v) % MOD
    d[r + 1] = (d[r + 1] - v) % MOD


def window_max_sum(arr: list[int]) -> list[int]:
    """回答:arr 的所有长度 k 子区间的最大值之和是多少(k = 1..n,对 MOD 取模)。

    每个区间只由它「最右边的那个最大值」代表。下标 i 是区间 [s, e] 的最右最大值,
    当且仅当 L[i] < s <= i <= e < R[i],其中 L 是左侧最近的严格更大位置、
    R 是右侧最近的大于等于位置。于是 arr[i] 被长度 k 的区间计入
        cnt(k) = min(k, a, b, a+b-k),a = i - L[i],b = R[i] - i,
    它关于 k 分三段线性,用两个差分数组一次求出全部 k 的答案。
    """
    n = len(arr) - 1
    lef = [0] * (n + 1)
    rig = [n + 1] * (n + 2)

    stk: list[int] = []  # 单调递减栈,存下标
    for i in range(1, n + 1):
        while stk and arr[stk[-1]] <= arr[i]:
            stk.pop()
        lef[i] = stk[-1] if stk else 0
        stk.append(i)

    stk.clear()
    for i in range(n, 0, -1):
        while stk and arr[stk[-1]] < arr[i]:
            stk.pop()
        rig[i] = stk[-1] if stk else n + 1
        stk.append(i)

    slope = [0] * (n + 3)    # 差分:k 的系数
    const = [0] * (n + 3)    # 差分:常数项
    for i in range(1, n + 1):
        v = arr[i] % MOD
        a, b = i - lef[i], rig[i] - i
        small, big = min(a, b), max(a, b)
        last = a + b - 1                                   # cnt(k) > 0 的最大 k
        add_range(slope, 1, small, v)                      # cnt = k
        add_range(const, small + 1, big, v * small % MOD)  # cnt = small
        add_range(const, big + 1, last, v * (a + b) % MOD)  # cnt = a+b-k
        add_range(slope, big + 1, last, (-v) % MOD)

    out = [0] * (n + 1)
    s1 = s2 = 0  # 斜率前缀、常数前缀
    for k in range(1, n + 1):
        s1 = (s1 + slope[k]) % MOD
        s2 = (s2 + const[k]) % MOD
        out[k] = (s1 * k + s2) % MOD
    return out


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]
    b = [next(data) for _ in range(n)]

    # C[i][j] = (A[i] + i) * (B[j] + j),两因子恒正,故行列最大值可分开算
    x = [0] + [v + i for i, v in enumerate(a, 1)]
    y = [0] + [v + i for i, v in enumerate(b, 1)]

    sx = window_max_sum(x)
    sy = window_max_sum(y)

    ans = [sx[k] * sy[k] % MOD for k in range(1, n + 1)]
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    solve()

C++ 版:

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 21:05
 * update_at: 2026-10-07 21:05
 *
 * 一本通 1749《矩阵求和》
 *
 * 关键恒等变换:C[i][j] = A[i]*B[j] + i*B[j] + A[i]*j + i*j = (A[i]+i)*(B[j]+j)。
 * 令 X[i] = A[i]+i, Y[j] = B[j]+j,由于 0 <= A,B 且下标从 1 起,X、Y 恒正,
 * 于是 k*k 子矩阵的最大值 = 行窗 X 最大值 * 列窗 Y 最大值,行列互不影响:
 *     F[k] = (所有长度 k 的 X 窗最大值之和) * (所有长度 k 的 Y 窗最大值之和)。
 * 剩下的子问题「所有长度 k 子区间最大值之和」用单调栈统计每个元素作为
 * 最右最大值时的贡献区间数,贡献数关于 k 分段线性,用两个差分数组一次求出全部 k。
 * 时间 O(n),空间 O(n)。
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL;
const int MAXN = 100005;

ll a[MAXN], b[MAXN];
ll x[MAXN], y[MAXN];    // x[i] = a[i] + i, y[i] = b[i] + i
int lef[MAXN], rig[MAXN]; // 左侧最近的严格更大位置、右侧最近的大于等于位置
int stk[MAXN];            // 单调栈,存下标
ll slope[MAXN];           // 差分数组:k 的系数
ll constant[MAXN];        // 差分数组:常数项
ll sx[MAXN], sy[MAXN];    // 两个数组的「长度 k 窗最大值之和」

// 对差分数组 d 在区间 [l, r] 上加 v(v 已对 MOD 取模)
void add_range(ll d[], int l, int r, ll v) {
    if (l > r || v == 0) return;
    d[l] = (d[l] + v) % MOD;
    d[r + 1] = (d[r + 1] - v + MOD) % MOD;
}

// 求 arr 所有长度 k 子区间最大值之和,k = 1..n,结果对 MOD 取模写入 out[1..n]
void window_max_sum(ll arr[], int n, ll out[]) {
    // 左侧最近的严格大于 arr[i] 的位置(无则 0)
    int top = 0;
    for (int i = 1; i <= n; i++) {
        while (top > 0 && arr[stk[top]] <= arr[i]) top--;
        lef[i] = (top > 0) ? stk[top] : 0;
        stk[++top] = i;
    }
    // 右侧最近的大于等于 arr[i] 的位置(无则 n+1)
    top = 0;
    for (int i = n; i >= 1; i--) {
        while (top > 0 && arr[stk[top]] < arr[i]) top--;
        rig[i] = (top > 0) ? stk[top] : n + 1;
        stk[++top] = i;
    }

    for (int i = 0; i <= n + 1; i++) {
        slope[i] = 0;
        constant[i] = 0;
    }

    // 记 a = i - lef[i],b = rig[i] - i。arr[i] 恰是区间 [s,e] 的最右最大值
    // 当且仅当 lef[i] < s <= i <= e < rig[i],故它被长度 k 的区间计入的次数
    //     cnt(k) = min(k, a, b, a+b-k)   (1 <= k <= a+b-1)
    // 该函数关于 k 分三段线性:k 段、常数 m 段、a+b-k 段。
    for (int i = 1; i <= n; i++) {
        ll v = arr[i] % MOD;
        int a = i - lef[i];
        int b = rig[i] - i;
        int m = min(a, b);
        int big = max(a, b);
        int last = a + b - 1;              // cnt(k) > 0 的最大 k
        add_range(slope, 1, m, v);                          // cnt = k
        add_range(constant, m + 1, big, v * m % MOD);       // cnt = m
        add_range(constant, big + 1, last, v * ((a + b) % MOD) % MOD); // cnt = a+b-k
        add_range(slope, big + 1, last, (MOD - v) % MOD);
    }

    // 前缀和还原出 f(k) = (斜率前缀) * k + (常数前缀)
    ll s1 = 0, s2 = 0;
    for (int k = 1; k <= n; k++) {
        s1 = (s1 + slope[k]) % MOD;
        s2 = (s2 + constant[k]) % MOD;
        out[k] = (s1 * (k % MOD) + s2) % MOD;
    }
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 1; i <= n; i++) {
        if (scanf("%lld", &a[i]) != 1) return 0;
        x[i] = a[i] + i;
    }
    for (int i = 1; i <= n; i++) {
        if (scanf("%lld", &b[i]) != 1) return 0;
        y[i] = b[i] + i;
    }

    window_max_sum(x, n, sx);
    window_max_sum(y, n, sy);

    for (int k = 1; k <= n; k++) {
        ll ans = sx[k] * sy[k] % MOD;
        if (k < n) printf("%lld ", ans);
        else printf("%lld\n", ans);
    }
    return 0;
}

复杂度

  • 时间:每个数组一次单调栈 O(n)O(n) + 每个位置 O(1)O(1) 次差分区间加 + 一次前缀和,两个数组共 O(n)O(n)。
  • 空间:L,RL, R、栈、两个差分数组与原数组均为 O(n)O(n)。

n=105n = 10^5 时数据量很小,1000 ms1000\ \mathrm{ms} / 128 MB128\ \mathrm{MB} 限制下 C++ 有极大余量。

正确性要点与边界

  1. 正数前提不能省。 若允许 AiA_i 为负,XiX_i 可能非正,"乘积取最大 = 两因子分别取最大"就不成立。本题 Ai,Bi⩾0A_i, B_i \geqslant 0 且 i⩾1i \geqslant 1,故 Xi,Yj⩾1>0X_i, Y_j \geqslant 1 > 0,这一步是合法的。
  2. 去重口径一严一松。 LL 用"严格大于"、RR 用"大于等于",否则大量并列值(例如 A≡B≡107A \equiv B \equiv 10^7 时 XX 严格递增,或 Ai=Bi=107−iA_i = B_i = 10^7 - i 时 X≡107X \equiv 10^7 全相等)会被重复计数或漏计。两处口径写反不会影响题目样例(样例的 XX 无并列),但会在有并列值的数据上算错——实测把两处口径互换后,测试点 3、7、8、10 的答案立即改变,其中点 10(Xi≡107X_i \equiv 10^7 全相等)是最极端的一例。
  3. 差分数组要开到 n+3n+3。 区间右端点可达 a+b−1⩽2n−1a+b-1 \leqslant 2n-1,在 d[r+1] 处会越界写入,数组必须留出余量;同时 add_range 需处理 l>rl > r 的空区间。
  4. 取模位置。 差分区间加时 XiX_i 要先对 109+710^9+7 取模,减法写成加 MODMOD 再取模;const 上的量 Xi⋅(a+b)X_i \cdot (a+b) 中 a+ba+b 可到 2×1052 \times 10^5,XiX_i 可到 1.1×1071.1 \times 10^7,乘积约 2×10122 \times 10^{12},C++ 需用 long long(Python 无此问题)。
  5. 输出格式。 一行 nn 个整数,用空格分隔、行尾换行,注意不要在行末多输出空格(多数判题器容忍,但严格比较的判题器会判错)。

总结

  • 先化简再优化。 四项展开式其实是 (Ai+i)(Bj+j)(A_i+i)(B_j+j),识别出"外积矩阵"后,n×nn \times n 个元素的最大值问题就塌缩成两个一维问题,这是本题最关键的一步,也是唯一需要"看出"的地方。
  • 正数乘积可分离极值。 max⁡(XpYq)=max⁡Xp⋅max⁡Yq\max (X_p Y_q) = \max X_p \cdot \max Y_q 只在两个因子恒正时成立;题面刻意给出 0⩽Ai,Bi0 \leqslant A_i, B_i 正是为了让这一步合法,反过来看也是题面在暗示解法。
  • 从"枚举区间"转向"枚举元素"。 对每个 kk 扫一遍是 O(n2)O(n^2),改让每个元素统计自己被多少个窗口计入,就把 O(n)O(n) 个元素的贡献分别变成 O(1)O(1) 次区间加,这是"所有子区间极值之和"这类题的通用套路。
  • 单调栈的口径决定计数是否唯一。 LL 严格大于、RR 大于等于,才能让每个区间恰有一个"最右最大值"来代表;并列值越多,这个细节越致命。
  • 分段线性函数用差分数组承载。 贡献函数 min⁡(k,a,b,a+b−k)\min(k, a, b, a+b-k) 是"上凸的折线",两段斜率变化 + 一段常数,用 slope / const 两个差分数组即可一次求出全部 kk,不需要任何数据结构。

关于本题数据的说明:仓库素材源中带有测试数据生成脚本(data.py,依赖 cyaron),说明 data/ 下 10 个测试点是由标程自造的,并非官方原始数据;题面也属于网络重建版本。因此上述「分层设计」描述的是本仓库数据的构造意图,出题意图与官方原题可能存在偏差,题解结论以题面公式与数据范围为准(已用 main.cpp / main.py 与全部 10 个测试点逐点比对一致)。