NowCoder 202A – 矩阵乘法 (分块)

呜呜呜这才第三道水题我就不会做了。

Table of Contents

题意

给你$N \times P$和$P \times M$的两个矩阵A与B,其中B是二进制矩阵。求$A \times B$的所有元素的异或和。

数据范围

  • $2 \le N, M \le 2048$
  • $1 \le P \le 64$
  • $0 \le A_{ij} \le 65536$

思路

呜呜呜这数据范围这么大做屁啊!如果直接计算$C$的话需要$2^{48} $次运算怎么可能跑得过啊

想想异或运算有没有什么特别的,没有

STFW看看有没有什么快速算矩阵的方法,没有

群里问大佬,大佬说的听不懂,僵

然后Bing搜了个原题出来……

简单地说就是预处理这个矩阵来使得乘法运算的次数大幅度减少,那么在$O(NPM)$的复杂度下能够卡过去。怎么处理呢?考虑到$B$是一个二进制矩阵,$A_i$与$B_j$的相乘的结果代表$A_i$中对应列元素的和。如果直接预处理需要考虑$2^{64}$种和的情况,根本不行。

然后就可以用神奇的分块了,每$\sqrt{P} = 8$个$A_{ij}$分为一块,那么只需要处理$2^{10} \times 8 \times 2^8 = 2 \times 10^6$种和就可以了。对于每一个$C_{ij}$,只需要对对应的分块和进行至多8次加法即可求出。

总时间复杂度为$$O(N \times P \times2^8)+O(MP)+O(NM\sqrt{P})+O(NM).$$

代码

#include <bits/stdc++.h>
using namespace std;

int n = 0, p = 0, m = 0, bk = 0;
int a[4200][70] = {};
int b[4200][70] = {};
int c[4200][4200] = {};
int apre[4200][10][260] = {};
int bpre[4200][10] = {};
char s[100] = {};

void pre() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < bk; ++j) {
      for (int k = 0; k < 256; ++k) {
        for (int p = 0; p < 8; ++p) {
          if ((k >> p) & 1) {
            apre[i][j][k] += a[i][(j << 3) + p];
          }
        }
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < bk; ++j) {
      for (int p = 0; p < 8; ++p) {
        bpre[i][j] += b[i][(j << 3) + p] << p;
      }
    }
  }
}

int getAns() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      for (int p = 0; p < bk; ++p) {
        c[i][j] += apre[i][p][bpre[j][p]];
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j= 0; j < m; ++j) {
      ans ^= c[i][j];
    }
  }
  return ans;
}

int main() {
  scanf("%d%d%d", &n, &p, &m), bk = ((p - 1) >> 3) + 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < p; ++j) {
      scanf("%x", &a[i][j]);
    }
  }
  for (int i = 0; i < m; ++i) {
    scanf("%s", s);
    for (int j = 0; j < p; ++j) {
      b[i][j] = s[j] - '0';
    }
  }
  pre();
  printf("%d\n", getAns());
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注