HDU 4920 Matrix multiplication

题目链接

题意：给定两个矩阵，求这两个矩阵相乘mod 3

思路：没什么好的想法，就把0的位置不考虑。结果就过了。然后看了官方题解，上面是用了bitset这个东西，能够用来存大的二进制数，那么对于行列相乘。事实上就几种情况，遇到0都是0了，1 1得1，2 1，1 2得2，2 2得1。所以仅仅要存下行列1和2存不存在分别表示的二进制数。然后取且bitcount一下的个数，就能够计算出对应的数值了

代码：

暴力：

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline void scanf_(int &num)//无负数

{

    char in;

    while((in = getchar()) > '9' || in < '0') ;

    num = in - '0';

    while(in = getchar(),in >= '0' && in <= '9')

	num *= 10,num += in - '0';

}

const int N = 805;

int n;

int a[N][N], av[N][N], an[N], b[N][N], bv[N][N], bn[N], c[N][N];

int main() {

    while (~scanf("%d", &n)) {

	int num;

	memset(an, 0, sizeof(an));

	memset(bn, 0, sizeof(bn));

	memset(c, 0, sizeof(c));

	for (int i = 0; i < n; i++) {

	    for (int j = 0; j < n; j++) {

		scanf_(num);

		num %= 3;

		if (num == 0) continue;

		av[j][an[j]] = i;

		a[j][an[j]++] = num;

	    }

	}

	for (int i = 0; i < n; i++) {

	    for (int j = 0; j < n; j++) {

		scanf_(num);

		num %= 3;

		if (num == 0) continue;

		bv[i][bn[i]] = j;

		b[i][bn[i]++] = num;

	    }

	}

	for (int i = 0; i < n; i++) {

	    for (int j = 0; j < an[i]; j++) {

		for (int k = 0; k < bn[i]; k++) {

		    int x = av[i][j], y = bv[i][k];

		    c[x][y] = (c[x][y] + a[i][j] * b[i][k]) % 3;

		}

	    }

	}

	for (int i = 0; i < n; i++) {

	    for (int j = 0; j < n - 1; j++)

		printf("%d ", c[i][j]);

	    printf("%d\n", c[i][n - 1]);

	}

    }

    return 0;

}

bitset：

#include <cstdio>

#include <cstring>

#include <string>

#include <bitset>

using namespace std;

const int N = 805;

int n, num;

bitset<800> row[N][2], col[N][2];

int main() {

    while (~scanf("%d", &n)) {

	for (int i = 0; i < n; i++) {

	    row[i][0].reset();

	    row[i][1].reset();

	    col[i][0].reset();

	    col[i][1].reset();

	    for (int j = 0; j < n; j++) {

		scanf("%d", &num);

		if (num % 3 == 1)

		    row[i][0].set(j, 1);

		if (num % 3 == 2)

		    row[i][1].set(j, 1);

	    }

	}

	for (int i = 0; i < n; i++) {

	    for (int j = 0; j < n; j++) {

		scanf("%d", &num);

		if (num % 3 == 1)

		    col[j][0].set(i, 1);

		if (num % 3 == 2)

		    col[j][1].set(i, 1);

	    }

	}

	for (int i = 0; i < n; i++) {

	    for (int j = 0; j < n; j++) {

		int ans = 0;

		ans += (row[i][0]&col[j][0]).count();

		ans += 2 * (row[i][1]&col[j][0]).count() + 2 * (row[i][0]&col[j][1]).count();

		ans += (row[i][1]&col[j][1]).count();

		printf("%d%c", ans % 3, j == n - 1 ?

'\n' : ' ');

	    }

	}

    }

    return 0;

}