矩阵快速幂

对于n方阵的矩阵快速幂

#include
#include

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

vector > mul(vector > a,vector > b)
{
	vector > s; 
	for(int i = 0 ; i < a.size() ; i ++){
		vector mq;
		
		for(int j = 0 ; j < a.size() ; j ++){
			int sum = 0;
			for(int k = 0 ; k < a.size() ; k ++){
				sum = (0ll+sum%mod + 1ll*a[i][k]*b[k][j]%mod)%mod;
			}
			mq.push_back(sum);		
		}
		s.push_back(mq);
	}
	return s;
}

vector > binpow(vector > a , ll k)
{
	//cout<
	vector > c(a.size(),vector (a.size()));
	for(int i = 0 ; i < a.size() ; i ++) c[i][i] = 1;
	while(k){
		if(k & 1) c = mul(c,a);
		a = mul(a,a);
		k /= 2;
	}
	return c;
}

void solve()
{
	int n;ll m;
	scanf("%d%lld",&n,&m);
	vector > q(n,vector (n));
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < n ; j ++){
			scanf("%d",&q[i][j]);
		}
	}
	vector > s = binpow(q,m);
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < n ; j ++){
			if(j) printf(" ");
			printf("%d",s[i][j]);
		}
		if(i + 1 != n) puts(" ");
	} 
}

int main()
{
	solve();
 	return 0;
}