hdu 4965 Fast Matrix Calculation【マトリックス高速べき乗テンプレート】
この問題は,ある行列を変換乗算するなど,2つの行列を乗算する順序を変え,行列の高速べき乗で解くだけでよい.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define N 1010
using namespace std;
const int mod=6;
int** mul(int** A,int** B,int n,int m,int l)//A n*m ,B m*l
{
int **t=new int*[n];
for(int i=0;i<n;i++)
t[i]=new int[l];
for(int i=0;i<n;i++)
for(int j=0;j<l;j++){
t[i][j]=0;
for(int k=0;k<m;k++)
t[i][j]=(t[i][j]+A[i][k]*B[k][j])%mod;
}
return t;
}
int** expo(int **p,int k,int n)//P n*n ,k k
{
if(k==1) return p;
int **e=new int*[n];
for(int i=0;i<n;i++)
e[i]=new int[n];
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
e[i][j] = (i == j);
while(k)
{
if(k&1)
e=mul(e,p,n,n,n);
p=mul(p,p,n,n,n);
k>>=1;
}
return e;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("D:/in.txt","r",stdin);
//freopen("D:/my.txt","w",stdout);
#endif
int NN,K;
while(~scanf("%d%d",&NN,&K)&&(NN||K))
{
int **a=new int*[NN];
for(int i=0;i<NN;i++)
a[i]=new int[K];
int **b=new int*[K];
for(int i=0;i<NN;i++)
b[i]=new int[NN];
int **c;
for(int i=0;i<NN;i++)
for(int j=0;j<K;j++)
scanf("%d",&a[i][j]);
for(int i=0;i<K;i++)
for(int j=0;j<NN;j++)
scanf("%d",&b[i][j]);
c=mul(b,a,K,NN,K);
int temp=NN*NN-1;
c=expo(c,temp,K);
c=mul(a,c,NN,K,K);
c=mul(c,b,NN,K,NN);
int ans=0;
for(int i=0;i<NN;i++)
for(int j=0;j<NN;j++)
ans+=c[i][j];
printf("%d
",ans);
}
return 0;
}