hdu 4920 Matrix multiplication(高效)

本文主要是介绍hdu 4920 Matrix multiplication(高效)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：4920 Matrix multiplication

题目大意：给定两个n阶矩阵，求矩阵相乘后模3.

解题思路：因为矩阵模掉3后只有0，1，2三种情况。所以对于矩阵A，记录每一行中1，2的位置，借助bitset。矩阵B中每一列1，2的位置。然后对于结果中每个位置，只要考虑1∗1,1∗2,2∗1，2∗2的个数即可。

#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>using namespace std;
const int maxn = 805;int N, C[maxn][maxn];
bitset<maxn> x[maxn][2], y[maxn][2];void init () {int u;memset(C, 0, sizeof(C));for (int i = 0; i < N; i++) {for (int j = 0; j < 2; j++) {x[i][j].reset();y[i][j].reset();}}for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {scanf("%d", &u);u %= 3;if (u)x[i][u-1].set(j, 1);}}for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {scanf("%d", &u);u %= 3;if (u)y[j][u-1].set(i, 1);}}
}int solve (int u, int v) {int ret = 0;for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {bitset<maxn> k = x[u][i]&y[v][j];ret = (ret + (i+1)*(j+1)*k.count()) % 3;}}return ret;
}int main () {while (scanf("%d", &N) == 1) {init();for (int i = 0; i < N; i++) {printf("%d", solve(i, 0));for (int j = 1; j < N; j++)printf(" %d", solve(i, j));printf("\n");}}return 0;
}

这篇关于hdu 4920 Matrix multiplication(高效)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---