hdu - 4920 - Matrix multiplication（緩存優化+開掛）

hdu - 4920 - Matrix multiplication（緩存優化+開掛）

題意：求兩個n x n的矩陣相乘後模3的結果，n <= 800。

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4920

——>>呀呀。。

1、3層計算的for進行緩存優化，根據CPU的L1級緩存的實現原理，減少緩存的變更。如果每次都計算完一個單元格的結果再計算下一個單元格的結果，那麼被乘矩陣的訪問就會頻繁地更新緩存，使效率很低。。

2、輸入開掛，G++提效500ms+。。

3、對乘法進行剪枝。。

沒有第1個操作，後果是嚴重的。。

n^3的復雜度A過，但，此不是正解。。

#include 
#include 

const int MAXN = 800 + 10;

int n;
int A[MAXN][MAXN], B[MAXN][MAXN], mtRet[MAXN][MAXN];

int ReadInt()
{
    int nRet = 0;
    char cIn;

    while ((cIn = getchar()) >= '0' && cIn <= '9')
    {
        nRet = nRet * 10 + cIn - '0';
    }

    return nRet % 3;
}

void Read()
{
    getchar();
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            A[i][j] = ReadInt();
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            B[i][j] = ReadInt();
        }
    }
}

void Solve()
{
    memset(mtRet, 0, sizeof(mtRet));
    for (int i = 1; i <= n; ++i)
    {
        for (int k = 1; k <= n; ++k)
        {
            if(!A[i][k]) continue;
            for (int j = 1; j <= n; ++j)
            {
                mtRet[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

void Print()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j < n; ++j)
        {
            printf("%d ", mtRet[i][j] % 3);
        }
        printf("%d\n", mtRet[i][n] % 3);
    }
}

int main()
{
    while (scanf("%d", &n) == 1)
    {
        Read();
        Solve();
        Print();
    }
    return 0;
}