AcWing 205. 斐波那契
原题链接
中等
作者:
lyxcqupt
,
2024-04-09 12:54:33
,
所有人可见
,
阅读 10
快速幂+矩阵乘法 很nice
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader((System.in))));
static BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static final int MOD = 10000;
public static void main(String[] args) throws IOException{
while(true) {
int n = getInt();
if(n == -1) break;
pw.println(fib(n));
}
pw.flush();
pw.close();
}
private static int getInt() throws IOException{
st.nextToken();
return (int)st.nval;
}
public static int fib(int n) {
int[][] a = new int[][] {{0,1},{0,0}};
int[][] f = new int[][] {{0,1},{1,1}};
while(n != 0) {
if((n & 1) == 1) a = mul(a,f);
f = mul(f,f);
n >>= 1;
}
return a[0][0];
}
public static int[][] mul(int[][] a,int[][] b){
int[][] c = new int[2][2];
for(int i = 0;i < 2;i++) {
for(int j = 0;j < 2;j++) {
for(int k = 0;k < 2;k++) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
}
}
}
return c;
}
}