CCPC-Wannafly Camp #5 A 矩阵乘法【分块暴力】

题目大意，给一个 $4096\ast 64$4096∗64的矩阵 A和一个 $64\ast 4096$64∗4096的01阵B，进行矩阵乘法 最后得出异或值，

如果我们直接用 $4096\ast 4096\ast 64\approx 1e9$4096∗4096∗64≈1e9 很显然会T，因为矩阵B是一个01阵，所以我们把矩阵B的每一列划分成八份，这样这个01阵的某一列的某一个划分，一定可以表示成 $0-255$0−255中间的某一个数字，因此，我们只要预处理 A，同样的把A中的每一列都划分成八分，然后与 $0-255$0−255分别预处理，这样的话，就可以得到A中的每一块与0~255这些数所代表的01组合相乘的结果，这样的空间复杂度是 $4096\ast 8\ast 256$4096∗8∗256 时间复杂度是 $4096\ast 64\ast 256$4096∗64∗256 ，然后A*B 就相当于每一个分块相乘，就可以解决此问题，分块相乘的复杂度应该为 $4096\ast 4096\ast 8$4096∗4096∗8

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
const int maxn=4096+50;
int n,m,p;
int a[maxn][80];
char s[maxn][80];
int b[maxn][80];
int Bp[10][maxn];
int Ap[maxn][10][260];
int c[maxn][maxn];
int main()
{
    scanf("%d%d%d",&n,&p,&m);
    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[i]);
        for(int j=0;j<p;j++)
        {
            b[i][j]=s[i][j]-'0';
        }
    }
    p =(p-1)/8+1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<p;j++)
        {
           int base = 8*j;
           for(int k=0;k<256;k++)
           {
               for(int l=0;l<=7;l++)
               {
                   if(k&(1<<l)) Ap[i][j][k]+=a[i][base+l];
               }
           }
        }
    }
    for(int j=0;j<=m-1;j++)
    {
        for(int i=0;i<p;i++)
        {
           int base = 8*i;
           for(int k =0;k<=7;k++)
           {
               Bp[i][j]+=b[j][base+k]<<k;
           }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<p;j++)
        {
            for(int k=0;k<m;k++)
            {
                c[i][k]+=Ap[i][j][Bp[j][k]];
            }
        }
    }
    int ans =0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            ans ^=c[i][j];
        }
    }
    printf("%d\n",ans);
        return 0;
    }

我们这里之前多写了一个循环，去处理01串，结果T了，所以我们要随时随地减少不必要的循环。