题意很简单，就是两个大矩阵相乘，然后求乘积。
用 Strassen算法 的话，当N的规模达到100左右就会*了
况且输入的数据范围可达到800，如果变量还不用全局变量的话连内存开辟都开不出来
#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <stdio.h>
#define ll long long
using namespace std; const int N=; //常量N用来定义矩阵的大小
int A[N][N],B[N][N],C[N][N]; //定义三个矩阵A,B,C
int A11[N][N],A12[N][N],A21[N][N],A22[N][N];
int B11[N][N],B12[N][N],B21[N][N],B22[N][N];
int C11[N][N],C12[N][N],C21[N][N],C22[N][N];
int M1[N][N],M2[N][N],M3[N][N],M4[N][N],M5[N][N],M6[N][N],M7[N][N];
int AA[N][N],BB[N][N],MM1[N][N],MM2[N][N]; void input(int n,int p[][N]) //矩阵输入函数
{
int i,j; for(i=;i<n;i++)
{
for(j=;j<n;j++)
cin>>p[i][j];
p[i][j] %= ;
}
} void output(int n,int C[][N]) //据矩阵输出函数
{
int i,j;
for(i=;i<n;i++)
{ for(j=;j<n;j++)
cout<<C[i][j]<<" ";
cout<<endl;
} } void MATRIX_MULTIPLY(int A[][N],int B[][N],int C[][N]) //按通常的矩阵乘法计算C=AB的子算法(仅做2阶)
{
int i,j,t;
for(i=;i<;i++) //计算A*B-->C
for(j=;j<;j++)
{
C[i][j]=; //计算完一个C[i][j]，C[i][j]应重新赋值为零
for(t=;t<;t++)
C[i][j]=(int)(C[i][j]+A[i][t]*B[t][j]+(int))%(int);
}
} void MATRIX_ADD(int n,int X[][N],int Y[][N],int Z[][N]) //矩阵加法函数X+Y—>Z
{
int i,j;
for(i=;i<n;i++)
for(j=;j<n;j++)
Z[i][j]=(X[i][j]+Y[i][j]+(int))%(int);
} void MATRIX_SUB(int n,int X[][N],int Y[][N],int Z[][N]) //矩阵减法函数X-Y—>Z
{
int i,j;
for(i=;i<n;i++)
for(j=;j<n;j++)
Z[i][j]=(X[i][j]-Y[i][j]+(int))%(int); } void STRASSEN(int n,int A[][N],int B[][N],int C[][N]) //STRASSEN函数（递归）
{ int i,j;//,x; if (n==)
MATRIX_MULTIPLY(A,B,C);//按通常的矩阵乘法计算C=AB的子算法(仅做2阶)
else
{
for(i=;i<n/;i++)
for(j=;j<n/;j++) {
A11[i][j]=A[i][j];
A12[i][j]=A[i][j+n/];
A21[i][j]=A[i+n/][j];
A22[i][j]=A[i+n/][j+n/];
B11[i][j]=B[i][j];
B12[i][j]=B[i][j+n/];
B21[i][j]=B[i+n/][j];
B22[i][j]=B[i+n/][j+n/];
} //将矩阵A和B式分为四块 MATRIX_SUB(n/,B12,B22,BB);
STRASSEN(n/,A11,BB,M1);//M1=A11(B12-B22) MATRIX_ADD(n/,A11,A12,AA);
STRASSEN(n/,AA,B22,M2);//M2=(A11+A12)B22 MATRIX_ADD(n/,A21,A22,AA);
STRASSEN(n/,AA,B11,M3);//M3=(A21+A22)B11 MATRIX_SUB(n/,B21,B11,BB);
STRASSEN(n/,A22,BB,M4);//M4=A22(B21-B11) MATRIX_ADD(n/,A11,A22,AA);
MATRIX_ADD(n/,B11,B22,BB);
STRASSEN(n/,AA,BB,M5);//M5=(A11+A22)(B11+B22) MATRIX_SUB(n/,A12,A22,AA);
MATRIX_SUB(n/,B21,B22,BB);
STRASSEN(n/,AA,BB,M6);//M6=(A12-A22)(B21+B22) MATRIX_SUB(n/,A11,A21,AA);
MATRIX_SUB(n/,B11,B12,BB);
STRASSEN(n/,AA,BB,M7);//M7=(A11-A21)(B11+B12)
//计算M1,M2,M3,M4,M5,M6,M7（递归部分） MATRIX_ADD(N/,M5,M4,MM1);
MATRIX_SUB(N/,M2,M6,MM2);
MATRIX_SUB(N/,MM1,MM2,C11);//C11=M5+M4-M2+M6 MATRIX_ADD(N/,M1,M2,C12);//C12=M1+M2 MATRIX_ADD(N/,M3,M4,C21);//C21=M3+M4 MATRIX_ADD(N/,M5,M1,MM1);
MATRIX_ADD(N/,M3,M7,MM2);
MATRIX_SUB(N/,MM1,MM2,C22);//C22=M5+M1-M3-M7 for(i=;i<n/;i++)
for(j=;j<n/;j++)
{
C[i][j]=C11[i][j];
C[i][j+n/]=C12[i][j];
C[i+n/][j]=C21[i][j];
C[i+n/][j+n/]=C22[i][j];
} //计算结果送回C[N][N] } } int main()
{
int num;
int i,j,k,r;
while(scanf("%d",&num)!=EOF)
{
if(num % == )
{
input(num,A);
input(num,B); //录入数组 STRASSEN(num,A,B,C); //调用STRASSEN函数计算 output(num,C); //输出计算结果
}
else
{
for(i=; i<num; i++)
for(j=; j<num; j++)
cin >> A[i][j];
A[i][j] %= ;
//scanf("%d",&A[i][j]);
for(i=; i<num; i++)
for(j=; j<num; j++)
cin >> B[i][j];
B[i][j] %= ;
//scanf("%d",&B[i][j]);
for(i=;i<num;++i)
for(k=;k<num;++k)
{
r=A[i][k];
for(j=;j<num;++j)
C[i][j]=(C[i][j]+r*B[k][j])%;
}
for(i=; i<num; i++)
{
for(j=; j<num; j++)
cout << C[i][j] << ' ';
//printf("%d ",C[i][j]);
//printf("\n");
cout << endl;
}
}
}
return ;
}
Stack Over Flow Code
所有只能考虑一开始肯定会TLE的朴素算法。
想到结果矩阵中只能有三个数，0，1，2
如果存在大量的0，那么就是一个稀疏矩阵，关于稀疏矩阵，我想到：
只需要在第二层循环内，碰到当然数为0则跳过，因为计算结果肯定为0
提交上去。
TLE.....................ORZ
于是开始思考是不是算法的问题，感觉不太科学，过的人也很多，不会太难把。
一直跪到了比赛结束，题说别人也是对稀疏矩阵优化九过了，我在检查了下代码。
发现了一个至关重要的问题，就是我在大规模数据输入输出的时候使用了cin 和 cout
不多说了，贴后来AC的代码：
#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <stdio.h>
#define ll long long
using namespace std; const int N=; //常量N用来定义矩阵的大小
int A[N][N],B[N][N],C[N][N]; //定义三个矩阵A,B,C
int main(){
int num;
int i,j,k,r;
while(scanf("%d",&num)!=EOF){
memset(C, , sizeof(C));
for(i=; i<num; i++){
for(j=; j<num; j++){
scanf("%d",&A[i][j]);
A[i][j] %= ;
}
}
for(i=; i<num; ++i){
for(j=; j<num; ++j){
scanf("%d",&B[i][j]);
B[i][j] %= ;
}
}
for(i=;i<num;++i){
for(k=;k<num;++k){
if(A[i][k] == ){
continue;
}
for(j=;j<num;++j)
C[i][j]=(C[i][j]+A[i][k]*B[k][j])%;
}
}
for(i=; i<num; i++){
for(j=; j<num; j++){
printf("%d",C[i][j]);
if(j != num -) printf(" ");
}
printf("\n");
}
}
return ;
}