题目链接：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 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxn = 805; int N, C[maxn][maxn]; bitset
       
         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
        
          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; }