NOI 2003 매트릭스 게임

제목 대의: 주어진 abcd 와 규칙 은 큰 행렬 의 마지막 수의 값 을 계산 해 야 합 니 다.
제목 분석: 두 번 의 빠 른 멱 은 마지막 한 줄 에 대해 두 가지 처리 방법 이 있 습 니 다. 마지막 줄 의 첫 번 째 줄 까지 계산 한 다음 에 빠 른 멱 으로 마지막 줄 까지 계산 한 다음 에 d 를 줄 이 고 다시 / c 를 줄 일 수 있 습 니 다. 계 산 된 행렬 은 구조 가 매우 좋 습 니 다. [a, b] 와 [c, d] (두 번 째 행위 [1, 0]) 를 관찰 한 결과 이 두 행렬 의 두 번 째 줄 이 모두 변 하지 않 았 음 을 알 수 있 습 니 다. 그래서 첫 번 째 줄 의 행렬 을 직접 계산 하여 상 수 를 낮 추 는 것 도 페 르 마 소장 n 과 m 를 10 ^ 9 이하 의 등급 으로 낮 출 수 있 습 니 다. 빠 른 속도 로 하면 됩 니 다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define phiF (1000000006)
#define MAXN (1000000+10)
typedef long long LL;

 
struct M{LL x,y;}A,B,C;
LL P=1e9+7,a,b,c,d,n,m,phi;
char s1[1000010],s2[1000010];

void mi(char*s,LL&aa){
	for(int t=0;s[t];t++)
	aa=(aa*10+s[t]-'0')%phi;
}

M operator*(const M&a,const M&b){
	return (M){a.x*b.x%P,(a.x*b.y+a.y)%P};
}

M operator^(M t,LL k){
	M f=t;
	for(--k;k;k>>=1,t=t*t)
	if(k&1)f=f*t;
	return f;
}

int main(){
    scanf("%s%s%lld%lld%lld%lld",s1,s2,&a,&b,&c,&d);
    if(a==1&&c==1)phi=P;else phi=P-1;
    mi(s1,n);mi(s2,m);
	A=(M){a,b},B=(M){c,d};
	A=A^(m-1);C=B*A;
	C=C^(n-1);A=A*C;
    printf("%lld",(A.x+A.y)%P);
}

좋은 웹페이지 즐겨찾기