Description

给定一个 n×mn \times m 的矩阵，一共 kk 次操作，在相应的行或者列上乘上一个数，求这 kk 次操作后的和，答案对 109+710^9 + 7 取模。

这里给出一种复杂度仅为 O(k)O(k) 的做法。

Solution

我们令 rowirow_i 表示矩阵第 ii 行被乘上的系数，colicol_i 表示矩阵第 ii 列被乘上的系数，显然一开始均为 11。

根据题意不难发现，矩阵中的权值 Ai,jA_{i, j} 最后的值将为这一行被乘的总积再乘上这一列被乘的总积。由此可以得出答案：

ans=∑i=1n∑j=1mAi,j×rowi×colj\begin{align*} ans &= \sum_{i = 1}^{n}\sum_{j = 1}^{m} A_{i, j} \times row_i \times col_j \end{align*}

由于 Ai,jA_{i, j} 的初值与其位置有关，我们再进行参数分离，可以得到：

ans=∑i=1n∑j=1m((i−1)×m+j)×rowi×colj=∑i=1nrowi×(∑j=1mj×colj+∑j=1m(i−1)×m×colj)=∑i=1nrowi×(i−1)×m×∑j=1mcolj+∑i=1nrowi×∑j=1mj×colj\begin{align*} ans &= \sum_{i = 1}^{n}\sum_{j = 1}^{m} \left( \left (i - 1 \right ) \times m + j \right ) \times row_i \times col_j \\ &= \sum_{i = 1}^{n}row_i \times \left ( \sum_{j = 1}^{m}j \times col_j + \sum_{j = 1}^{m} \left( i - 1\right) \times m \times col_j \right)\\ &= \sum_{i = 1}^{n}row_i \times (i - 1) \times m \times \sum_{j = 1}^{m}col_j + \sum_{i = 1} ^ {n}row_i \times \sum_{j = 1}^{m}j \times col_j \\ \end{align*}

不难发现我们每次可以 O(1) 的修改 rowirow_i 和 colicol_i 的值，最后行列各跑一遍，根据上式算出答案。

时间复杂度为 O(n+m+k)O(n + m + k)。

Code

代码中： sum1←∑i=1mcolisum1 \leftarrow \textstyle {\sum_{i = 1}^{m} col_i}，sum2←∑i=1mi×colisum2 \leftarrow \textstyle \sum_{i = 1}^{m}i \times col_i。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
signed main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= max(n, m); i ++) tagr[i] = tags[i] = 1;
    while (k --)
    {
        char opt; int x, y; cin >> opt >> x >> y;
        if (opt == 'R') tagr[x] = tagr[x] * y % mod;
        else tags[x] = tags[x] * y % mod;
    }
    int sum1 = 0, sum2 = 0, ans = 0;
    for (int i = 1; i <= m; i ++)
        sum1 = (sum1 + tags[i]) % mod, sum2 = (sum2 + tags[i] % mod * i) % mod;
    for (int i = 1; i <= n; i ++)
        ans = (ans + tagr[i] * (i - 1) % mod * m % mod * sum1 % mod + tagr[i] * sum2 % mod) % mod;
    cout << ans << '\n';
    return 0;
}

Extra

如果 n,m≤109n,m \le 10^9，k≤106k \le 10^6 ，应该如何做呢？

显然时间会超时，而且数组也存不下。

注意到 kk 仍旧是可以接受的范围，而每次只会修改一行或者一列，即这个大型矩阵被修改的行列数上界为 kk， 我们仅仅记录好被修改过的行列，预处理出剩下的点数，每次修改时在线更新 sum1sum1 和 sum2sum2 的值，即可做到 O(1)O(1) 的处理。

此处代码以 unordered_map 进行记录，时间复杂度为 O(k)O(k)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
LL n, m, k;
unordered_map<LL, LL> mpr, mps;
LL row1, row2, col1, col2;

// row1 = \sigma{tagr_i}   row2 = \sigma{tagr_i * (i - 1)}
// col1 = \sigma{tags_i}   col2 = \sigma{tags_i * i}

int main()
{
    cin >> n >> m >> k;
    row1 = n, row2 = (n - 1) * n / 2 % mod;
    col1 = m, col2 = (m + 1) * m / 2 % mod;

    while (k --)
    {
        char opt; int x, y; cin >> opt >> x >> y;
        if (opt == 'R')
        {
            if (!mpr.count(x)) mpr[x] = 1LL;
            row1 = (row1 + mpr[x] * (y - 1 + mod) % mod) % mod;
            row2 = (row2 + mpr[x] * (y - 1 + mod) % mod * (x - 1) % mod) % mod;
            mpr[x] = mpr[x] * y % mod;
        }
        else
        {
            if (!mps.count(x)) mps[x] = 1LL;
            col1 = (col1 + mps[x] * (y - 1 + mod) % mod) % mod;
            col2 = (col2 + mps[x] * (y - 1 + mod) % mod * x % mod) % mod;
            mps[x] = mps[x] * y % mod;
        }
    }
    cout << (row2 * m % mod * col1 % mod + row1 * col2 % mod) % mod << '\n';
    return 0;
}