POJ - 3070. Fibonacci

Question

题目

解析

关键在于推导出递推式，也就是左边是一个 A 矩阵， B 一般是一个列向量；

类似的规律：

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

  static class Matrix{
    public int row;
    public int col;
    public int[][] m;

    public Matrix(int row, int col) {
      this.row = row;
      this.col = col;
      m = new int[row][col];
    }
  }

  static final int mod = 10000;


  static Matrix mul(Matrix a,Matrix b){
    Matrix c = new Matrix(a.row,b.col); //注意这里

    for(int i = 0; i < a.row; i++){
      for(int j = 0; j < b.col; j++){
        for(int k = 0; k < a.col; k++)
          c.m[i][j] = (c.m[i][j] + a.m[i][k]*b.m[k][j]) % mod;
      }
    }
    return c;
  }

  static Matrix pow(Matrix a,int k){
    Matrix res = new Matrix(a.row,a.col); // 方阵
    for(int i = 0; i < a.row; i++)
      res.m[i][i] = 1;
    while(k > 0){
      if( (k&1) != 0)
        res = mul(res,a);
      a = mul(a,a);
      k >>= 1;
    }
    return res;
  }

  public static void main(String[] args) {
    Scanner cin = new Scanner(new BufferedInputStream(System.in));

    while(cin.hasNext()){
      int n = cin.nextInt();
      if( n == -1)break;
      if(n == 0){
        System.out.println(0);
        continue;
      }

      Matrix a = new Matrix(2,2);
      a.m[0][0] = a.m[0][1] = a.m[1][0] = 1;
      a.m[1][1] = 0;

      Matrix res = pow(a,n-1);

      System.out.println(res.m[0][0] % mod);
    }
  }

}

题目链接

http://poj.org/problem?id=3070