题解 P4521 【[COCI2017-2018 Contest4] Automobil 】

· · 题解

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;
}