kmjp's blog

競技プログラミング参加記です

Google Code Jam 2008 Round 1A : C. Numbers

GCJ

この問題はGCJ2009の宣伝で使われていたので印象深い問題。
この宣伝みてGCJ出るの決めたんだよね。
http://code.google.com/codejam/contest/32016/dashboard#s=p2


問題はnを与えられたとき(3+\sqrt{5})^nの整数部分下３桁を答えるというもの。
nは最大2000000000なので、まともにn回掛け算すると時間も精度も足りない。

ここでA_n = (3+\sqrt{5})^n + (3-\sqrt{5})^nとすると、(3-\sqrt{5})^n < 1なので答えはA_n - 1の整数部分になる。
ここでA_nを漸化式に落とし込むことを考えると、以下の様になる。

A_{n+1} = (3+\sqrt{5})^{n+1} + (3-\sqrt{5})^{n+1}
= ( (3+\sqrt{5})^n + (3-\sqrt{5})^n)( (3+\sqrt{5}) + (3-\sqrt{5})) - ( (3+\sqrt{5})^n (3-\sqrt{5}) + (3-\sqrt{5})^n (3+\sqrt{5})
= 6( (3+\sqrt{5})^n + (3-\sqrt{5})^n) - 4 ( (3+\sqrt{5})^{n-1} + (3-\sqrt{5})^{n-1})
= 6A_n - 4A_{n-1}

この漸化式を20億回回す時間はないので、高速化することを考える。
\left( \begin{matrix} A_{n+1} \\ A_n \end{matrix}\right) = \left( \begin{matrix} 6 & -4 \\ 0 & 1 \end{matrix}\right)\left( \begin{matrix} A_n \\ A_{n-1} \end{matrix}\right) = \left( \begin{matrix} 6 & -4 \\ 0 & 1 \end{matrix} \right)^n \left( \begin{matrix} A_1 \\ A_0 \end{matrix}\right) = \left( \begin{matrix} 6 & -4 \\ 0 & 1 \end{matrix}\right)^n \left( \begin{matrix} 6 \\ 2 \end{matrix}\right)

最後の行列のn乗はO(logN)で計算できる。
最後に1引くのを忘れずに。

int N;

void solve(int _loop) {
	int i,j,k,m,result;
	int A[2][2],B[2][2],E[2][2],NE[2][2];
	
	N=GETi();
	//A(n+1)=6An-4(n-1)
	A[0][0]=6;
	A[1][0]=996; //1000-4
	A[0][1]=1;
	A[1][1]=0;
	E[0][0]=E[1][1]=1;
	E[0][1]=E[1][0]=0;
	
	while(N>0) {
		
		if(N&1) {
			// E=E*A
			NE[0][0]=(E[0][0]*A[0][0]+E[1][0]*A[0][1])%1000;
			NE[1][0]=(E[0][0]*A[1][0]+E[1][0]*A[1][1])%1000;
			NE[0][1]=(E[0][1]*A[0][0]+E[1][1]*A[0][1])%1000;
			NE[1][1]=(E[0][1]*A[1][0]+E[1][1]*A[1][1])%1000;
			memcpy(E,NE,sizeof(E));
		}
		
		// B=A*A
		B[0][0]=(A[0][0]*A[0][0]+A[1][0]*A[0][1])%1000;
		B[1][0]=(A[0][0]*A[1][0]+A[1][0]*A[1][1])%1000;
		B[0][1]=(A[0][1]*A[0][0]+A[1][1]*A[0][1])%1000;
		B[1][1]=(A[0][1]*A[1][0]+A[1][1]*A[1][1])%1000;
		memcpy(A,B,sizeof(A));
		N>>=1;
	}
	
	// A1=6, A0=2
	result = (((6*E[0][1]+2*E[1][1]-1)%1000)+1000)%1000;
	_PE("Case #%d: %03d\n",_loop, result);
}

まとめ

昔、最初自分で解く前に他の人の回答見てなんで行列演算してるか不思議だった。
漸化式を行列で表現すると、n乗がすんなり計算できていいね。