블 루 브리지 컵 알고리즘 훈련 매트릭스 곱셈 (매트릭스 빠 른 속도 모드)

알고리즘 훈련 매트릭스 곱셈 
시간 제한: 1.0s  메모리 제한: 512.0MB
    
문제 설명
행렬 A, 비 마이너스 정수 b 와 하나의 정수 m 를 정 하고 A 의 b 제곱 제 m 의 여 수 를 구하 십시오.
그 중에서 nxn 의 행렬 은 m 의 나머지 를 제외 하고 nxn 의 행렬 을 얻 을 수 있 습 니 다. 이 행렬 의 모든 요 소 는 원 행렬 이 대응 하 는 위치 에서 m 를 제외 한 나머지 입 니 다.
이 문 제 를 계산 하려 면 A 를 b 회 곱 하고 매번 m 에 나머지 를 구 할 수 있 지만 이런 방법 은 매우 느 려 서 b 가 비교적 클 때 사용 할 수 없다.다음은 비교적 빠 른 알고리즘 을 제시 합 니 다 (A ^ b 로 A 의 b 제곱 을 표시 합 니 다).
b = 0 이면 A ^ b% m = I% m.그 중에서 I 는 단위 행렬 을 나타 낸다.
b 가 짝수 라면 A ^ b% m = (A ^ (b / 2)% m) ^ 2% m, 즉 A 를 b / 2 로 곱 하고 m 에 여 유 를 구 한 다음 제곱 한 후에 m 에 여 유 를 구 하 는 것 입 니 다.
b 가 홀수 라면 A ^ b% m = (A ^ (b - 1)% m) * a% m, 즉 A 곱 하기 b - 1 차방 이 m 에 여 유 를 구 한 다음 에 A 를 곱 한 후에 m 에 여 유 를 구 하 는 것 이다.
이런 방법 은 속도 가 비교적 빠 르 니 이런 방법 으로 A ^ b% m 를 계산 하 십시오. 그 중에서 A 는 2x2 의 행렬 이 고 m 는 10000 보다 크 지 않 습 니 다.
입력 형식
첫 번 째 줄 에 두 개의 정수 b, m, 두 번 째 줄 과 세 번 째 줄 에 두 개의 정 수 를 포함 하고 행렬 A 를 입력 하 십시오.
출력 형식
두 줄 을 출력 하고 줄 마다 두 개의 정 수 를 출력 하여 A ^ b% m 의 값 을 표시 합 니 다.
샘플 입력
2 2
1 1
0 1
샘플 출력
1 0
0 1

#include <iostream>
#include <cstdio>
using namespace std;
const int N=2;
int m;
struct Matrix{
	int m[N][N];
}matrix;
Matrix I={1,0,
          0,1};
Matrix p;
inline Matrix  multiply(Matrix a,Matrix b){
	  int i,j,k;
	  Matrix re;
	  for(i=0;i<N;i++)
	  for(j=0;j<N;j++){
	  	 re.m[i][j]=0;
	  	 for(k=0;k<N;k++)
	  	   re.m[i][j]+=a.m[i][k]*b.m[k][j];
	  	   re.m[i][j]%=m;
	  }
	  return re;
}
inline Matrix quick_pow(int n){
	Matrix re=p,b=I;
	while(n>0){
		if(n&1){
			b=multiply(b,re);
		}
		n=n>>1;
		re=multiply(re,re);
	}
	return b;
}

int main()
{
   int b;
   while(cin>>b>>m){
   	   for(int i=0;i<2;i++)
   	     for(int j=0;j<2;j++)
   	       cin>>p.m[i][j];
   	       
		matrix=quick_pow(b);
		
   	   for(int i=0;i<2;i++){
   	   	for(int j=0;j<2;j++)
   	     cout<<matrix.m[i][j]%m<<" ";    //     m=1         mod 0 
   	     cout<<endl;
	 } 
			  	     
   }
    return 0;
}