题目链接：hdu 4965，题目大意：给你一个 n*k 的矩阵 A 和一个 k*n 的矩阵 B，定义矩阵 C= A*B，然后矩阵 M= C^(n*n)，矩阵中一切元素皆 mod 6，最后求出 M 中所有元素的和。题意很明确了，便赶紧敲了个矩阵快速幂的模板（因为编程的基本功不够还是调试了很久），然后提交后TLE了，改了下细节，加了各种特技，比如输入优化什么的，还是TLE，没办法，只好搜题解，看了别人的题解后才知道原来 A*B 已经是 n*n 的矩阵了，所以（A*B）n*n 的快速幂里的每个乘法都是 n3 级别的了，n 的上限为1000，这样子超时也不奇怪了，怎么办呢，原来是要转化一下：（A*B）n*n= A*(B*A)n*n-1*A，这样子的话，B*A 是 k*k 的矩阵，乘法是 k3 级别的，k<=6，就不会超时了，这个转化果然好厉害！
如果结构体内直接开个数组的话会超内存，要用指向一维数组的指针来 new 才行，不过还是很容易出错：
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define For(i,s,t) for(int i=s; i<=t; ++i)
const int mod= ;
const int maxn= ; struct matrix{
int n,m, (*a)[maxn]= NULL;
matrix(int n=, int m=):n(n),m(m){
a= new int[n+][maxn];
For(i,,n) For(j,,m)
a[i][j]= ;
}
void identity(){
For(i,,n) a[i][i]= ;
}
matrix operator *(const matrix &m2) const {
matrix mul(n,m2.m);
For(i,,n) For(j,,m2.m) For(k,,m)
mul.a[i][j]= (mul.a[i][j]+a[i][k]*m2.a[k][j]%mod)%mod;
return mul;
}
int sum(){
int ans= ;
For(i,,n) For(j,,m)
ans+= a[i][j];
return ans;
}
void clear() { delete[] a; }
}; matrix quick_mod(matrix m2, int p){
matrix ans(m2.n,m2.m);
ans.identity();
while(p){
if(p&) ans= ans*m2;
m2= m2*m2;
p>>=;
}
return ans;
} void read(int &x){
x= ;
char ch= getchar();
while(!isdigit(ch)) ch= getchar();
while(isdigit(ch)){
x= x*+(ch-''+);
ch= getchar();
}
} int main(){
int n,k;
read(n); read(k);
while(){
if(!n || !k) break;
matrix A(n,k), B(k,n), tmp(k,k), C(n,n);
For(i,,n) For(j,,k) read(A.a[i][j]);
For(i,,k) For(j,,n) read(B.a[i][j]);
tmp= B*A;
tmp= quick_mod(tmp,n*n-);
C= A*tmp*B;
printf("%d\n",C.sum());
read(n); read(k);
A.clear();
B.clear();
tmp.clear();
C.clear();
}
return ;
}
用指向一维数组的指针貌似挺耗费内存的，于是改用了二级指针来试下，果然内存和效率都明显有了很大的提高（但好像还是比不上 vector 耶~）：
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define For(i,s,t) for(int i=s; i<=t; ++i)
const int mod= ;
const int maxn= ; struct matrix{
int n,m, **a= NULL;
matrix(int n=, int m=):n(n),m(m){
a= new int *[n+];
For(i,,n) a[i]= new int[m+];
For(i,,n) For(j,,m)
a[i][j]= ;
}
void identity(){
For(i,,n) a[i][i]= ;
}
matrix operator *(const matrix &m2) const {
matrix mul(n,m2.m);
For(i,,n) For(j,,m2.m) For(k,,m)
mul.a[i][j]= (mul.a[i][j]+a[i][k]*m2.a[k][j]%mod)%mod;
return mul;
}
int sum(){
int ans= ;
For(i,,n) For(j,,m)
ans+= a[i][j];
return ans;
}
void clear(){
For(i,,n) delete a[i];
delete a;
a = NULL;
}
}; matrix quick_mod(matrix m2, int p){
matrix ans(m2.n,m2.m);
ans.identity();
while(p){
if(p&) ans= ans*m2;
m2= m2*m2;
p>>=;
}
return ans;
} void read(int &x){
x= ;
char ch= getchar();
while(!isdigit(ch)) ch= getchar();
while(isdigit(ch)){
x= x*+(ch-''+);
ch= getchar();
}
} int main(){
int n,k;
read(n); read(k);
while(){
if(!n || !k) break;
matrix A(n,k), B(k,n), tmp(k,k), C(n,n);
For(i,,n) For(j,,k) read(A.a[i][j]);
For(i,,k) For(j,,n) read(B.a[i][j]);
tmp= B*A;
tmp= quick_mod(tmp,n*n-);
C= A*tmp*B;
printf("%d\n",C.sum());
read(n); read(k);
A.clear();
B.clear();
tmp.clear();
C.clear();
}
return ;
}
后来无意中看到别人的代码用 vector 来代替动态数组就行，不用自己手动 new 和 delete 了，确实方便了好多：
#include<cstdio>
#include<cstring>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
#define For(i,s,t) for(int i=s; i<=t; ++i)
const int mod= ;
const int maxn= ; struct matrix{
int n,m;
vector<vector<int> > a;
matrix(int n=, int m=):n(n),m(m){
a.resize(n+);
For(i,,n) a[i].resize(m+,);
}
void identity(){
For(i,,n) a[i][i]= ;
}
matrix operator *(const matrix &m2) const {
matrix mul(n,m2.m);
For(i,,n) For(j,,m2.m) For(k,,m)
mul.a[i][j]= (mul.a[i][j]+a[i][k]*m2.a[k][j]%mod)%mod;
return mul;
}
int sum(){
int ans= ;
For(i,,n) For(j,,m)
ans+= a[i][j];
return ans;
}
~matrix() {
For(i,,n) a[i].clear();
a.clear();
}
}; matrix quick_mod(matrix m2, int p){
matrix ans(m2.n,m2.m);
ans.identity();
while(p){
if(p&) ans= ans*m2;
m2= m2*m2;
p>>=;
}
return ans;
} void read(int &x){
x= ;
char ch= getchar();
while(!isdigit(ch)) ch= getchar();
while(isdigit(ch)){
x= x*+(ch-''+);
ch= getchar();
}
} int main(){
int n,k;
read(n); read(k);
while(){
if(!n || !k) break;
matrix A(n,k), B(k,n), tmp(k,k), C(n,n);
For(i,,n) For(j,,k) read(A.a[i][j]);
For(i,,k) For(j,,n) read(B.a[i][j]);
tmp= B*A;
tmp= quick_mod(tmp,n*n-);
C= A*tmp*B;
printf("%d\n",C.sum());
read(n); read(k);
}
return ;
}
看来自己曾经引以为傲的矩阵快速幂还差得很远啊~~总之得加把劲了！