Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #215 - Mã nguồn bài LATGACH4-Sử dụng tích ma trận, độ phức tạp log(n)
Ngày: 01-07-2011
Cập nhật: 29-08-2011
Người gửi: timxad
Ngôn ngữ: C++
Xem: 803

Điểm: 4.2/5 (5 Phiếu)


//============================================================================
// Name        : LATGACH4.cpp
// Author      : ThucDX
// Version     :
// Copyright   : 
// 
//============================================================================
 
/*
 * Dat W_k la ma tran 2x1( 2 dong,1 cot) [F_(k+1),F_k]^T  (transpose)
 * thi co cong thuc: W_k= A. W_(k-1) voi A =[1,1]
 * _________________________________________[1,0]
 * => W_n=A^(n-1). W_1 .
 *
 *  W_1 biet roi nen chi can tinh A^(n-1) bang phuong phap chia doi.
 */
#include <iostream>
#include <stdio.h>
#define REMAIN 111539786
using namespace std;
struct matrix{
	long long a11,a12,a21,a22;
	void operator=(matrix b){
		a11=b.a11;
		a12=b.a12;
		a21=b.a21;
		a22=b.a22;
	}
};
inline matrix mu(matrix mat, long long n);
inline matrix nhan(matrix A, matrix B);
int main() {
	matrix a,b;
	int i,nTest,n;
	a.a11=1;
	a.a12=1;
	a.a21=1;
	a.a22=0;
	scanf("%d",&nTest);
	for(i=1;i<=nTest;++i){
		scanf("%d",&n);
		switch(n){
		case 1: printf("%d\n",1);break;
		case 2: printf("%d\n",2);break;
		default:
			b=mu(a,n-2);
			printf("%lld\n",((b.a11<<1)+b.a12)%REMAIN);
			break;
		}
	}
 
}
matrix mu(matrix mat, long long n){
	if(n==1) return mat;
	matrix tmp,result;
	tmp=mu(mat,n>>1);
	result=nhan(tmp,tmp);
	if(n&1)//n le
		result=nhan(result,mat);
	return result;
}
matrix nhan(matrix A, matrix B){
	matrix result;
	result.a11= (A.a11*B.a11+A.a12*B.a21)%REMAIN;
	result.a12= (A.a11*B.a21+A.a12*B.a22)%REMAIN;
	result.a21= (A.a21*B.a11+A.a22*B.a21)%REMAIN;
	result.a22= (A.a21*B.a12+A.a22*B.a22)%REMAIN;
	return result;
}