HDU 4920 Matrix multiplication（bitset)

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

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