自动搬运

查看原文

来自洛谷，原作者为

	ikka 菜

搬运于2025-08-24 22:01:00，当前版本为作者最后更新于2019-09-30 09:58:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

给你一个大小为$n\times m$的矩阵，矩阵中第$i$行第$j$列的数为$(i-1)m+j$，给你$k$次操作，每次操作指定某一行或某一列乘上一个非负整数，求$k$次操作后，矩阵中所有数的和，对$10^9+7$取模。

$n,m\leq 10^6,k\leq 10^4$

Solution

首先注意到$n,m$都很大，直接算出这个矩阵是不可能的。因为这题只有对一整行或一整列的操作，所以可以考虑对一整行和一整列计算答案。

然后可以注意到，只需要求出最后矩阵中数字的和，所以这个操作的顺序是无所谓的，可以把操作排序，先处理行操作，然后处理出每一列的数字和，记作$f[i]$，这样对于后面的列操作就成了在$f[i]$上的一个一维的问题，这个复杂度就可以接受。

然后考虑如何处理行操作。可以把每一行乘的数算出来，记作$v[i]$，然后就可以把$f[i]$算出来，不过朴素的算法算$f[i]$还是$O(nm)$的，要搞一个优化。

原矩阵的一行中，后一个数等于前一个数$+1$，考虑到这个性质，你一拍大腿，发现这个$f[i]$是可以递推的！根据小学所学的乘法分配律，显然我们可以得到$f[i] = f[i-1] + \sum_{i=1}^{n} v[i]$，后面的这个和式可以$O(n)$预处理得到，$f[1]$也可以$O(n)$计算，所以，$f[i]$就可以$O(m)$递推出来了。

这之后你就可以对着一维问题乱搞了。

时间复杂度$O(n)$。

Code

#include <cstdio>
#include <algorithm>
const int maxn = 1000010;
const int maxk = 1010;
const int mod = 1000000007;

int inline pls(int a, int b) { int m = a + b; return m < mod ? m : m - mod; }
int inline dec(int a, int b) { int m = a - b; return m < 0 ? m + mod : m; }
int inline mul(int a, int b) { return 1ll * a * b % mod; }

struct qry {
  int o, x, y;
  bool operator < (const qry &rhs) const {
    return o < rhs.o;
  }
} a[maxk];

int val[maxn], f[maxn];

int main() {
  static int n, m, k, x, y, s, ans; char opt[2];
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= k; ++i) {
    scanf("%s%d%d", opt, &x, &y);
    a[i] = (qry){*opt == 'S', x, y};
  }
  std::sort(a + 1, a + k + 1);
  for (int i = 1; i <= n; ++i) val[i] = 1;
  for (int i = 1; i <= k; ++i) {
    if (a[i].o) break;
    val[a[i].x] = mul(val[a[i].x], a[i].y);
  }
  for (int i = 1; i <= n; ++i) s = pls(s, val[i]);
  for (int i = 1; i <= n; ++i) f[1] = pls(f[1], mul(pls(mul(m, i - 1), 1), val[i]));
  for (int i = 2; i <= m; ++i) f[i] = pls(f[i - 1], s);
  for (int i = 1; i <= k; ++i) {
    if (!a[i].o) continue;
    f[a[i].x] = mul(f[a[i].x], a[i].y);
  }
  for (int i = 1; i <= m; ++i) ans = pls(ans, f[i]);
  printf("%d\n", ans);
  return 0;
}