Algo

f(1) = 1
f(2) = 2
f(3) = 3
f(x) = f(x-1) + f(x-2) + f(x-3) untuk x>3
Berapakah nilai 4 digit terakhir dari f(1,000,000,000,000,007) ?
(tantangan dari soal ini adalah bagaimana kita menghitung nilai secara cepat).

Soal ini membutuhkan teknik perkalian matriks, teori modular aritmatika dan cara cepat memangkatkan bilangan.

Coba perhatikan matriks berikut:

A = [1 2 3] (isinya dari f(1), f(2) dan f(3))

B = 0 0 1
1 0 1
0 1 1

Coba kalikan A dengan B maka kita akan dapatkan

[2 3 6]

kalikan lagi dengan B maka kita akan dapatkan

[3 6 11]

kalau diperhatikan setiap elemen dalam matriks tersebut akan bergeser dan elemen terakhir akan digantikan dengan nilai penjumlahan 3 elemen sebelumnya.

Nah dari situ kita bisa mengambil kesimpulan bahwa jika ingin mendapatkan nilai f(X) kita harus melakukan perkalian matriks sebanyak X-3 kali untuk mendapatkan hasil di element terakhir.
Contoh:
Mau tau nilai f(4) berarti matriks A dikalikan 1x dengan B
Mau tau nilai f(5) berarti matriks A dikalikan 2x dengan B
Mau tau nilai f(6) berarti matriks A dikalikan 3x dengan B

((A x B) x B) x B sama dengan A x (B^3)

Berarti untuk menghitung f(1,000,000,000,000,007) sama dengan A x (B^1,000,000,000,000,004)

Nah timbul lagi kesulitan bagaimana kita menghitung nilai B^1,000,000,000,000,004 dengan cepat?

Kita gunakan metode divide and conquer berikut:

ilustrasi ketika menghitung B^35:
B^35 = B^17 * B^17 * B
B^17 = B^8 * B^8 * B
B^8 = B^4 * B^4
B^4 = B^2 * B^2
B^2 = B * B

Dari situ kita lihat bahwa utk menghitung B^35 hanya membutuhkan log2(35) = 5 operasi.
Berarti untuk menghitung B^1,000,000,000,000,004 hanya membutuhkan log2(1,000,000,000,000,004) = 50 operasi.

Nah lalu karena yang diminta hanya 4 digit terakhir tiap perhitungan kita modulus 10000. Teori modular aritmetika:
(a x b) % x = ((a%x) * (b%x)) % x
(a + b) % x = ((a%x) + (b%x)) % x

#include
#include
#include
using namespace std;

#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define CLEAR(x) memset(x,0,sizeof(x))

typedef long long LL;

int MOD = 10000;

struct Matrix {
int m[3][3];
Matrix() { CLEAR(m); }
inline int &operator()(int x,int y) { return m[x][y]; }
inline Matrix operator*(Matrix &a) {
Matrix ret;
REP(i,3) REP(j,3) REP(k,3) ret(i,j) = (ret(i,j) + (*this)(i,k) * a(k,j)) % MOD;
return ret;
}
};

inline Matrix fastpow(Matrix a,LL b) {
if(b==1) return a;
Matrix ret=fastpow(a,b/2);
ret=ret*ret;
if(b%2==1) ret=ret*a;
return ret;
}

inline int calc(LL n) {
n--;
int f[]={1,2,3};
if(n<=2) return f[(int)n];

Matrix a;
a(1,0) = 1; a(2,1) = 1;
a(0,2) = a(1,2) = a(2,2) = 1;
a = fastpow(a,n-2);

return (f[0] * a(0,2) + f[1] * a(1,2) + f[2] * a(2,2)) % MOD;
}

int main() {
printf("%d\n",calc(1000000000000007LL));
return 0;


Sumber Kaskus Forum Computer Stuff